Recursive Function Problem

[BeginnerP]

Hi,I can't understand this code. For f(4), prints 4 4 7 4 11 4 7 4 4. For f(3), prints 4 7 4. Why program prints like this?

int f(int x) {  
if (x == 0) return 1;  
else if (x == 1) return 3;  
else  {   
printf("%d  ", f(x - 2) + f(x - 1));   
return f(x - 1) + f(x - 2);  
} 
} 
 
int main() {  
f(4); 
return 0;
} 

[tpb]

It's a modification of the Fibonacci sequence (starting 1 3 instead of 0 1). It's printing out it's intermediate results, but it's (stupidly) calling the functions both for printing the values and for the return. That's pretty senseless. Also, in the expression f(x-2)+f(x-1) it is undefined which call is executed first, and the code actually calls them in different orders for the printing and the return. So to make it sane, I feel it should be more like this.

#include <iostream>
#include <iomanip>
using namespace std;

int f(int x) {
    if (x == 0) {
        //cout << " 1 ";
        return 1;
    }
    else if (x == 1) {
        //cout << " 3 ";
        return 3;
    }
    else  {
        int n = f(x - 1);
        n += f(x - 2);
        cout << setw(2) << n << ' ';
        return n;
    }
}

int main() {
    for (int i = 0; i <= 8; i++) {
        cout << setw(2) << i << ": ";
        f(i);
        cout << '\n';
    }
}

I forgot the original was C:

#include <stdio.h>

int f(int x) {
    if (x == 0) {
        //printf(" 1 ");
        return 1;
    }
    else if (x == 1) {
        //printf(" 3 ");
        return 3;
    }
    else  {
        int n = f(x - 1);
        n += f(x - 2);
        printf("%2d ", n);
        return n;
    }
}

int main() {
    for (int i = 0; i <= 8; i++) {
        printf("%2d: ", i);
        f(i);
        putchar('\n');
    }
}

[icy1]

Might be better off storing it all in one structure and only print once at the end, or you'll risk duplicate printing. Not sure what your sequence is supposed to look like, but here is a C++ recursive fibonacci w/ vector storage:

#include <iostream>
#include <vector>

using namespace std;

// Recursively fill vector with fibonacci
//   i - positive integer
int fib(vector<int>& v, int i)
{
    if (i<=1) { return 1; }
    if (v[i]) { return v[i]; }
    
    return v[i] = fib(v, i-2) + fib(v, i-1);
}

int main() 
{
    int limit = 12;
    
    vector<int> v(limit+1); 
    v[0] = v[1] = 1;  // Important to seed first two.
    fib(v, limit);

    for(auto& k : v)
        cout << k << " ";
    cout << endl;
    
    return 0;
}

1 1 2 3 5 8 13 21 34 55 89 144 233 

The resulting vector stores an extra number for indexing convenience; e.g. requested 12 results in 0..12 . One optimization you'll notice here is that if the number was already calculated, it is returned. For example, subsequent calls of fib(v, limit); would be instantaneous if v[limit] was calculated.

How does it do this? The vector is value-initialized to all zeroes on line 20 since int is a primitive type. We then check calculated by comparing v[i] to 0 on line 11.