Unable to understand Recursivly calling same method with two different input

Question

I have recently started getting my hands on recursion. I have gone through some of the online documents available, but unable to understand how the recursion calls works when we call a same method with different inputs.

Just suppose, in case of tree i have seen

return find(node.left) + find(node.right);

I am unable to understand how that works.

In general recursion every call gets a place in stack and when the base condition reaches we compute and return the result. I tried doing a small program where i called the same method from tow different caller with different index and if the base condition is reached, add the both returned value.

if(n==0){
        return arr[n];
    }

    else {
        return calculateSum(arr, n-1) + arr[n];
    }

The code works well. Now i moved forward and tried something like this.

And it is giving me stack overflow.

if(n==1){
        return arr[n];
    }

    else {
        return calculateSum(arr, n-1) + calculateSum(arr, n-2);
    }

I am completely unable to understand how it is happening, what am i missing out to from this topic to unable to understand it completely.

I have changes my code on based of suggestion provided. But unable to understand the flow. How the n-2 is funtioning. I gave some print. Please find the print and Code below.

private static int calculateSum(int[] arr, int n, String caller){

    if(n<=1){
        System.out.println(caller+" : "+n+ " : "+arr[n]);

        return arr[n];
    }

    else {
        return calculateSum(arr, n-1," minus one") + calculateSum(arr, n-2,"minus two");
    }


}

Prints :

minus one : 1 : 2

minus two : 0 : 1

minus two : 1 : 2

minus one : 1 : 2

minus two : 0 : 1

minus one : 1 : 2

minus two : 0 : 1

minus two : 1 : 2

Sum of the array :13

If someone can help me to understand how it is working . I am wondering how the minus two value is getting as 0 in the beginning and then as 1. and why minus one is been called again after minus two when once it has reached to attained the base condition.

Note : I have removed the arr[n] with the return statement. so, for now i want to understand the calling and how it is working.

Answer 1

In this case you have not applied the correct base condition

See, your program:-

cal(arr,n){
if(n==1){
        return arr[n];
    }

    else {
        return calculateSum(arr, n-1) + calculateSum(arr, n-2);
    }

}

Take an example now,arr = [1,2,3] n = 3

Cal(arr,3){
// Base condtn fails
Recursion takes place now
cal(arr,2) + cal(arr,1);

}

Now, execute

cal(arr,2){
// Base condtn fails
Recursion takes place now
cal(arr,1) + cal(arr,0);
}

Now , execute

cal(arr,1){
// Base condtn true return arr[1]
}

Now, execute

cal(arr,0){
// Base condtn fails here also stackoverflow now never returning
}

Though sum can't be find out by this recursion, Use this

cal(arr, n)
{
    if (n <= 0)
        return 0;
    return (cal(a, n-1) + arr[n-1]);
}

Answer 2

Your last version of the program has a number of problems, not least of which is that the only element of the array ever included in the sum is arr[1].

The reason for the stack overflow, however, is that it is possible to generate a call to calculateSum where the second argument is 0 (for example, the second recursive call when n==2), which will fail the base-case test and, because subsequent recursive calls have even smaller values for n, will never succeed.

The way I have found most helpful to think about recursion is imagine that someone else has written a function that solves your problem for "smaller" versions of that problem (for example, any sub-tree, or any smaller value of n; whatever is appropriate). Write your function making use of that one, making sure that a) whenever you call it, it is with a smaller version of the problem, and b) if you have a small enough version of the problem that you can solve without a recursive call, don't make the recursive call. (Note that, if you apply this technique to your final bit of code, you can see that, even if the recursive calls worked properly, you'd be double-counting most of the array. And it is clear that your earlier version is correct.)

Here's the magic: by doing what I described above, you have written the very function that you assumed that someone else has written.