Fibonacci numbers are used as a very common example for teaching recursion.

fib 0 = 0 fib 1 = 1 fib n = fib (n-1) + fib (n-2)