How to make algorithm to calculate efficient (not exponential) recursive Fibonacci sequence?

Question

I’m studying recursion, and I wanted to find a way to make a recursive algorithm for efficient Fibonacci sequence, where the algorithm is not exponential. How will I save the value of subproblems?? I was thinking of using the vector and try to save the subproblems or whatever

unsigned long long fibonacci (unsigned long long n){
    int cont = n, unsigned long long fib[cont];

    if(n < 2)
        return n;
    else if(n == cont)
            return fib[cont];
    else
        fib[cont] = return fibonacci(n-1) + fibonacci(n-2);   
}

Answer 1

The solution is just what you proposed: save the values already calculated on a vector. This technique is known as memoization (or memoization).

Store the array of old values in a static variable, then you can save data between a function call and another:

#include <stdio.h>
#define MAX_DEPTH 512

unsigned long long fibonacci (unsigned long long n){
    static unsigned long long max_n = 1;
    static unsigned long long memo[MAX_DEPTH];

    memo[0] = 0;
    memo[1] = 1;

    if (n <= max_n)
        return memo[n];

    memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    max_n = n;

    return memo[n];
}

int main() {
    int i;
    for (i = 0; i < 10; i++)
        printf("%llu\n", fibonacci(i));
    return 0;
}

You can see that the function is recursive (fibonacci calls itself), but now you only calculate what has not yet been calculated. complexity is the same if you run with a repeat loop.