Fibonacci sequence is the sequence of whole numbers 0,1, 1, 2, 3, 5, 8, ... which starts with 0 and 1, and where every number thereafter is equal to the sum of the previous two numbers.  The pseudocode for the program is –  Step 1: CALL the fib function and pass the argument ‘n’.  Step 2: CHECK if the number ‘n’ is less than 2. If true, return the number ‘n’.  Step 3: RETURN the summation of CALL to fib function with ‘n-1’ and ‘n-2’ parameters respectively.  The python implementation for the same is –  def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print('Fibonacci for n=8 is', fib(8))  The output of the program is “Fibonacci for n=8 is 21”.