Recall the definition of the Fibonacci numbers: they are a sequence of integers in which every number after the first two (0 and 1) is the sum of the two preceding numbers. To arrive at the sequence, we can quickly recognize there's a pattern in place, where we are repeating a similar calculation multiple times with different numbers.

Time to reach into our toolbox-- this can readily be solved with recursion. At each recursive call, run the same calculation based off the same function for the prior elements. You can see the pseudo-code provided for how this can be accomplished.

xxxxxxxxxx

Routine: f(n)

Output: Fibonacci number at the nth place

​

Base case:

1. if n==0 return 0

2. if n==1 return 1

​

Recursive case:

1. temp1 = f(n-1)

2. temp2 = f(n-2)

3. return temp1+temp2