Chapter 11
RECURSION
Chapter Goals
• To learn to “think recursively”
• To be able to use recursive helper functions
• To understand the relationship between recursion and iteration
• To understand when the use of recursion affects the efficiency of an
algorithm
4/15/2025 1
• To analyze problems that are much easier to solve by recursion than
by iteration
• To process data with recursive structures using mutual recursion
Contents
• Triangle Numbers Revisited
• Problem Solving: Thinking Recursively
• Recursive Helper Functions
• The Efficiency of Recursion
• Permutations
• Backtracking
4/15/2025 Page 2
• Mutual Recursion
11.1 Triangle Numbers Revisited
• Triangle shape of side length 4:
[]
[][]
[][][]
[][][][]
• Will use recursion to compute the area of a triangle of width n ,
assuming each [] square has an area of 1
• Also called the nth triangle number
• The third triangle number is 6, the fourth is 10
4/15/2025 Page 3
Handling Triangle of Width 1
• The triangle consists of a single square
• Its area is 1
• Take care of this case first:
def triangleArea(sideLength) :
if sideLength == 1 :
return 1
. . .
Handling The General Case
• Assume we know the area of the smaller, colored
triangle:
4/15/2025 Page 4
[]
[][]
[][][]
[][][][]
• Area of larger triangle can be calculated as
area = smallerArea + sideLength
• To get the area of the smaller triangle
• Call the triangleArea() function:
smallerSideLength = sideLength - 1
smallerArea =
triangleArea(smallerSideLength)
4/15/2025 Page 5
Computing the Area of a Triangle With Width 4
•triangleArea() function makes a smaller triangle of width 3
• It calls triangleArea() on that triangle
• That function makes a smaller triangle of width 2
• It calls triangleArea() on that triangle
• That function makes a smaller triangle of width 1
• It calls triangleArea() on that triangle
• That function returns 1
4/15/2025 Page 6
• The function returns smallerArea + sideLength = 1 + 2
=3
• The function returns smallerArea + sideLength = 3 + 3
=6
• The function returns smallerArea + sideLength = 6 + 4
= 10
Recursive Computation
• A recursive computation solves a problem by using the solution to
the same problem with simpler inputs
• Call pattern of a recursive function is complicated
4/15/2025 Page 7
• Key: Don’t think about it
4/15/2025 Page 8
Successful Recursion
• Every recursive call must simplify the computation in
some way
• There must be special cases to handle the simplest
computations directly
4/15/2025 Page 9
Other Ways to Compute Triangle
Numbers
• The area of a triangle equals the sum:
1 + 2 + 3 + ... + sideLength
• Using a simple loop:
area = 0; for i in range (1,
(sideLength+1), 1) : area = area +
i
• Using math:
1 + 2 + ... + n = n × (n + 1)/2
=> n * (n + 1) / 2
4/15/2025 Page 10
[Link]
4/15/2025 Page 11
4/15/2025 Page 12
Special Topic 11.1
• An Object-Oriented version of the triangles program
class Triangle def _ _init_ _
(self, sideLength) :
self._sideLength = sideLength
def getArea(self) :
if self._sideLength == 1 :
return 1
. . .
• General case: compute the area of the larger triangle as
smallerArea + self._sideLength.
• To get the smaller area:
smallerTriangle = Triangle(self._sideLength
- 1) smallerArea =
[Link]() area =
smallerArea + self._sideLength
4/15/2025 Page 13
Common Error 11.1
• Infinite recursion:
• A function calling itself over and over with no end in sight.
• The computer needs some amount of memory for bookkeeping
during each call.
• After some number of calls, all memory that is available for this
purpose is exhausted.
• Your program shuts down and reports a “stack overflow”.
• Causes:
• The arguments don’t get simpler or because a special terminating
case is missing.
4/15/2025 Page 14
Thinking Recursively
• Problem: Test whether a sentence is a
palindrome
• Palindrome: A string that is equal to itself
when you reverse all characters
• A man, a plan, a canal – Panama!
• Go hang a salami, I’m a lasagna hog
• Madam, I’m Adam
Implement IsPalindrome() Function
## Tests whether a string is a palindrome.
# @param text a string that is being checked
# @return True if text is a palindrome, False
otherwise
# def
4/15/2025 Page 15
isPalindrome(text) :
. . .
Thinking Recursively: Step 1
• Consider various ways to simplify inputs.
• Several possibilities:
• Remove the first character
• Remove the last character
• Remove both the first and last characters
• Remove a character from the middle
• Cut the string into two halves
4/15/2025 Page 16
Thinking Recursively: Step 2 (1)
• Combine solutions with simpler inputs into a solution of the original
problem.
• Most promising simplification: Remove both first and last
characters.
• “adam, I’m Ada”is a palindrome too!
• Thus, a word is a palindrome if
• The first and last letters match, and
• Word obtained by removing the first and last letters is a palindrome
Thinking Recursively: Step 2 (2)
• What if first or last character is not a letter?
Ignore it
4/15/2025 Page 17
• If the first and last characters are letters, check whether they match;
if so, remove both and test shorter string
• If last character isn’t a letter, remove it and test shorter string
• If first character isn’t a letter, remove it and test shorter string
4/15/2025 Page 18
Thinking Recursively: Step 3
• Find solutions to the simplest inputs.
• Strings with two characters
• No special case required; step two still applies
• Strings with a single character
• They are palindromes
• The empty string
• It is a palindrome
4/15/2025 Page 19
Thinking Recursively: Step 4 (1)
• Implement the solution by combining the simple cases and the
reduction step.
def isPalindrome(text) :
length = len(text)
# Separate case for shortest strings.
if length <= 1 :
return True
else :
# Get first and last characters, converted to
# lowercase. first =
text[0].lower() last =
text[length - 1].lower()
4/15/2025 Page 20
Continued
Thinking Recursively: Step 4 (2)
# Non base case if [Link]()
and [Link]() :
# Both are letters.
if first == last :
# Remove both first and last
character. shorter = text[1 :
length - 1] return
isPalindrome(shorter)
else :
return False
elif not [Link]() :
# Remove last
4/15/2025 Page 21
shorter = text[0 : length - 1]
return isPalindrome(shorter)
else :
# Remove first character.
shorter = text[1 : length]
return isPalindrome(shorter)
Recursive Helper functions
• Sometimes it is easier to find a recursive solution if you make a slight
change to the original problem.
• Consider the palindrome test of previous section.
• It is a bit inefficient to construct new string objects in every step.
4/15/2025 Page 22
Substring Palindromes (1)
• Rather than testing whether the sentence is a palindrome, check
whether a substring is a palindrome:
## Recursively tests whether a substring is
# a palindrome.
# @param text a string that is being checked
# @param start the index of the first character of the
substring
# @param end the index of the last character of the
substring # @return True if the substring is a
palindrome
# def substringIsPalindrome(text, start,
end) :
4/15/2025 Page 23
Substring Palindromes (2)
• Then, simply call the helper function with positions that test the entire
string:
def isPalindrome(text) :
return substringIsPalindrome(text, 0, len(text)
– 1)
4/15/2025 Page 24
Recursive Helper function
def substringIsPalindrome(text, start, end) :
# Separate case for substrings of length 0 and 1.
if start >= end :
return True
else :
# Get first and last characters, converted to
lowercase.
first = text[start].lower()
last = text[end].lower()
Continued
Recursive Helper Function
if [Link]() and [Link]() :
if first == last :
# Test substring that doesn’t contain the
4/15/2025 Page 25
matching
# letters. return
substringIsPalindrome
(text, start + 1, end - 1)
else :
return False
elif not [Link]() :
# Test substring that doesn’t contain the last
character.
return substringIsPalindrome(text, start, end - 1)
else :
# Test substring that doesn’t contain the first
# character. return
substringIsPalindrome(text, start + 1, end)
4/15/2025 Page 26
11.4 The Efficiency of Recursion
• Fibonacci sequence:
4/15/2025 Page 27
Sequence of numbers defined
by f1 = 1 f2 = 1
4/15/2025 Page 28
fn = fn-1 + fn-2
4/15/2025 Page 29
• First ten terms:
4/15/2025 Page 30
1, 1, 2, 3, 5, 8, 13, 21, 34, 55
4/15/2025 Page 31
[Link]
4/15/2025 Page 32
Efficiency of Recursion
• Recursive implementation of fib() is
straightforward.
• Watch the output closely as you run the test
program.
• First few calls to fib() are quite fast.
• For larger values, the program pauses an amazingly
long time between outputs.
• To find out the problem, let’s insert trace messages.
4/15/2025 Page 33
[Link]: 1
4/15/2025 Page 34
[Link]: 2
4/15/2025 Page 35
Call Pattern of Recursive Fib()
Function
4/15/2025 Page 36
4/15/2025 Page 37
Efficiency of Recursion
• The function takes so long because it computes the same values over
and over.
• Computation of fib(6) calls fib(3) three times.
• Imitate the pencil-and-paper process to avoid computing the values
more than once.
4/15/2025 Page 38
Efficiency of Recursion
• Occasionally, a recursive solution runs much slower
than its iterative counterpart.
• In most cases, the recursive solution is only slightly
slower.
• The iterative isPalindrome() performs only
slightly better than recursive solution.
• Each recursive function call takes a certain amount
of processor time
[Link] (1)
4/15/2025 Page 39
4/15/2025 Page 40
4/15/2025 Page 41
[Link] (2)
4/15/2025 Page 42
Efficiency of Recursion
• Smart compilers can avoid recursive function calls if they follow simple
patterns.
• Most compilers don’t do that
• In many cases, a recursive solution is easier to understand and
implement correctly than an iterative solution .
• ‘To iterate is human, to recurse divine.’ - L. Peter Deutsch
Iterative IsPalindrome() Function
def
isPalindrome(text)
: start = 0 end =
len(text) - 1
while start <
4/15/2025 Page 43
end :
first = text[start].lower() last =
text[end].lower() if
[Link]() and
[Link]() :
# Both are letters.
if first == last :
start = start + 1
end = end - 1
else :
return False
if not [Link]()
end = end - 1
11.5 Permutations
• Design a class that will list all permutations of string, where a
permutation is a rearrangement of the letters
4/15/2025 Page 44
• The string "eat" has six permutations:
• "eat"
• "eta"
• "aet"
• "ate"
• "tea"
• "tae"
Generate All Permutations (1)
• Generate all permutations that start with 'e', then 'a', then 't'
• The string "eat" has six permutations:
• "eat"
• "eta"
• "aet"
4/15/2025 Page 45
• "ate"
• "tea"
• "tae"
Generate All Permutations (2)
• Generate all permutations that start with 'e', then 'a', then 't'
• To generate permutations starting with 'e', we need to find all
permutations of "at"
• This is the same problem with simpler inputs
• Use recursion
4/15/2025 Page 46
Implementing Permutations() Function
• Loop through all positions in the word to be
permuted
• For each of them, compute the shorter word obtained
by removing the ith letter:
shorter = word[ : i] + word[i + 1 : ]
• Compute the permutations of the shorter word:
shorterPermutations = permutations(shorter)
4/15/2025 Page 47
Implementing Permutations()
Function
• Add the removed letter to the front of all
permutations of the shorter word:
for s in shorterPermutations :
[Link](word[i] + s)
• Special case for the simplest string, the empty string,
which has a single permutation - itself
4/15/2025 Page 48
[Link] (1)
4/15/2025 Page 49
[Link] (2)
4/15/2025 Page 50
4/15/2025 Page 51
Backtracking
• Backtracking examines partial solutions, abandoning unsuitable
ones and returning to consider other candidates
• Can be used to
• solve crossword puzzles
• escape from mazes
• find solutions to systems that are constrained by rules
Backtracking Characteristic Properties
1. A procedure to examine a partial solution and determine whether to:
I. accept it as an actual solution or,
4/15/2025 Page 52
II. abandon it (because it either violates some rules or can never lead
to a valid solution)
2. A procedure to extend a partial solution, generating one or more
solutions that come closer to the goal
Recursive Backtracking Algorithm
Solve(partialSolution)
Examine(partialSolution).
If accepted
Add partialSolution to the list of solutions.
Else if not abandoned
For each p in extend(partialSolution)
Solve(p)
4/15/2025 Page 53
Eight Queens Problem
• Problem: position eight queens on a chess board so that none
of them attacks another according to the rules of chess
• A solution:
4/15/2025 Page 54
Eight Queens Problem
• Easy to examine a partial solution:
• If two queens attack one another, reject it
• Otherwise, if it has eight queens, accept it
4/15/2025 Page 55
• Otherwise, continue
• Easy to extend a partial solution:
• Add another queen on an empty square
• Systematic extensions:
• Place first queen on row 1
• Place the next on row 2
• Etc.
Function: Examine()
def examine(partialSolution) :
for i in range(0, len(partialSolution)) :
for j in range(i + 1,
len(partialSolution)) :
4/15/2025 Page 56
if attacks(partialSolution[i],
partialSolution[j]) :
return ABANDON
if len(partialSolution) == NQUEENS :
return ACCEPT
else :
return CONTINUE
Function: Extend()
def extend(partialSolution) :
results = []
row = len(partialSolution) + 1
for column in "abcdefgh" :
newSolution = list(partialSolution)
[Link](column + str(row))
[Link](newSolution)
return results
4/15/2025 Page 57
Diagonal Attack
• To determine whether two queens attack each other diagonally:
• Check whether slope is ±1
(row2 – row1)/(column2 – column1) =
±1 row2 – row1 = ±(column2 –
column1) row2 – row1| = |column2 –
column1|
Backtracking in the Four Queens Problem (1)
4/15/2025 Page 58
4/15/2025 Page 59
Backtracking in the Four Queens Problem (2)
• Starting with a blank board, four partial solutions with a queen in row 1
• When the queen is in column 1, four partial solutions with a queen in
row 2
• Two are abandoned immediately
• Other two lead to partial solutions with three queens and , all
but one of which are abandoned
• One partial solution is extended to four queens, but all of those are
abandoned as well
4/15/2025 Page 60
[Link]
4/15/2025 Page 61
4/15/2025 Page 62
4/15/2025 Page 63
[Link]
4/15/2025 Page 64
[Link]
11.7 Mutual Recursion
• Problem: Compute the value of arithmetic expressions such as:
4/15/2025 Page 65
3+4*5
(3 + 4) * 5
1 - (2 - (3 - (4 - 5)))
• Computing the expression is complicated
• * and / bind more strongly than + and –
• Parentheses can be used to group sub-expressions
Syntax Diagrams for Evaluating an Expression
4/15/2025 Page 66
4/15/2025 Page 67
Mutual Recursion
• An expression can be broken down into a sequence of terms,
separated by + or –
• Each term is broken down into a sequence of factors,
separated by * or /
• Each factor is either a parenthesized expression or a number
• The syntax trees represent which operations should be carried
out first
4/15/2025 Page 68
Syntax Trees for Two Expressions
4/15/2025 Page 69
Mutual Recursion
• In a mutual recursion, a set of cooperating functions calls each other
repeatedly
• To compute the value of an expression, implement 3 functions that call
each other recursively:
• expression()
• term()
• factor()
4/15/2025 Page 70
Function:
Expression()
def expression(tokens) :
value = term(tokens) done =
False while not done and
len(tokens) > 0 : next =
tokens[0] if next == "+" or next
== "-" :
[Link](0) # Discard "+" or
"-" value2 = term(tokens) if
next == "+" :
value = value + value2
else : value = value -
value2
else :
done = True
4/15/2025 Page 71
Function:
return value
Term()
• The term() function calls factor() in the same way,
multiplying or dividing the factor values
def term(tokens) : value =
factor(tokens) done = False
while not done and len(tokens)
> 0: next = tokens[0] if next
== "*" or next == "/" :
[Link](0) value2 =
factor(tokens) if next == "*" :
value = value * value2
else :
value = value / value2
4/15/2025 Page 72
Function:
else :
done = True
return value
Factor()
4/15/2025 Page 73
Function:
def factor(tokens) :
next =
[Link](0) if
next == "(" :
value = expression(tokens)
[Link](0) # Discard ")"
else :
value = next
return value
4/15/2025 Page 74
Trace (3 + 4) * 5
To see the mutual recursion clearly, trace through the expression (3+4)*5:
• expression() calls term()
• term() calls factor()
• factor() consumes the ( input
• factor() calls expression()
• expression() returns eventually with the value of 7,
having consumed 3 + 4. This is the recursive call.
• factor() consumes the ) input
• factor() returns 7
4/15/2025 Page 75
• term() consumes the inputs * and 5 and returns 35
• expression() returns 35
4/15/2025 Page 76
[Link]
[Link] (1)
4/15/2025 Page 77
4/15/2025 Page 78
[Link]
4/15/2025 Page 79
[Link]
4/15/2025 Page 80
[Link]
4/15/2025 Page 81
Summary
• Understand the control flow in a recursive computation.
• A recursive computation solves a problem by using the solution
to the same problem with simpler inputs.
• For a recursion to terminate, there must be special cases for
the simplest values.
• Design a recursive solution to a problem.
4/15/2025 Page 82
Summary
• Identify recursive helper functions for solving a problem.
• Sometimes it is easier to find a recursive solution if you make a
slight change to the original problem.
• Contrast the efficiency of recursive and non-recursive algorithms.
• Occasionally, a recursive solution runs much slower than its
iterative counterpart. However, in most cases, the recursive
solution is only slightly slower.
4/15/2025 Page 83
Summary
• In many cases, a recursive solution is easier to understand and
implement correctly than an iterative solution.
• Review a complex recursion example that cannot be solved with
a simple loop.
• The permutations of a string can be obtained more naturally
through recursion than with a loop.
4/15/2025 Page 84
Summary
• Use backtracking to solve problems that require trying out
multiple paths.
• Backtracking examines partial solutions, abandoning unsuitable
ones and returning to consider other candidates.
• Recognize the phenomenon of mutual recursion in an expression
evaluator.
4/15/2025 Page 85
Summary
• In a mutual recursion, cooperating functions or methods call
each other repeatedly.
4/15/2025 Page 86