CODEWITHSUNDEEP
javarecursion
Karan Khosla
Karan Khosla

Reputation: 33

2 recursive calls in function in Java

I am having some problems with Recursion in Java. Here is my code

public class recursionTrial {

public static void main(String[] args)
{
System.out.println(doSomething(6));
}

public static int doSomething(int n)
{
    if (n==0 || n==1)
        return 0;

    else
        return n + doSomething(n-1) + doSomething(n-2);


}

}

Which gives me an output of 38. However I am unable to trace the recursive function in my head or on paper. How will the working out look? 6+5.... and so on.

I get if it were just 

return n + doSomething(n-1)

then it would be 6+5+4+3+2 = 20 ; it is the second part of the code that is confusing me. If someone could explain to me how to trace the recursive function properly and write the working out I would appreciate it! Also is there a way to write a piece of code that prints the value of n before it changes each time?

Upvotes: 1

Views: 1903

Answers (5)

Zereges
Zereges

Reputation: 5209

Beware that this has exponential complexity.
doSomething(6) calls doSomething(5) and doSomething(4)
doSomething(5) calls doSomething(4) and doSomething(3)
doSomething(4) calls doSomething(3) and doSomething(2)
doSomething(3) calls doSomething(2) and doSomething(1)
doSomething(2) calls doSomething(1) and doSomething(0)
doSomething(1) is 0 doSomething(0) is 0

This illustrates callings of doSomething(), they are not results, since you are adding n for each call.

                      6
               _______|_______
              /               \
             5                 4
         ____|____            _|_
        /         \          /   \
       4           3        3     2
      _|_          |        |     |
     /   \        / \      / \   / \
    3     2      2   1    2   1 1   0
   / \   / \    / \      / \
  2   1 1   0  1   0    1   0
 / \  
1   0

Upvotes: 0

Ely
Ely

Reputation: 11174

public static int doSomething(int n) {
    if (n==0 || n==1)
        return 0;
    else
        return n + doSomething(n-1) + doSomething(n-2);
}

You could try to expand recursively, this is conceptually what the program does.

doSomething(6) expands to 6 + doSomething(5) + doSomething(4)

doSomething(5) expands to 5 + doSomething(4) + doSomething(3)

doSomething(4) expands to 4 + doSomething(3) + doSomething(2)

...

Simply go down the recursion. For example (I use dS for doSomething):

dS(6) = 6 + dS(5) + dS(4) =

6 + 5 + dS(4) + dS(3) + 4 + dS(3) + dS(2) = 

6 + 5 + 4 + dS(3) + dS(2) + 3 + dS(2) + dS(1) + 4 + 3 + dS(2) + dS(1) + 2 + dS(1) + dS(0) =

6 + 5 + 4 + 3 + dS(2) + dS(1) + 2 + dS(1) + dS(0) + 3 + 2 + dS(1) + dS(0) + 0 + 4 + 3 + 2 + dS(1) + dS(0) + 0 + 2 + 0 + 0 =

6 + 5 + 4 + 3 + 2 + dS(1) + dS(0) + 0 + 2 + 0 + 0 + 3 + 2 + dS(1) + 0 + 0 + 4 + 3 + 2 + 0 + 0 + 0 + 2 + 0 + 0 =

6 + 5 + 4 + 3 + 2 + 0 + 0 + 0 + 2 + 0 + 0 + 3 + 2 + 0 + 0 + 0 + 4 + 3 + 2 + 0 + 0 + 0 + 2 + 0 + 0 =

38 <-- Final result

Upvotes: 0

themiDdlest
themiDdlest

Reputation: 106

doSomething(1)= return 0,

doSomething(2)== 2+dosomething(1)= 2+0=2,

doSomething(3)=3+doSomething(2)=3+2=5,

doSomething(4)=4+doSomething(3)+doSomething(2)=4+5+2=11

doSomething(5)=5+doSomething(4)+doSomething(3)=5+11+5=21,

doSomething(6)=6+doSomething(5)+doSomething(4)=6+21+11=38

Start at doSomething(6), it calls: doSomething(5) go to that line, to figure out doSomething(5) we need to know doSomething(4) and doSomething(3).... and work your way up the tree, till you get to an actual "Return value" which in this case would be when we reach doSomething(1), then put those values in as you back down the tree.

Upvotes: 0

Debasis
Debasis

Reputation: 3750

Your recursive function is

f(n) = n + f(n-2) + f(n-1)

The execution flow is as follows.

  1. f(n-2) is evaluated first... To compute f(n-2) the program again makes a recursive call to f(n-4) and f(n-3) and so on...
  2. Next, f(n-1) is evaluated... this again depends on computed values of f(n-3) and f(n-2) and so on...
  3. These two values are added with n to get the final result...

For example, the recursion tree for n=4 is as follows (I'm not showing the addition with n for simplicity):

f(4) {
    f(2) {
        f(0) {0}
        f(1) {0} 
    }
    f(3) {
        f(1) {0}
        f(2) { 
            f(0) {0} 
            f(1) {0}
        }
    }
 }

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726929

In the absence of side effects one can think of this recursive function as of a regular function. You can draw a small table showing the results of invocation of your function, starting with zero:

n res computation
- --- -----------
0   0           0
1   0           0
2   2       2+0+0
3   5       3+2+0
4  11       4+5+2
5  21      5+11+5
6  38     6+21+11

No special mental treatment is required for the second recursive invocation: it is the same as the first one.

Note: your function will be taking progressively longer time as the value of n goes up, because it would be re-doing a lot of computations it has already done. Fortunately, this can be addressed with a simple and very common trick, called memoization.

Upvotes: 2

Related Questions