Any function that calls itself is known as a recursive function. In most cases, recursion can be considered an alternative to iteration (loops). Instead of defining a loop structure, recursion defines a problem as a smaller problem until it reaches an end point. There are three requirements for a successful recursive function:
Base case: each function must have one or more base cases where the function does not make a recursive call to itself. Instead, the problem has reached its smallest point, and we can begin returning back the small solutions.
Recursive case: the function makes one (or more) calls to itself. The call must use a different argument to the function (or else we keep making the same recursive call over and over again!). Typically, the problem gets 1 smaller.
All possible recursive calls must be guaranteed to hit a base case. If you miss one, your program is susceptible to an infinite recursion bug!
Open numRecursion.py in this week’s directory:
$ cd ~/cs21/inclass/w11-recursion/
$ atom numRecursion.pyWe are going to write some iterative and recursive versions of the same function. Iterative versions use loops, recursive versions do not use loops, and instead contain calls to themselves but on a smaller problem. I have given you the code for an algorithm we have seen before - a for loop that sums all integers between 1 and n:
def sumN_iterative(n):
accum = 0
for i in range(1,n+1):
accum += i
return accumTogether, we will write a recursive function that accomplishes the same task.
Recall the iterative version (using a loop) of factorial that takes a positive int value, n, and returns the product of the first n integers. Try writing a recursive version of the factorial function. We will do a stack diagram of how Python interprets recursive functions. The key concept is that Python treats the recursive call the same as any function call - it places a new stack frame on top and begins executing the new function. Here is a walk through by Python Tutor.
NOTE: Python Tutor makes design choices that we disagree with. You should use the style we have in class (grow the stack upwards; draw all values outside the stack frame). However, Python tutor is a great tool for gaining more experience with understanding programs.
Open countdown.py. Explain the program to your neighbor. What is the recursive function doing? Can you identify the base vs recursive case? Are you sure that all recursive calls eventually hit the base case? Run the code in Python tutor.
For any recursive problem, think of three questions:
Next, we will work on recursive algorithms for strings. Open up stringRecursion.py and write two functions.
First, we will write a function that implements the isdigit() functionality of the string class. Our version will use recursion to examine each character in the string to verify if it is a digit (i.e., number between 0 and 9).
Take-home exercise: Write a function that checks if a word is a palindrome. A palindrome is any word that reads the same forward as backwards. Or, to put another, the second half is a mirror of the first half. For example, “hello” is not a palindrome, but “racecar” and “otto” are.
Try these problems out to test your understanding of recursion:
In Week 3, we wrote functions in class to double all the letters in a word using for loops. Can you write this as a recursive function? How about skipping every other letter?
From Lab 2, do Dashes as a recursive function. Then do Sum of Mathematical Series as a recursive function.
From Lab 3, do Leet Speak as a recursive function.
Next, we will work on recursive algorithms for strings. For example, we can construct a list of integers 1 through n using recursion. We will do this on the board.
An additional example of using lists can be taken from two weeks ago: binary search. Recursive functions can have more than one different recursive call within the function. For example, let us work out how we can recursively define binary search, which recursively calls binary search on one-half of the problem. The recursion is as follows:
def binarySearch(x, ls):
"""
A recursive implementation of binary search.
Parameters: x - the value to search for
ls - a list of values to search through (ls should be sorted)
Return: True if x is in ls
"""
if len(ls) == 0: #base case 1 - no values to search
return False
mid = len(ls)//2
if ls[mid] == x: #base case 2 - found the value x
return True
if x < ls[mid]: #recursive case 1 - x is in left half
return binarySearch(x,ls[0:mid]) #left half of ls (0 to mid-1)
else:
return binarySearch(x,ls[mid+1:]) #right half of ls (mid+1 to end)We will code our solution in binarySearch.py. We will do a more advanced version that does not require creating a new list every time we recurse. Instead, we will add parameters to keep track of low and high, just as we did with the iterative version. We will see the idea of using a helper function - a detailed function that does the recursion while the main binary search function abstracts details.
Recursion plays in important role in mathematics and graphical representations of seemingly complex objects. In sierpinksi.py, I have provided an example known as Sierpinski Triangle. You are not responsible for knowing how to do this, but it shows an example of the power of recursion. This is a triangle with 4 sub-triangles, each having exactly 1/2 the length on each edge. These sub-triangles are recursively defined to also have 4 sub-triangles, and so on.
Fractals, related to recursion, is a fascinating area of mathematics. It is an essential feature for computer graphics animation, and reflects real evolutionary patterns in biology. Here is a great documentary on the subject.