Recursion

[insanely_sane]

Yeah... I have a headache...

So I have the following code:

public class inc
{
    public static void main (String args[])
    {
        new inc();
    }
    
    public inc()
    {
        System.out.println (addTwo(7));
    }
    
    public int addTwo(int n)
    {
        System.out.println (n);
        if (n < 1)
        {
            return 2;
        }
        else
        {
            return addTwo(n-1)+2;
        }
        
    }
    
}

Can anyone PLEASE trace it line by line and tell me what in Alan Turing's name is going on? Like explain the whole recursive part properly...

and please point me to the best website which I can use to understand recursion properly.

Thank you.

[kvass]

Here's a very simple example of recursion to help you get started with understanding it:

Problem: Write a program to add all the numbers from 1 to X.
Solution:

public static int addFrom1(int x)
{
    if (x<1)
        return 0;
    else if (x==1)
        return 1;
    else
        return x + addFrom1(x-1);
}

So what exactly is happening here? Let's put in the number 4 and trace this program.

Is 4 < 1? No. Is 4 == 1? No. So now we go into the last option. Return 4 + addFrom1(4-1), or rather, 4 + addFrom1(3). So then now we call the function with x as 3.

Is 3 < 1? No. Is 3 == 1? No. So now we go into the last option. Return 3 + addFrom1(3-1), or rather, 3 + addFrom1(2). So then now we call the function with x as 2.

Is 2 < 1? No. Is 2 == 1? No. So now we go into the last option. Return 2 + addFrom1(2-1), or rather, 2 + addFrom1(1). So then now we call the function with x as 1.

Is 1 < 1? No. Is 1 == 1? YES! So now we return 1 as the answer.

We received 1 as our answer for addFrom1(1), so now we can substitute and get return 2 + 1 , so 3 is returned.

We received 3 as our answer for addFrom1(2), so now we can substitute and get return 3 + 3 , so 6 is returned.

We received 6 as our answer for addFrom1(3), so now we can substitute and get return 4 + 6 , so 10 is returned.

So now we have recursively added the numbers from 1 to 4, and have found that the answer is 10.

Basically the way recursion works is that you are repeating the same process over and over again as you come closer and closer to a base case, which is the bottom-most case your function can reach. In our example, we started at 4, and came closer and closer to the base case of 1, where the function simply returns 1 instead of once again invoking the method.

To write a recursive function, use the following format:

function header
{
    if (base case)
        return a certain value.
    else //Not the base case
        return something and call the method again on a value closer to the base case.
}

So take my example above. x<1 and x==1 were the two base cases, returning 0 and 1 respectively. In all other cases, the answer is based on method calls that come closer and closer to these base cases. So before when we called the method addFrom1() on 4, it was to return a value that depended on addFrom1(3), which was closer to the base case than addFrom1(4). addFrom1(3) depended on addFrom1(2), which was again closer to the base case. addFrom1(2) depended on addFrom1(1), which was the base case. So then addFrom1(1) returned the value of 1, and then it goes all the way back up the chain.

So now onward to your problem.

public int addTwo(int n)
{
    System.out.println (n);
    if (n < 1)
    {
        return 2;
    }
    else
    {
        return addTwo(n-1)+2;
    }
}

You are calling this function on the value of 7. So addTwo(7) does not invoke the base case because it is not less than 1. Therefore, it returns addTwo(7-1)+2, or addTwo(6)+2.

addTwo(6) does not invoke the base case because it is not less than 1. Therefore, it returns addTwo(6-1)+2, or addTwo(5)+2.

addTwo(5) does not invoke the base case because it is not less than 1. Therefore, it returns addTwo(5-1)+2, or addTwo(4)+2.

I'm not going to follow this all the way down the chain, but you get the idea. Eventually it gets to the base case of addTwo(0), which is the first time n is less than 1. This returns 2.

addTwo(1) can then be simplified from addTwo(0)+2 to 2+2, and returns 4.

addTwo(2) can then be simplified from addTwo(1)+2 to 4+2, and returns 6.

addTwo(3) can then be simplified from addTwo(2)+2 to 6+2, and returns 8.

Again, you can follow this all the way up the chain to addTwo(7), which ultimately returns 16.

Hopefully this explained recursion well enough... good luck!!!

[insanely_sane]

And... I believe... this thread is solved. Thank you kvass.