Recursion
Contents
5.2. Recursion#
Recursion is arguably the most powerful tool for a computer scientist. It is used throughout theory and practice. Unfortunately, it is one of the more difficult concepts to understand in computer science.
In this chapter we will examine recursion in the context of mathematics and computer science. We will use the principle of induction to make logical arguments and proofs involving recursive constructs and structures.
5.2.1. Recursive Definitions#
Definition (recursive definition)
A recursive definition of a set defines elements of the set in terms of other elements in the set.
A recursively-defined set is a set with a recursive definition. For example, the natural numbers are a recursively-defined set.
Recursively-defined natural numbers
Let \(\mathbb{N}\) be the set of numbers defined as follows:
\(0\) is in \(\mathbb{N}\).
If an integer \(n\) is in \(\mathbb{N}\) then \(n+1\) is in \(\mathbb{N}\).
Recursive definitions have two crucial parts.
The basis step or “base case”. It explicitly defines one more elements in the set.
The recursive step. It defines how to construct new elements of the set from other elements.
Sometimes the recursive step is called “production rules”, since they define rules on how to produce new elements of the set form old ones.
Since relations, functions, sequences are all themselves defined as certain kinds of sets, a recursive definition also applies to all of those discrete structures.
In fact, we have already seen this as recurrence relations in Section 3.2.2.
Recursively-defined sequences
Let \(a_0 = 1\) and \(a_1 = 3\). Define \(a_n = 2a_{n-1} + a_{n-2}\). Then, this sequence is:
The exclusion rule
Given a recursive definition of a set, it is possible that many different sets satisfy the definition.
Consider again the recursive definition of the natural numbers: \(0\) is a natural number and, if \(n\) is a natural number then so is \(n+1\).
The set \(\{0, 1, 1.5, 2, 2.5, 3, 3.5 \ldots\}\) satisfies this definition.
Therefore, to get a unique set the exclusion rule states that the set contains nothing other than those elements specified in the basis step and that are generated by applications of the recursive step.
Using the exclusion rule along with the previous recursive definition of the natural numbers, the natural numbers are uniquely the set:
We will always assume the exclusion rule, unless otherwise stated.
Recursive Summation
Let \((a_n)\) be a sequence.
Give a recursive definition for the summation
Recursive Summation
Basis:
Recursive step:
Recursive definitions can lead to some very abstract, yet very useful definitions.
For example, consider the set \(P\) of strings of balanced parentheses. We can define this set recursively.
\(() \in P\)
If \(w \in P\) then \(() w \in P\), \(w () \in P\), and \((w) \in P\).
Show that \((() ())\) is in \(P\) by repeatedly applying the recursive definition.
Show that \((() (\) is not in \(P\).
Solution
Let \(w_1 = ()\). \(w_1 \in P\). Then, we have \(w_2 = w_1 () \in P\). Then, we also have \(( w_2 ) \in P\). Therefore, \(( () () ) \in P\).
Each application of the recursive step always adds exactly 1 opening parenthesis and one closing parenthesis. The base case also has exactly 1 opening and 1 closed parenthesis. Therefore, it is impossible to have a string in \(P\) with different numbers of opening and closing parentheses. Thus, \((() ( \not\in P\)
As another example, consider all possible propositional formulas containing any combination of disjunction and conjunction of propositional variables.
Recursively-Defined Conjunctions and Disjunctions
Let \(F\) be the set of propositional formulas containing only conjunctions and disjunctions. A recursive definition of \(F\) is as follows.
Basis step: \(\mathbf{T}, \mathbf{F} \in F\). For any propositional variable \(p\), \(p \in F\).
Recursive step: If \(X\) and \(Y\) are formulas in \(F\) then:
Can you show that the formula \(p \land q \lor r \in F\)?
Solution
By the basis step, \(p \in F\), \(q \in F\), \(r \in F\).
From one application of the recursive step, \(p \land q \in F\).
From another application of the recursive step, \((p \land q) \lor r \in F\).
5.2.2. Recursive Functions and Algorithms#
In computer science, the most important recursive definition is that of a recursive algorithm. We have already seen recursive functions several times in this course.
The factorial function \(Fact(n)\) can be defined recursively as:
We can also define the Fibonacci function as the function which takes \(n\) as argument and returns the \(n\)th Fibonacci number:
Of course, either can be converted to recursive algorithms in the sense of computer science. That is, functions which call themselves. Below are two recursive Python functions for factorial and Fibonacci.
def Fact(n) :
if (n < 1) :
return 1
else :
return Fact(n-1) * n
print([Fact(i) for i in range(0,7)])
[1, 1, 2, 6, 24, 120, 720]
def Fib(n) :
if (n < 2) :
return n
else :
return Fib(n-1) + Fib(n-2)
print([Fib(i) for i in range(0,8)])
[0, 1, 1, 2, 3, 5, 8, 13]
Many other functions can also be defined recursively. Try one yourself.
Recursive Exponentiation
Write a Python function which recursively computes \(7^n\) for some \(n\).
Recursive Summation
def ExpSeven(n) :
if (n < 1) :
return 1
else :
return ExpSeven(n-1)*7
Another example of an algorithm which readily admits a recursive definition is the Euclidean Algorithm. Recall that the Euclidean algorithm computes a GCD between two integers by computing a a sequence of remainders until the remainder is 0.
This algorithm converts to a recursive algorithm as follows.
def Recursive_Euclid(a,b) :
if (a % b == 0) :
return b
else :
return Recursive_Euclid(b, a % b)
print(Recursive_Euclid(216, 264))
24
5.2.3. Proving Recursive Algorithms#
Recursive definitions and mathematical induction are naturally intertwined. For a recursive algorithm, we have a base case, then, further solutions are build up modifications of that base case.
This is exactly the intention of induction. We have a basis step that can be proved directly, then, we rely on the inductive hypothesis to guarantee the correctness for all \(n\).
Let us see how we can apply induction for a recursive algorithm.
Recursive Correctness via Induction
Consider the following function which computes \(x^n\) for some integer \(x\) and some non-negative integer \(n\).
def power(x, n) :
if (n == 0) :
return 1
else :
return x * power(x, n-1)
We will prove that this function correctly computed \(x^n\).
Proof:
Proceed by induction.
For the basis step, power(x,0) clearly returns \(x^0 = 1\) from the first if condition.
For the inductive step, assume that power(x,k) returns the correct result \(x^k\), for some \(k \geq 0\). We will show that power(x, k+1) returns the correct result.
By the definition of power we see that power(x,k+1) returns x * power(x, k). By the inductive hypothesis, power(x, k) \(= x^k\). Thus, we have power(x,k=1) \(= x \cdot x^k = x^{k+1}\).
Therefore, by mathematical induction, power(x,n) correctly computed \(x^n\) for all \(n \geq 0\).
5.2.4. Exercises#
Exercise 5.10
Give a recursive definition for the following sets.
\(\{10, 12, 14, 16, 18, 20, \ldots \}\)
\(\{3x \ |\ x \in \mathbb{Z}^+\}\)
\(\{\frac{1}{2}, \frac{1}{4}, \frac{1}{8}, \frac{1}{16}, \frac{1}{32}, \ldots \}\)
Solution to Exercise 5.10
\(a_0 = 10\), \(a_{n} = a_{n-1} + 2\)
\(a_0 = 3\), \(a_{n} = a_{n-1} + 3\)
\(a_0 = \frac{1}{2}\), \(a_{n} = \frac{1}{2}a_{n-1}\)
Exercise 5.11
Recall from Strings as Sequences that sequences of characters from an alphabet create strings.
For some alphabet \(\Sigma\), the set of all possible strings from characters in \(\Sigma\) is denoted by \(\Sigma^{*}\).
For example, if \(\Sigma = \{0,1\}\), then \(\Sigma^* = \{\lambda, 0, 1, 00, 01, 10, 11, 000, 001, \ldots \}\).
Let \(\Sigma = \{a,b\}\). Give a recursive definition for the set \(\Sigma^*\).
Solution to Exercise 5.11
\(\lambda \in \Sigma^*\)
If \(w \in \Sigma^*\) then \(aw, bw, wa, wb \in \Sigma^*\).
Exercise 5.12
Give a recursive definition of the integers \(\mathbb{Z}\). Use a base case of \(0 \in \mathbb{Z}\).
Solution to Exercise 5.12
\(0 \in \mathbb{Z}. x \in \mathbb{Z} \rightarrow x+1, -x \in \mathbb{Z}\).
Exercise 5.13
Write a recursive Python function which takes a parameter \(n\) and return the \(n\)th term of the following sequence, \(a_n\). The sequence \((a_n)\), starting at \(n=0\), is defined as:
Solution to Exercise 5.13
def f(n) :
if (n < 1) :
return 1;
else :
return f(n-1) + 4
Exercise 5.14
Define a closed-form formula for the sequence given in Exercise 5.13. Prove using induction that the Python program in the solution of Exercise 5.13 computes the correct formula.