CODEWITHSUNDEEP
c++
user3857907
user3857907

Reputation: 39

How addition of 2 recursive function works

How does the recursive function return printCountRec(dist-1) + printCountRec(dist-2); works in following code. By my logic The printCountRec(dist-1) function call will return 1 and printCountRec(dist-2) will return 0 by adding these two ,answer should be 1+0 i.e 1 but I am getting the answer as 3. I am not getting it.

Program for Count number of ways to cover a distance; The code is as follows-

#include <iostream>
using namespace std;


int printCountRec(int dist)
{
    // Base cases
    if (dist<0)    return 0;
    else if (dist==0)  return 1;

    // Recur for all previous 3 and add the results
   else   return printCountRec(dist-1)  + printCountRec(dist-2);

}

int main()
{
    int dist = 3;
    cout << printCountRec(dist);
    return 0;
}

Upvotes: 0

Views: 393

Answers (3)

Shridhar R Kulkarni
Shridhar R Kulkarni

Reputation: 7063

dist = -1 outputs 0

dist = 0 outputs 1

dist = 1 outputs 1

dist = 2 outputs 2

dist = 3 outputs 3

printCountRec(2) = printCountRec(1) + printCountRec(0) = 2

printCountRec(3) = printCountRec(2) + printCountRec(1) = 2 + 1 = 3.

Upvotes: 0

Marievi
Marievi

Reputation: 5009

The printCountRec(dist-1) function call will return 1 and printCountRec(dist-2) will return 0

How did you suppose this? Step by step :

  • printCountRec(dist-1) means printCountRec(2), which will call printCountRec(1) + printCountRec(0). For these two, the first will call printCountRec(0) + printCountRec(-1), which will return 1+0 = 1 to printCountRec(2), and the second will return 1 to printCountRec(2).

    In other words you have this order :

    printCountRec(dist-1) = printCountRec(2) -->
printCountRec(1) + printCountRec(0) -->
printCountRec(0) + printCountRec(-1) + 1 -->
1 + 0 + 1 --> 3

    So the first member of the addition is evaluated to 2.

  • printCountRec(dist-2) means printCountRec(1), which will call printCountRec(0) + printCountRec(-1) , returning 1+0 = 1 to printCountRec(1).

    In other words you have this order :

    printCountRec(dist-2) = printCountRec(1) -->
printCountRec(0) + printCountRec(-1) -->
1 + 0 --> 1

    So the second member of the addition is evaluated to 1.

Adding the two members (2 and 1) gives you the result 3.

Upvotes: 0

user1245262
user1245262

Reputation: 7505

This is how I'm following your recursion:

printCountRec(-1) = 0
printCountRec(0) = 1
printCountRec(1) = printCountRec(0) + printCountRec(-1) = 1
printCountRec(2) = printCountRec(1) + printCountRec(0) = 2
printCountRec(3) = printCountRec(2) + printCountRec(1) = 3

Upvotes: 2

Related Questions