Fibonacci Number

Fibonacci numbers start 0, 1, and each next one is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, … Return fib(n). Write it as plain recursion. It gets slow near n = 30, and chapter 3 shows why.

Examples

Example 1

Input:  n = 2
Output: 1

Example 2

Input:  n = 10
Output: 55