↓ CSCE 221.509 | Fibonacci and Recursion

Natural numbers apparently don’t necessarily involve the number zero

Definition of Natural Numbers
	Base case: n=0
		n=0 is a natural number
	Successive case: n_{i+1} = n_i + 1
		if n_i is a natural number, then n_i + 1 is a natural number.

Fibonacci sequence

There was the rabbit Fibonacci sequence analogy

F(0) = 1
F(1) = 1
F(2) = F(1) + F(0)
F(3) = F(2) + F(1)
F(4) = F(3) + F(2)
F(n) = F(n-1) + F(n-2), for n > 1

Algorithm Fib(n)
	Input: n //rank of fib. number
	Output: actual fib. number

	if n < 2 then
		return 1;
	end if
	return F(n-1) + Fib(n-2)

Fib(5) = (Fib(4) + Fib(3)) = ((Fib(3) + Fib(2)) + (Fib(2) + Fib(1)))

Do the analysis to speed it up.

T(n)
T(0) = 1
T(1) = 1
T(n-1) + T(n-2)
So T(n) = T(n-1) + T(n-2) + 1
T(n) = 2F(n) - 1

Note: T(n-2) < T(n-1), for n >= 3

T(n) < T(n-1) + T(n-1) +1

T(n) < 2T(n-1) + 1

Note: T(n-1) < 2T(n-2) + 1

T(n) < 2^2 T(n-2) + 2 + 1

Note: T(n-2) < 2T(n-3) + 1

T(n) < 2^3T(n-3) + 2^2 + 2 + 1

…

T(n) < 2^k(n-k) + (2^{k-1} + ... + 2^2 + 2 + 1)

Side note: how to solve S(k) = (2^{k-1} + … + 2^2 + 2 + 1) 2S(k) = (2^k + ... + 2^3 + 2^2 + 2) 2S(k) - S(k) = 2^k + 2^{k-1} - 2^{k-1} + … + 2^2 - 2^2 + 2 - 2 + 1 So S(k) = 2^k + 1

Therefore

T(n) < 2^kT(n-k) + (2^k + 1) T(n) < 2^{n-1}T(1) + (2^{n-1} - 1) T(n) < 2^{n-1} + 2^{n-1} - 1 T(n) < 2^n - 1

Fibonacci 2

  1. Start with F(0) and F(1)
  2. Always keep the last two value, F(i-1) and F(i-2)
  3. Compute until F(i=n)

In this case, T(n) = n

This is called dynamic programming, when we save data that is frequently used.

How can we do better?

Closed form of F(n)

F(n) = \frac{(golden ratio)^n - (golden ratio conjugate)^n}{\sqrt{5}}

T(n) = 2*(the cost of the power function)

The actual T(n) for the recursive function is O((golden ratio)^n)

a^n = a*a*a*a*a* … *a Which would be O(n) and worse than the dynamic programming version

a^n = a^{n/2} * a^{n/2} if n is even a^n = a^{n/2} * a^{n/2} * a if n is odd