3.8 Fibonacci numbers

One of the well-known mathematical recursive functions is to compute the Fibonacci numbers. The Fibonacci numbers are the numbers in the following sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... By default, the first two Fibonacci numbers F(0) and F(1) are 0 and 1 respectively, and each other subsequent number is the sum of the previous two such that the recurrence relation is F(n) = F(n-1) + F(n-2).
One more off-topic is that, there are many order integer sequences similar to the Fibonacci numbers, such as the Lucas numbers.

Time Complexity
Assume without using Dynamic Programming (or say Memorization), for each recursive step two recursive function calls will be done, that means the time complexity is exponential to n, so the time complexity is O(2n)
Note that some results will be used repetitively, just imagine if it is computed in iterative way, then the time complexity should be in linear time, recursion with memorization helps to do the similar thing, so the time complexity can be reduced to O(n)

Pseudo Code

   if n < 0 then
       return "Negative n is invalid"
   else if n == 0 then
       return 0
   else if n == 1 then
       return 1
       return fibonacci(n-1) + fibonacci(n-2)
© The University of Hong Kong Algorithms Library - hkual@cs.hku.hk