Base cases: , Recursive case: python def fib(n): if n == 0: return 0 if n == 1: return 1 return fib(n - 1) + fib(n - 2) Tracing fib(4): plaintext fib(4) = fib(3) + fib(2) fib(3) = fib(2) + fib(1) fib(2) = fib(1) + fib(0) fib(1) = 1 fib(0) = 0 Notice fib(2) is computed twice!
This is a problem with naive recursive Fibonacci. For large , you compute the same values many times. For now, this works for small inputs. You'll learn to fix this inefficiency later.