CODEWITHSUNDEEP
c++recursion
anima
anima

Reputation: 19

Recursion with Double Call (C++)

Can someone please explain to me how exactly this adds up to 26?

I get confused by the 'double call'. Maybe I just don't understand recursion as well as I think I do.

#include <iostream>
using namespace std;

int rec(int * N, int max) {
    if (max < 0)
        return 0;

    return N[max] + rec(N, max - 1) + rec(N, max - 2); 
}

int main() {
   const int max = 5;
    int N[] = { 1, 2, 3, 4, 5 };
    int f = rec(N, max - 1);

    cout << f << endl; 
   return 0;
}

Upvotes: 0

Views: 289

Answers (1)

R2-Dequeue
R2-Dequeue

Reputation: 638

int f = rec(N, 4)
      = N[4] + rec(N, 3) + rec(N, 2)
      = 5 + (N[3] + rec(N, 2) + rec(N, 1)) + (N[2] + rec(N, 1) + rec(N, 0))
      = 5 + (4 + (N[2] + rec(N, 1) + rec(N, 0)) + (N[1] + rec(N, 0) + rec(N, -1)) + (3 + (N[1] + rec(N, 0) + rec(N, -1)) + (N[0] + rec(N, -1) + rec(N, -2)))
      = 5 + (4 + (3 + rec(N, 1) + rec(N, 0)) + (2 + rec(N, 0) + 0) + (3 + (2 + rec(N, 0) + 0) + (1 + 0 + 0))
      = 5 + (4 + (3 + (N[1] + rec(N, 0) + rec(N, -1)) + (N[0] + rec(N, -1) + rec(N, -2))) + (2 + (N[0] + rec(N, -1) + rec(N, -2)) + 0) + (3 + (2 + (N[0] + rec(N, -1) + rec(N, -2)) + 0) + 1)
      = 5 + (4 + (3 + (2 + (N[0] + rec(N, -1) + rec(N, -2)) + 0) + (1 + 0 + 0)) + (2 + (1 + 0 + 0) + 0) + (3 + (2 + (1 + 0 + 0) + 0) + 1))
      = 5 + (4 + (3 + (2 + (1 + 0 + 0) + 0) + 1) + (2 + 1 + 0) + (3 + (2 + 1 + 0) + 1))
      = 5 + (4 + (3 + (2 + 1 + 0) + 1) + 3 + (3 + 3 + 1))
      = 5 + (4 + (3 + 3 + 1) + 3 + 7)
      = 5 + (4 + 7 + 10)
      = 5 + 21
      = 26

And as suggested above, the following code generates the entire expression that, when evaluated, equals 26. It can also be played with to generate step-by-step work.

#include <iostream>
#include <string>

using namespace std;

string rec(string * N, int max) {
    if (max < 0)
        return "0";

    auto a = rec(N, max - 1), b = rec(N, max - 2);

    return "(" + N[max] + " + " + a + " + " + b + ")";
}

int main() {
    const int max = 5;
    string N[] = { "1", "2", "3", "4", "5" };
    auto f = rec(N, max - 1);

    cout << f << endl; 
    return 0;
}

Upvotes: 5

Related Questions