7. Describing functions by recursion

Describing $N\to N$ functions by recursion

Factorial

Factorial

The factorial function, $\boxed{n!}$, defined recursively is: ?

• Basis step: $f(0)=1$ and $f(1)=1$.
• Recursive step: If $n>1$ then $f(n)=f(n-1)\times n$.

Link to original

Fibonacci

Fibonacci function

Leonardo Fibonacci asked in 1202: Let’s start with a pair of rabbits that needs one month to mature, and assume that every month each pair produces a new pair that becomes productive after one month. How many new pairs are produced each month?

The Fibonacci function, defined recursively is:

• Basis step: $f(0)=1$ and $f(1)=1$.
• Recursive step: If $n>1$ then $f(n)=f(n-2)+f(n-1)$.

This generates a series of integers: $0,1,1,2,3,5,8,13,21,[...]$

Link to original