Fibonacci – Iterative and Recursive algorithms


Fibonacci series is defined as:
Fibonacci: f(0) = 0, f(1) = 1, f(n) = f(n – 1) + f(n – 2)
Write the iterative and recursive functions to give the nth Fibonacci number. Discuss on the efficiency on both the approaches

Possible Solution:
Iterative solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
int fib(int n) {
  if (n == 0) {
    return 0;
  }
  int a = 1
  int b = 1;
  for (int i = 3; i <= n; i++) {
    int c = a + b;
    a = b;
    b = c;
  }
  return b;
}
Recursive Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int fib(int n) {
  if (n == 0)
  {
    return 0;
  }
  else if (n == 1)
  {
    return 1;
  }
  else if (n > 1)
  {
    return fibo(n-1) + fibo(n-2); /* this line is dangerous, makes the algo exponential */
  }
  else
  {
    return –1; /* Error in input */
  }
}
The iterative code is much better as this completes in O(n). The recursive code is exponential in nature as we do not store the previous result of Fib(x) anywhere. E.g. While computing Fib(4), it has to compute Fib(3) and Fib(2) but again to compute Fib(5) it goes back to compute Fib(4) and Fib(3) though it ideally should have stored the previously computed value somewhere.
i.e. If we call, say, fib(5), we produce a call tree that calls the function on the same value many different times:
  1. fib(5)
  2. fib(4) + fib(3)
  3. (fib(3) + fib(2)) + (fib(2) + fib(1))
  4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
  5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
Let’s rewrite the recursive function using memorization of previous results.
Modified linear code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int fibTable[46]; /* 46th Fib number is the maximum that can be stored in an int */
int fib(int n) {
  if (n == 0)
  {
    return fibTable[0] = 0;
  }
  else if (n == 1)
  {
    return fibtable[1]=1;
  }
  else if (n > 1)
  {
    if(fibTable[n] !=0) return fibTable[n];
    return fibTable[n] = fibo(n-1) + fibo(n-2);
  }
}

0 comments:

Post a Comment