问题描述:

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?

随机阅读：

**推荐内容**-

**热点内容**-
- php - Reading a specific line from a text file
- clr - Any implementation of an Unrolled Linked List in C#?
- Finding Hudson Log Files
- WCF in Winforms app - is it always single-threaded?
- git svn - git svn fetch does not fetch a Subversion commit message modified after initial clone
- java me - Why I am getting the bad length exception when I am running this application?
- java - How to get string.format to complain at compile time
- ruby on rails - Trigger observer of parent class on change
- python - Issue with URL pattern in Django with webmonkey tutorial