Recursive Functions

$\newenvironment {prompt}{}{} \newcommand {\ungraded }[0]{} \newcommand {\todo }[0]{} \newcommand {\oiint }[0]{{\large \bigcirc }\kern -1.56em\iint } \newcommand {\mooculus }[0]{\textsf {\textbf {MOOC}\textnormal {\textsf {ULUS}}}} \newcommand {\npnoround }[0]{\nprounddigits {-1}} \newcommand {\npnoroundexp }[0]{\nproundexpdigits {-1}} \newcommand {\npunitcommand }[1]{\ensuremath {\mathrm {#1}}} \newcommand {\sagemath }[0]{\textsf {SageMath}} \newcommand {\surfaceColor }[0]{violet} \newcommand {\surfaceColorTwo }[0]{redyellow} \newcommand {\sliceColor }[0]{greenyellow} \newcommand {\vector }[1]{\left \langle #1\right \rangle } \newcommand {\sectionOutcomes }[0]{} \newcommand {\HyperFirstAtBeginDocument }[0]{\AtBeginDocument }$

formula of formulas

So far, our formulas have been arithmetic instructions involving domain numbers. We have also seen functions defined by repeating values. We can stretch the idea of repeating to recursive values. That is function values that depend on other function values.

Factorial

Domain is all whole numbers.
Range is all natural numbers.

$Factorial(n) = \begin {cases} 1 & n = 0 \\ 1 & n = 1 \\ n \cdot Factorial(n-1) & 1 < n \end {cases}$

The traditional symbol for the factorial function is !.

$0! = 1$
$1! = 1$
$n! = n \cdot (n-1) \cdot (n-2) \cdots 3 \cdot 2 \cdot 1$

Write these factorials in the standard place value notation.

$3! = \answer {6}$
$4! = \answer {24}$
$5! = \answer {120}$

The values of the factorial function depend on previous values of the factorial function.

Fibonacci

Domain is $\mathbb {N}$ .
Range is $\mathbb {N}$ .

$Fibonacci(n) = \begin {cases} 1 & n = 1 \\ 1 & n = 2 \\ Fibonacci(n-1) + Fibonacci(n-2) & 2 < n \end {cases}$

$Fibonacci(2) = Fibonacci(1) + Fibonacci(0) = 1 + 1 = 2$
$Fibonacci(3) = Fibonacci(2) + Fibonacci(1) = 2 + 1 = 3$
$Fibonacci(4) = Fibonacci(3) + Fibonacci(2) = 3 + 2 = 5$

Compute these values.

$Fibonacci(5) = \answer {8}$
$Fibonacci(6) = \answer {13}$
$Fibonacci(7) = \answer {21}$

The values of the Fibonacci function depend on previous values of the Fibonacci function.

Recursively defined functions mimic periodic functions. Both use “previous” values. Periodic functions repeat the “previous” values, while recursive functions use these “previous” values within more computation.

Equations such as

$Factorial(n) = n \cdot Factorial(n-1)$
$Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)$

are called functional equations. They define how function values relate to other function values.

ooooo=-=-=-=-=-=-=-=-=-=-=-=-=ooOoo=-=-=-=-=-=-=-=-=-=-=-=-=ooooo
more examples can be found by following this link
More Examples of Piecewise-Defined Functions