问题描述:

I'm having a tough time in understanding the following code based on recursion algorithm in Java. I don't understand, what's the different value `x`

and `y`

have when they call within one another? I tried to get the right value by calling `System.out.print()`

within a code, but still get no help.

`public class RecursionExample`

{

private static int[][] arr={

{3},

{7, 4},

{2, 4, 6},

{8 ,5, 9, 3}

};

public static int maxSum(int[][] graph, int x, int y, int sum) {

if (x == 3)

{

return sum+graph[x][y];

}

int max= Math.max(maxSum(graph, x+1, y, sum), maxSum(graph, x+1, y+1, sum));

sum += graph[x][y];

return sum+max;

}

public static void main(String[] ar)

{

System.out.println(maxSum(arr,0,0,0));

}

}

I'm not a master in programming, and I'm trying to learn Java by doing. Any help is appreciated.

Essentially, this keeps calling itself until you reach the third iteration (`x==3`

).

So, here's the flow (minus the two calls to `maxSum`

within `max`

...for simplicity's sake) (each indent is a call to `maxSum`

):

```
x = 0
y = 0
sum = 0
x != 3
x = 1
y = 0
sum = 0
x != 3
x = 2
y = 0
sum = 0
x != 3
x = 3
y = 0
sum = 0
x == 3
return 0 + 8 //graph[3][0] == 8
max = 8 //previous return
sum = 0 + 2 //graph[2][0] == 2
return 10 //max + sum == 8 + 2 == 10
max = 10
sum = 0 + 7 //graph[1][0] == 7
return 17
max = 17
sum = 0 + 3 //graph[0][0] == 3
return 20
```

The x and y values you are referring to link to specific numbers in the number pyramid.

What your algorithm does is find the maximum path down the pyramid by adding on the top digit, then splitting the large pyramid into two smaller ones:

```
{7},
{2, 4},
{8 ,5, 9}
```

and

```
{4},
{4, 6},
{5, 9, 3}
```

.

It then does the same process on the smaller pyramids (I will just do it with the top one):

```
{2},
{8 ,5}
```

and

```
{4},
{5, 9}
```

.

Now you can see that when it breaks these pyramids up, it's just left with 2 numbers, so it returns them. As it climbs back up the stack, it compares the returned values and returns the larger one.

Eventually, we get to the top by brute force checking every trail in the pyramid.

(Incidentally, the same problem is on projecteuler.net)

The easiest way to understand what's going on a recursive function is by getting out a pencil and paper and writing out each step till you get to the base case (in this equation, when x == 3). Then work backwards from there, plugging in the returned values in the preceeding steps. What you've got here is head recursion, a situation where the runtime has to solve each step and return from each step until it gets back to the original call by which time, you've got your answer.

The values of x and y are easy as they're arguments -- just look at the many calls to maxSum: at first they're 0 and 0, at every next step x+1 and y+1 (and x+1 and y) wrt the previous step, stopping when x gets to 3. So make a table, or rather a tree...:

```
0, 0
1, 1
2, 2
3, 3
3, 2
2, 1
3, 2
3, 1
1, 0
2, 1
3, 2
3, 1
2, 0
3, 1
3, 0
```

...and, that's all!

您可能感兴趣的文章：

- Gradient trick changed in iPhone 3.0 SDK?
- mysql - zip file saves incomplete with doctrine::createquery->update()
- php - Reload Smarty Template with New Variables?
- jquery - Can I run a JavaScript function AFTER Google Loader has run?
- javascript - jQuery ajax:before event
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- Forward to a payment-gateway together with POST data using cURL (or any other PHP server side solution)
- WCF in Winforms app - is it always single-threaded?

随机阅读：

- 如图，Rt△ABC中，∠ABC=90°，以AB为直径作⊙O交AC边于点D，E是边BC的中点，连接DE．（1）求证：直线DE是⊙O的切线；（2）连接OC交DE于点F，若
- How do I properly reinstall application in the Android emulator from Eclipse?
- 浅绿色溶液A和无色溶液B可进行下列反应，D是一种常见的盐，E是气态氢化物，G是非金属氧化物．（1）填写下列各物质的化学式：A______，B______，H_____
- watir - It seems as though firewatir is not being found when trying to run my script?

**推荐内容**-

**热点内容**