6.2: Recursion

Recursion is a method where the solution to a problem depends on solutions to smaller instances of the same problem. This approach is extensively used in mathematics and computer science, especially in the computation of binomial coefficients, the evaluation of polynomials, and the generation of sequences.

Recursion in Sequences

A recursive sequence is defined by one or more base cases and a recursive step that relates each term to its predecessors.

Note

Use recursion to solve problems by breaking them down into similar steps. In programming, recursively defined functions often improve code readability.

Given a sequence defined by a recursive formula, we can ask Sage to find its closed form. Here, s is a function representing the sequence defined by recursion. The equation eqn defines the recursive relation \(s_n=s_{n-1}+2 \cdot s_{n-2}\). The rsolve() function is then used to find a closed-form solution to this recurrence, given the initial conditions \(s_0=2\) and \(s_1=7\). At last, we use the SR() function to convert from Python notation to mathematical notation.

from sympy import Function, rsolve
from sympy.abc import n
s = Function('s')
eqn = s(n) - s(n-1) - 2*s(n-2)
sol = rsolve(eqn, s(n), {s(0): 2, s(1): 7})
show(SR(sol))

$$/*<![CDATA[*/\newcommand{\Bold}[1]{\mathbf{#1}}3 \cdot 2^{n} - \left(-1\right)^{n}/*]]>*/$$

We can use the show() function to make the output visually more pleasing; you can try removing it and see how the output looks.

Similarly, the Fibonacci sequence is another example of a recursive sequence, defined by the base cases \(F_0=0\) and \(F_1=1\), and the recursive relation \(F_n=F_{n-1}+F_{n-2}\) for \(n>1\). This sequence is a cornerstone example in the study of recursion.

from sympy import Function, rsolve
from sympy.abc import n
F = Function('F')
fib_eqn = F(n) - F(n-1) - F(n-2)
fib_sol = rsolve(fib_eqn, F(n), {F(0): 0, F(1): 1})
show(SR(fib_sol))

$$/*<![CDATA[*/\newcommand{\Bold}[1]{\mathbf{#1}}\frac{1}{5} \, \sqrt{5} {\left(\frac{1}{2} \, \sqrt{5} + \frac{1}{2}\right)}^{n} - \frac{1}{5} \, \sqrt{5} {\left(-\frac{1}{2} \, \sqrt{5} + \frac{1}{2}\right)}^{n}/*]]>*/$$

The show() function is again used here to present the solution in a more accessible mathematical notation, illustrating the power of recursive functions to describe complex sequences with simple rules.

We can also write a function fib() to compute the nth Fibonacci number by iterating and updating the values of two consecutive Fibonacci numbers in the sequence. Let’s calculate the third Fibonacci number.

def fib(n):
    # assuming n is always an int
    if n < 2:
        return n
    else:
        # the initial terms F0 and F1
        U = 0; V = 1
        for k in range(2, n+1):
            W = U + V;
            U = V; V = W
        return V

# display the first 10 Fibonacci numbers
[fib(i) for i in range(10)]

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

We go back to the previous method where we calculated the closed form fib_sol and evaluate it now at \(n=3\).

from sympy import Function, rsolve, Symbol, simplify
n = Symbol('n')
F = Function('F')
fib_eqn = F(n) - F(n-1) - F(n-2)
fib_sol = rsolve(fib_eqn, F(n), {F(0): 0, F(1): 1})
# Evaluate the solution at n=3
fib3 = simplify(fib_sol.subs(n, 3))
show(SR(fib3))

$$/*<![CDATA[*/\newcommand{\Bold}[1]{\mathbf{#1}}2/*]]>*/$$

As we can see, we obtain the same number either by evaluating the closed form at \(n=3\) or by finding the third Fibonacci number directly by iteration.

Recursion with Binomial Coefficients

Binomial coefficients, denoted as \(\binom{n}{k}\), count the number of ways to choose \(k\) elements from an \(n\)-element set. They can be defined recursively. Sage can compute binomial coefficients using the binomial(n, k) function.

binomial(5, 3)

10

We can also explore the recursive nature of binomial coefficients by defining a function ourselves recursively.

def binomial_recursive(n, k):
    if k == 0 or k == n:
        return 1
    else:
        return binomial_recursive(n-1, k-1) + binomial_recursive(n-1, k)
binomial_recursive(5, 3)

10

This function implements the recursive formula \(\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}\), with base cases \(\binom{n}{0}=\binom{n}{n}=1\).