simple recursive example - please help me understand recursion

    public static int triple(int n)
    {
        if (n == 0)
            return 0;
        else
            total = 3 + triple(n-1);
    System.out.println(total);
    return total;
    }

Ok, so I've got this simple recusion example that I just cant seem to grasp, I was hoping someone would be kind enough to walk me through cycle by cycle of how the program gets its output.

Here is what I thought would happen. Lets say n=5 So, the program cycles and hits total = 3 + triple(5-1) which i would think would be equal to 7.. which is wrong the program prints

3

6

9

12

15

So... then I thought triple must run through again before printing the total... which I believe it does but I just don't understand how it comes to its totals at all then.

Because it would just l开发者_JS百科ook like this :

3 + triple(4)
       3 + triple(3)
               3 + triple(2)
                       3 + triple(1)
                                =3

Can someone explain please, as you can I am very lost!

---

You're interpreting it slightly wrong. It's more like this:

triple(5) = 3 + triple(4)
triple(4) = 3 + triple(3)
triple(3) = 3 + triple(2)
triple(2) = 3 + triple(1)
triple(1) = 3 + triple(0)
triple(0) = 0

Now imagine that triple(0), triple(1), etc. are all individual variables, and solve for triple(5) by working your way up.

---

So wouldn't it work its way down to zero doing (by subtracting 1) then add 3 to each (0 3 6, etc).

This is the output I'm getting:

n:5
n:4
n:3
n:2
n:1
n:0
total:3
total:6
total:9
total:12
total:15

What it's doing is subtracting one from n each enumeration in, then adding 3 to the now 0-5

---

Your output should be read as follows:

3 = triple(1) = 3+triple(0)
6 = triple(2) = 3+triple(1)
9 = triple(3) = 3+triple(2)
12 = triple(4) = 3+triple(3)
15 = triple(5) = 3+triple(4)

It is because triple(n) would invoke triple(n-1) before printing out the message. So your triple(5) message will be printed last.

---

When the execution hits that point, the triple method begins executing again from the start. Once it returns, execution will then resume at the next line. This happens recursively.

So the order of execution is something like:

1. if (n == 0) // n == 5 at this point, condition is false
2. total = 3 + triple(n-1) // we must calculate triple(4)
3. if (n == 0) // n == 4 now.
4. total = 3 + triple(n-1) // we must calculate triple(3)
5. ... etc, until n does == 0:
6. if (n == 0) // true!
7. return 0 // returns 0
8. total = 3 + 0 // 0 comes from triple(n-1), which just returned 0
9. System.out.println(total); // prints 3
10. return total; // returns 3
11. total = 3 + 3; // again 3 comes from triple(n-1), where n==2
12. System.out.println(total); // prints 6 this time
13. ... and so on.

Note the function as defined just multiplies the input by 3, and prints the result at each multiple.

---

public static int triple(int n)
{

if (n == 0)
return 0;
else
return 3 + triple(n-1);
System.out.println(return);
}

Disregard the println(return) its just for understanding purposes. This is how i broke it down to finally get a good grasp on recursive functions/methods.

triple(3)
return 3 + triple(3-1)_is_6<---- (return = 9)<--
println(return)

    triple(2)
    return 3 + triple(2-1)_is_3<-- (return = 6)<----
    println(return);

              triple(1)
              return 3 + triple(1-1)_is_0<---- (return = 3)<--
              println(return)

                       triple(0)
                       return 0; is 0 (return = 0)<----
                       (no println for n==0)

Thank you all for you help in understanding this. The thing I was not doing was remembering that each triple(n-1) returned its own value that was then calculated into the call above it.

THANKS AGAIN!

---

triple(0) = 0
triple(1) = 3 + triple(0) i.e. 3+0=3
triple(2) = 3 + triple(1) i.e. 3+3=6
triple(3) = 3 + triple(2) i.e. 3+6=9
triple(4) = 3 + triple(3) i.e. 3+9=12
triple(5) = 3 + triple(4) i.e. 3+12=15

---

You got confused between triple(n-1) and (n-1). They are different thing, so you cannot just assign the value to n inside triple(n-1) and then add it to 3