Fibonacci using Recursion

Question

This is my idea of solving 'nth term of fibonacci series with least processing power'-

int fibo(int n, int a, int b){
    return (n>0) ? fibo(n-1, b, a+b) : a;
}

main(){
    printf("5th term of fibo is %d", fibo(5 - 1, 0, 1));
}

To print all the terms, till nth term,

int fibo(int n, int a, int b){
    printf("%d ", a);
    return (n>0)? fibo(n-1, b, a+b): a;
}

I showed this code to my university professor and as per her, this is a wrong approach to solve Fibonacci problem as this does not abstract the method. I should have the function to be called as fibo(n) and not fibo(n, 0, 1). This wasn't a satisfactory answer to me, so I thought of asking experts on SOF.

It has its own advantage over traditional methods of solving Fibonacci problems. The technique where we employ two parallel recursions to get nth term of Fibonacci (fibo(n-1) + fibo(n-2)) might be slow to give 100th term of the series whereas my technique will be lot faster even in the worst scenario.

To abstract it, I can use default parameters but it isn't the case with C. Although I can use something like -

int fibo(int n){return fiboN(n - 1, 0, 1);}
int fiboN(int n, int a, int b){return (n>0)? fiboN(n-1, b, a+b) : a;}

But will it be enough to abstract the whole idea? How should I convince others that the approach isn't wrong (although bit vague)?

