Recursive Algorithm: Let T(n) be the time to compute r(n). Recursion tree shows that r(n) needs r(n-1), r(n-2),.., r(0). Therefore

T(n) = T(n-1)+T(n-2)+ +T(0) and T(0) =1 (*)

Prove by induction that the solution of equation (*) is T(n) = 2^n

Therefore recursion algorithm has running time T(n) = Q(2^n), which is too slow