Many call of function in Recursion

Question

I was implementing maxPathSum function using recursion and I didn't know what happens when using two calls in the function .i know then that is called binary recursion and know how to think about it from this reply on that question Understanding double recursion

but when I write the code it didn't give me the right answer [Note that] the only direction needed is right and down

#include <iostream>
#include<algorithm>
using namespace std;
const int MAX=3;
int grid[MAX][MAX]={
                    {5,1,2},
                    {6,4,8},
                    {1,8,9}
};

bool valid(int r, int c);//check not get out grid
int maxPathSum(int r,int c);

int main()
{
    int sum=0;
    for(int i=0;i<MAX;i++)
    sum += maxPathSum(i,i);
    cout<<"the sum of the  longest path is: "<<sum;
}

int maxPathSum(int r,int c){
    if(!valid(r,c))
        return 1;

     //Reach the last element in the last right down
    if(r == MAX-1 && c == MAX-1)
        return grid[r][c];

    int path1=maxPathSum(r,c+1);//Right
    int path2=maxPathSum(r+1,c);//down

    return grid[r][c]+max(path1,path2);
}

 bool valid(int r, int c){
    if(r > MAX-1)
        return false;
    if(c > MAX-1)
        return false;

    return true;
}

when I call the function without loop in main sometimes it give me the right answer

like that with low matrix length

const int MAX=2;
int grid[MAX][MAX]={
                    {5,2},
                    {1,8}
};
maxPathSum(0,0);

`if(!valid(r,c)) return 1;` Shouldn't this case be `return 0`? — jcai, Jul 09 '17 at 08:03
Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation. [Minimal, complete, verifiable example](http://stackoverflow.com/help/mcve) applies here. In particular, include the actual and expected output frmo your problem case. — Prune, Jul 10 '17 at 16:15

SugarOnBacon · Accepted Answer · 2017-07-09T09:45:43.780

You are making a double sum.

return grid[r][c]+max(path1,path2)

This piece of code already sums elements on the path.

for(int i=0;i<MAX;i++)
sum += maxPathSum(i,i);

maxPathSum will return the sum of all elements on the path between (i,i) and (2,2). Then sum will contain the sum of all of those sums on on the diagonal elements. I don't think you want that.

Calling maxPathSum(0,0) in main should give the answer.

Now lets say you call maxPathSum(1,2). This function will then call maxPathSum(2,2) and maxPathSum(1,3). The first will return e22 and the latter 1. If e22=0 the result will be incorrect.

I am answering the question for the problem of finding the maximum path between (0,0) and (max-1,max-1). If the problem is not defined like that, you should specify it clearly.

Many call of function in Recursion

1 Answers1