CODEWITHSUNDEEP
javarecursion
Malinator
Malinator

Reputation: 143

Explaining an output to a recursion example

Can someone explain why the output to this is 6? I don't really understand why.

public class blah {
    public static int blah( int n, int m){
      if (m ==0 || n==m || n==2)
         return 1;
      else if (m>n)
         return 0;
      else 
         return blah(n-1,m-1) + blah(n-1,m);
    }
    public static void main(String [] args){
        System.out.println (blah(7,6));
    }

}

from what I understand the outputs should be

(6,5)+(6,6)
(5,4)+(5,5)
(4,3)+(4,4)
(3,2)+(3,3)
(2,1)+(2,2)---->2
(1,0)+(1,1)---> 2
=4?

Upvotes: 0

Views: 50

Answers (2)

mech
mech

Reputation: 2913

The actual resolution looks closer to this (remember that if n==m then blah(n,m) returns 1):

(7,6)
(6,5) + (6,6)=1
(5,4) + (5,5)=1 + 1
(4,3) + (4,4)=1 + 1 + 1
(3,2) + (3,3)=1 + 1 + 1 + 1
(2,1)=1 + (2,2)=1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1

Which is ==6.

Upvotes: 4

Prune
Prune

Reputation: 77837

I took the simple debugging step of printing the arguments on entry to the routine, arguments and result on exit. Here's a trace for you. Can you take it from here? @mech identified the basic rationale nicely: each case of m=n returns another 1 to be added, and those run from (6,6) down to (2,2). Add in the returned 1 for case (2,1), and you have your answer.

           n m result
ENTER blah 7 6
ENTER blah 6 5
ENTER blah 5 4
ENTER blah 4 3
ENTER blah 3 2
ENTER blah 2 1
LEAVE blah 2 1 1
ENTER blah 2 2
LEAVE blah 2 2 1
LEAVE blah 3 2 2
ENTER blah 3 3
LEAVE blah 3 3 1
LEAVE blah 4 3 3
ENTER blah 4 4
LEAVE blah 4 4 1
LEAVE blah 5 4 4
ENTER blah 5 5
LEAVE blah 5 5 1
LEAVE blah 6 5 5
ENTER blah 6 6
LEAVE blah 6 6 1
LEAVE blah 7 6 6

Upvotes: 3

Related Questions