Recursion

Subsection 2.4.4 Recursion

Recall that a sequence $\seq{a_n}{n}$ can be defined for all $n\in\NN_0$ by giving

an initial value $a_0$ and
🔗

🔗
a recurrence relation that for $k\ge 2$ gives $a_k$ as a formula in $a_{k-1}\text{.}$
🔗

🔗

Recurrence relations example of a more general concept called recursion, where a concept or process depends on a simpler version of itself.

🔗

In Python a recursive function is a function that calls itself. To assure termination we need to have a base case for which the function does not call itself.

🔗

We give examples of recurrence relations and their implementation with recursive functions in Python..

🔗

Example 2.4.4.1. Factorial.

Let the sequence $\seq{f_n}{n}$ be given by the recurrence relation $f_{n}=n\cdot f_{n-1}$ and the initial value $f_0=1\text{.}$

🔗

We compute $f_5\text{.}$

\begin{align*} f_5 \amp =5\cdot f_4 \\ \amp = 5\cdot(4\cdot f_3) \\ \amp = 5\cdot(4\cdot(3\cdot f_2)) \\ \amp = 5\cdot(4\cdot(3\cdot (2\cdot f_1))) \\ \amp = 5\cdot(4\cdot(3\cdot (2\cdot (1\cdot f_0)))) \\ \amp = 5\cdot(4\cdot(3\cdot (2\cdot (1\cdot 1)))) \\ \amp = 5\cdot(4\cdot(3\cdot (2\cdot 1))) \\ \amp = 5\cdot(4\cdot(3\cdot 2)) \\ \amp = 5\cdot(4\cdot6) \\ \amp = 5\cdot24 \\ \amp = 120 \end{align*}

We have computed $f_5=120$ using 4 multiplications.

🔗

We can directly transfer the definition of the recurrence relation into Python by letting a function call itself. Our Python function evaluates $f(n)$ for a non-negative integer $n$ recursively following the recurrence relation $f(n)=n\cdot f(n-1)$ and the initial value $f(0)=1\text{.}$

🔗

def f(n):
  if n==0: 
    return 1
  return n*f(n-1)

🔗

The function $f(n)$ can also be evaluated using a for loop.

🔗

def f(n):
  f = 1
  for n in range(1,n): 
    f=f*n
  return f

🔗

Example 2.4.4.2. Compound interest recursive.

Alice deposits $\$1000$ in an account that pays $5\%$ interest yearly and her grandmother transfers $\$100$ to the account every year right after the interest t has been paid.

🔗

The amount $A_t$ in Alice’s account $t$ years after her initial deposit is given by initial value

\begin{equation*} A_0 = 1000 \end{equation*}

and the recurrence relation

\begin{equation*} A_{t}=A_{t-1}+A_{t-1}\cdot 5\% +100=A_{t-1}\cdot 1.05+100. \end{equation*}

We can use the following Python function for recursively evaluating $A\text{.}$ When the input is a non-negative integer $t$ the function A returns the amount in Alice’s account after $t$ years.

🔗

def A(t):
  if t==0: 
    return 1000
  return A(t-1)*1.05+100

🔗

Example 2.4.4.3. Exponentiation recursive.

Let $b\in\RR$ and let the sequence $\seq{p_n}{n}$ be given by $p_n=b^n\text{.}$ Then $p_n$ satisfies the recurrence relation

\begin{equation*} p_n=b\cdot p_{n-1}. \end{equation*}

which together with the initial value $p_0=1$ uniquely defines $p_n\text{.}$ We formulate this in Python:

🔗

def p(b,n):
  if n==0: 
    return 1
  return b*p(b,n)

🔗

Example 2.4.4.4. Fast exponentiation recursive.

Let $b\in\RR$ and let the sequence $\seq{p_n}{n}$ be given by $p_n=b^n\text{.}$

🔗

Recall that by Theorem 0.1.5.1 for $n\in\NN_0$ there exits $q\in\NN_0$ and $r\in\set{0,1}$ such that $n=2\cdot q+r\text{.}$ Thus

\begin{equation*} b^n=b^{2\cdot q+r}=b^{q\cdot 2}\cdot b^r=\left(b^q\right)^2\cdot b^r. \end{equation*}

As in Theorem 0.1.5.1 we write $q=n\div 2$ and $r=n\bmod 2$ and get the recurrence relation

\begin{equation*} p_n=(p_q)^2 \cdot b^r= (p_{(n\div 2)})^2\cdot b^{(n\bmod 2)} \end{equation*}

In Python this is considerably more efficient than the function in Example 2.4.4.3.

🔗

def p(b,n):
  if n==0: 
    return 1
  q,r = divmod(n,2)
  return p(b,q)**2 * b**r

🔗

White Hat stands behind Cueball, who is sitting at a computer. White Hat: Why do you like functional programming so much? What does it actually get you? Cueball: Tail recursion is its own reward. — Figure 2.4.4.5. *Functional* by Randall Munroe (`https://xkcd.com/1270`). Functional programming combines the flexibility and power of abstract mathematics with the intuitive clarity of abstract mathematics.
🔗

🔗

Prev Top Next