CODEWITHSUNDEEP
javarecursion
Drago
Drago

Reputation: 1875

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?

Upvotes: 3

Views: 337

Answers (4)

nhouser9
nhouser9

Reputation: 6780

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.

Upvotes: 6

apajak
apajak

Reputation: 21

First line "System.out.println(n + " " + (n-1));" shows only the values of variable 'n' and DOESN'T CONTAIN ANY ARITHMETIC OPERATIONS.

Steps of this function:

6>1 so: 6 + fun(5),

5>1 so: 6 + 5 + fun(4),

4>1 so: 6 + 5 + 4 + fun(3),

3>1 so: 6 + 5 + 4 + 3 + fun(2),

2>1 so: 6 + 5 + 4 + 3 + 2 + fun(1),

1>=1 so: 6 + 5 + 4 + 3 + 2 + 1

and the SUM of: 6 + 5 + 4 + 3 + 2 + 1 = 21

I hope my explanation will be useful for you.

Upvotes: 1

Andreas
Andreas

Reputation: 5103

fun(6) = 6 + fun(5)
       = 6 + 5 + fun(4)
       = 6 + 5 + 4 + fun(3)
       ...
       = 6 + 5 + 4 + 3 + 2 + 1 = 21

Upvotes: 1

Emil Kantis
Emil Kantis

Reputation: 1114

I think it's simpler to visualize it as:

fun(6) =
6 + fun(5) =
6 + 5 + fun(4) =
...
6 + 5 + 4 + 3 + 2 + 1 =
21

Basically each recursive call moves us one step closer to a termination (n <= 1). The final result can only be computed once termination has been reached

Upvotes: 6

Related Questions