Section 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.
Subsection 6.2.1 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.
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}\text{.}\) 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\text{.}\) At last, we use the SR() function to convert from Python notation to mathematical notation.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\text{,}\) and the recursive relation \(F_n = F_{n-1} + F_{n-2}\) for \(n > 1\text{.}\) This sequence is a cornerstone example in the study of recursion.
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 \(n\)th Fibonacci number by iterating and updating the values of two consecutive Fibonacci numbers in the sequence. Let’s calculate the third Fibonacci number.We go back to the previous method where we calculated the closed form
fib_sol and evaluate it now at \(n = 3\text{.}\)
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.
Subsection 6.2.2 Recursion with Binomial Coefficients
Binomial coefficients, denoted as \(\binom{n}{k}\text{,}\) 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.We can also explore the recursive nature of binomial coefficients by defining a function ourselves recursively.
This function implements the recursive formula \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\text{,}\) with base cases \(\binom{n}{0} = \binom{n}{n} = 1\text{.}\)
