Question

Write a recursive algorithm to calculate the Fibonacci number

The Fibonacci number of an input value x is calculated as

fib(x) = fib(x-1) + fib(x-2);

Also it is known that fib(0) = 0 and fib(1) = 1

For example if x = 4 then ​fib(4) ​=   fib(3) ​           + fib(2)

= fib(2) ​   + fib(1) + fib(1)    + fib(0)

= fib(1) + fib(0) + fib(1)   + fib(1)   + fib(0)

= 1    ​   + 0    + 1    + 1 ​  + 0     = 3

Answer 1

Recursive algorithm of fibonacci series is as below.

algorithm fibonacci(num):

//checks if num is less than 1 then return 1
if num<=1 then
    return 1;

//if num is greater than 1 then make recursive call until num becomes 1.
else
   return fibonacci(n-1) + fibonacci(n-2)

end

Below is the implementation of recursive fibonacci series in c++ language.

#include <iostream>

using namespace std;

int fibonacci(int num) 
{ 
    if (num <= 1) 
        return num; 
    return fibonacci(num-1) + fibonacci(num-2); 
} 
  
int main () 
{ 
    cout << fibonacci(5); 
    
    return 0; 
}