Drago - 1 year ago 86
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?

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`.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download