Drago Drago - 2 months ago 18
Java Question

Hard time understanding recursion

public static int fun(int n) {
if (n<=1) return 1;
else return (n + fun(n-1));
}


Why does
fun(6)
return
21
?

How I visualize the recursion is as follow:

6 + 5 = 11
5 + 4 = 9
4 + 3 = 7
3 + 2 = 5
2 + 1 = 3
1 1
11 + 9 + 7 + 5 + 3 + 1 = 36


Could someone please explain to me what is happening here?

-- edit removed the
System.out.println()
, forgot to remove it when i posted the code.

I tried the following on my own:

public static int fun(int n) {
if (n==1) return 2;
else return 2 * fun(n-1);
}

2 * fun(4)
2 * (2 * fun(3))
2 * (2 * (2 * fun(2)))
2 * (2 * (2 * (2 * fun(1))))
2 * 2 * 2 * 2 * 2 = 32


Is this the right way of visualizing it?

Answer

Each call to fun ends up doing return n + fun(n-1);. So let's step through and see what happens.

You call fun(6) which...

evaluates to 6 + fun(5) which...

evaluates to 6 + (5 + fun(4)) which...

evaluates to 6 + (5 + (4 + fun(3))) which...

evaluates to 6 + (5 + (4 + (3 + fun(2)))) which...

evaluates to 6 + (5 + (4 + (3 + (2 + fun(1))))) and since fun(1) = 1, this

evaluates to 6 + 5 + 4 + 3 + 2 + 1 which is 21.