Drago - 1 year ago 71

Java Question

`public static int fun(int n) {`

if (n<=1) return 1;

else return (n + fun(n-1));

}

Why does

`fun(6)`

`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()`

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 Source

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`

.