(I know, this isn't sort of question that I should I ask on SOF but I just wanted to get advice from experts here.)

Answer 1

With the understanding that the base case in your recursion should be a rather than 0, this seems to me to be an excellent (although not optimal) solution. The recursion in that function is tail-recursion, so a good compiler will be able to avoid stack growth making the function O(1) soace and O(n) time (ignoring the rapid growth in the size of the numbers).

Your professor is correct that the caller should not have to deal with the correct initialisation. So you should provide an external wrapper which avoids the need to fill in the values.

int fibo(int n, int a, int b) {
    return n > 0 ? fibo(b, a + b) : a;
}
int fib(int n) { return fibo(n, 0, 1); }

However, it could also be useful to provide and document the more general interface, in case the caller actually wants to vary the initial values.

By the way, there is a faster computation technique, based on the recurrence

fib(a + b - 1) = f(a)f(b) + f(a - 1)f(b - 1)

Replacing b with b + 1 yields:

fib(a + b) = f(a)f(b + 1) + f(a - 1)f(b)

Together, those formulas let us compute:

fib(2n - 1) = fib(n + n - 1)
            = fib(n)² + fib(n - 1)²

fib(2n)     = fib(n + n)
            = fib(n)fib(n + 1) + fib(n - 1)fib(n)
            = fib(n)² + 2fib(n)fib(n - 1)

This allows the computation to be performed in O(log n) steps, with each step producing two consecutive values.

Answer 2

Your result will be 0, with your approaches. You just go in recursion, until n=0 and at that point return 0. But you have also to check when n==1 and you should return 1; Also you have values a and b and you do nothing with them.

i would suggest to look at the following recursive function, maybe it will help to fix yours:

int fibo(int n){
    if(n < 2){
        return n;
    }
    else 
    {
       return (fibo(n-1) + fibo(n-2));    
    }
}

It's a classical problem in studying recursion.

EDIT1: According to @Ely suggest, bellow is an optimized recursion, with memorization technique. When one value from the list is calculated, it will not be recalculated again as in first example, but it will be stored in the array and taken from that array whenever is required:

const int MAX_FIB_NUMBER = 10;

int storeCalculatedValues[MAX_FIB_NUMBER] = {0};

int fibo(int n){

    if(storeCalculatedValues[n] > 0)
    {
        return storeCalculatedValues[n];
    }

    if(n < 2){
        storeCalculatedValues[n] = n;
    }
    else 
    {
       storeCalculatedValues[n] = (fibo(n-1) + fibo(n-2));
    }
    return storeCalculatedValues[n];
}

Answer 3

Using recursion and with a goal of least processing power, an approach to solve fibonacci() is to have each call return 2 values. Maybe one via a return value and another via a int * parameter.

The usual idea with recursion is to have a a top level function perform a one-time preparation and check of parameters followed by a local helper function written in a lean fashion.

---

The below follows OP's idea of a int fibo(int n) and a helper one int fiboN(int n, additional parameters)

The recursion depth is O(n) and the memory usage is also O(n).

static int fib1h(int n, int *previous) {
  if (n < 2) {
    *previous = n-1;
    return n;
  }
  int t;
  int sum = fib1h(n-1, &t);
  *previous = sum;
  return sum + t;
}

int fibo1(int n) {
  assert(n >= 0); // Handle negatives in some fashion
  int t;
  return fib1h(n, &t);
}

Answer 4

#include <stdio.h>
int fibo(int n);//declaring the function.

int main()
{
    int m;
    printf("Enter the number of terms you wanna:\n");
    scanf("%i", &m);
    fibo(m);
    for(int i=0;i<m;i++){
        printf("%i,",fibo(i)); /*calling the function with the help of loop to get all terms */
    }
    return 0;
}

int fibo(int n)
{ 
    if(n==0){
        return 0;
    }
    if(n==1){
        return 1;
    }

    if (n > 1)
    {
        int nextTerm;
        nextTerm = fibo(n - 2) + fibo(n - 1); /*recursive case,function calling itself.*/
         return nextTerm;
    }
}

Answer 5

solving 'nth term of fibonacci series with least processing power'

I probably do not need to explain to you the recurrence relation of a Fibonacci number. Though your professor have given you a good hint.

Abstract away details. She is right. If you want the nth Fibonacci number it suffices to merely tell the program just that: Fibonacci(n)

Since you aim for least processing power your professor's hint is also suitable for a technique called memoization, which basically means if you calculated the nth Fibonacci number once, just reuse the result; no need to redo a calculation. In the article you find an example for the factorial number.

For this you may want to consider a data structure in which you store the nth Fibonacci number; if that memory has already a Fibonacci number just retrieve it, otherwise store the calculated Fibonacci number in it.

By the way, didactically not helpful, but interesting: There exists also a closed form expression for the nth Fibonacci number.

This wasn't a satisfactory answer to me, so I thought of asking experts on SOF.

"Uh, you do not consider your professor an expert?" was my first thought.

Answer 6

As a side note, you can do the fibonacci problem pretty much without recursion, making it the fastest I know approach. The code is in java though:

public int fibFor() {
    int sum = 0;
    int left = 0;
    int right = 1;
    for (int i = 2; i <= n; i++) {
        sum = left + right;
        left = right;
        right = sum;
    }
    return sum;
}

Answer 7

Although @rici 's answer is mostly satisfactory but I just wanted to share what I learnt solving this problem. So here's my understanding on finding fibonacci using recursion-

• The traditional implementation fibo(n) { return (n < 2) n : fibo(n-1) + fibo(n-2);} is a lot inefficient in terms of time and space requirements both. This unnecessarily builds stack. It requires O(n) Stack space and O(rⁿ) time, where r = (√5 + 1)/2.
• With memoization technique as suggested in @Simion 's answer, we just create a permanent stack instead of dynamic stack created by compiler at run time. So memory requirement remains same but time complexity reduces in amortized way. But is not helpful if we require to use it only the once.
• The Approach I suggested in my question requires O(1) space and O(n) time. Time requirement can also be reduced here using same memoization technique in amortized way.
• From @rici 's post, fib(2n) = fib(n)² + 2fib(n)fib(n - 1), as he suggests the time complexity reduces to O(log n) and I suppose, the stack growth is still O(n).

So my conclusion is, if I did proper research, time complexity and space requirement both cannot be reduced simultaneously using recursion computation. To achieve both, the alternatives could be using iteration, Matrix exponentiation or fast doubling.