Recursive Functions
Contents
Recursive Functions¶
In this section, we provide some additional recursive function examples.
For Loop vs recursion¶
Many students first thought about recursion is “I can’t use loops anymore!”. This may be true, but much of the knowledge you learned about loops can be transferred to recursion.
The below Python code completely a very simple loop. It loops over a range of numbers between a and b. It adds up all the numbers in the range using an accumulator named total. It uses a for loop to deal with the iteration variable i. Then it returns the final answer.
#The classic for loop
def count(a,b):
total=0
for i in range(a,b):
total=total+i
return total
print(count(0,10))
We could try to design a naturally recursive function to solve this problem. We could also try to use the iterative solution as our foundation. To match the iterative method as closely as possible, we start with a helper function. We need our iterator i and accumulator total. We add this as function input arguments.
;Count sum from a to b
;input-contract: (and (int? a) (int? b))
;output-contract: (int? (count a b))
(define (count a b)
(count_helper a b a 0)
)
Now we have both the “variables” we need. They are not “variables”, they are input arguments. They will accomplish the same goal. The iterator i starts at value a. Instead of writing i=a we assign it in the function call. We also want to start total=0. This can also be accomplished in the function call. This is why the body of the function as two extra inputs. In this call (count_helper a b a 0), the last two values are setting i=a and total=0.
Next, we need to add the base case. The original loop looks like for i in range(a,b):. It keeps going as long as a < b. That means it stops when \(a \ge b\). The opposite of the loop condition is our base case. We need to do (>= i b). If we wanted to be really strict in the opposite statement we could even literally write (not (< i b))).
What happens what the original loop exits? It executes return total. This becomes our base case return value. This gets us to (if (>= i b) total ...). We just need the recursive case.
The recursive case is determined by the body of the loop. We have one assignment in the loop, total=total+i. We also have one implicit assignment i=i+1 as part of the loop. Since each of these values has become part of our function inputs, we can just do the assignment by passing in a changed value to the recursive call. The body of the loop generates (count_helper a b (+ i 1) (+ total i)).
The full racket function and helper is given below. It will work the same way as the Python code.
;Count sum from a to b
;input-contract: (and (int? a) (int? b))
;output-contract: (int? (count a b))
(define (count a b)
(count_helper a b a 0)
)
(define (count_helper a b i total)
(if (>= i b);not in range
total;return total
(count_helper a b (+ i 1) (+ total i))
)
)
(count 0 10)
We can make code that uses helper functions cleaner by defining the helper within the function. This make the function a local value. It will only exist within the parent function. A simplified version of the code is given below.
;Count sum from a to b
;input-contract: (and (int? a) (int? b))
;output-contract: (int? (count2 a b))
(define (count2 a b)
(define (ch a b total)
(if (>= a b) total (ch (+ a 1) b (+ total a)))
)
(ch a b 0)
)
(count2 0 10)
Generate a Range¶
A common pattern in recursion is to build a list. One of the easiest lists to generate is just a sequence of numbers in order. In this example, we will generate a sequence of numbers from a to b by step c. This replicates the range function found in Python.
Whenever we are generating a list, we need to think about a few things.
What causes an empty list?
How will we generate the first element in a list?
How will we generate the rest of the list?
We can start by generating a list from a to 10 by 1. The empty list will be returned when \(a > 10\). Our first value is determined by a. The rest of our list is a sequence from a+1 to 10.
(define (range1 a)
(if (> a 10)
null
(cons a (range1 (+ a 1)))
)
)
(range1 4) ;'(4 5 6 7 8 9 10)
We can make the function stop at any number by replacing the constant 10 with an input. We change it to b. Remember, when you add an input, you need to add it everywhere.
(define (range2 a b)
(if (> a b)
null
(cons a (range2 (+ a 1) b))
)
)
(range2 4 12) ;'(4 5 6 7 8 9 10 11 12)
What if we want to change the step? We could increase by 2 or 3 at a time. We add a third input c to control the step.
;Generate a range of numbers
;input-contract: (and (int? a) (int? b) (int? c))
;output-contract: (list? (range a b c))
;Numbers from a to b by step c
(define (range a b c)
(if (> a b)
null
(cons a (range (+ a c) b c))))
(range 2 100 5)
We can now use this function to generate all kinds of lists easily.
(range 2 100 5)
;'(2 7 12 17 22 27 32 37 42 47 52 57 62 67 72 77 82 87 92 97)
Alternatively, we could have started by thinking about an iterative solution. The range code is implemented in Python below using a loop.
def myRange(a,b,c):
L=[]
while a <= b:
L.append(a)
a=a+c
return L
print(myRange(2,21,3))
We follow the steps outlined in the previous example to make a recursive version in Python.
def myRange2(a,b,c):
return myRange_helper(a,b,c,[])
def myRange_helper(a,b,c,L):
if not (a <= b):
return L
else:
return myRange_helper(a+c,b,c,L+[a])
print(myRange2(2,21,3))
This code is a little messy. It we loop at the code, we realize that the list could be built with cons on the return values. This leads to a cleaner definition. This code matches the Racket solution exceptionally well.
def myRange3(a,b,c):
if a > b:
return []
else:
return [a] + myRange3(a+c,b,c)
print(myRange3(2,21,3))
Trying to solve every problem by starting with a iterative solution is generally more work then solving recursively first. As you are getting experience with recursive design, this provides a secondary method to approach problems.
Filter a List¶
Another common pattern is to filter a list. We need to look through a list and pick some values to keep. If we want to keep a value, we can just cons it back into its original position. We can start with a function that creates copies. It doesn’t even look at the values, it just builds a copy of the list.
(define (copy L)
(if (null? L)
null
(cons (first L) (copy (rest L)))
)
)
(copy '(1 3 4 5 7 8));'(1 3 4 5 7 8)
To build a filter, we need to modify the copy pattern. We make three conditions. The empty list is handled the same way. We check if the first value has the property we want. In this case, we check if it is even. If the value is even, we add it back in place. If the value is not even, we just filter the rest and throw away the first value.
;Filtering
;Filter out all odd numbers
;input-contract: (list? L) and for all x in L (int? x)
;output-contract: (list? (filter L)) and for all x in (filter L) (even? x)
(define (filter L)
(cond
[(null? L) null]
[(even? (first L)) (cons (first L) (filter (rest L)))]
[else (filter (rest L))]
)
)
This pattern can be changed to work with any predicate. We just only cons the value back onto the list when our predicate returns true.
The following command generates a range, then filters it to only contain even numbers.
(filter (range 2 100 5))
;'(2 12 22 32 42 52 62 72 82 92)
Starts With¶
We stated earlier that we need to think about what to do with the first and rest of the list. Sometimes, we only care about one of these two things. If we want to know if a list starts with a certain value, we only care about the first. This question doesn’t require any information about the rest. That means we don’t need any recursion.
There are three possible cases.
If the list is empty, then it does not start with \(x\)
If the first value is \(x\), then it does start with \(x\)
If none of the above, then it does not start with \(x\)
We can implement this easily with a condition statement.
;Starts with x
;input-contract: (and (list? L) (int? x))
;output-contract: (bool? (startsWith x L))
;Returns true if list starts with value x
(define (startsWith x L)
(cond
[(null? L) #f]
[(= (first L) x) #t]
[else #f]
)
)
We can test the function on different lists to confirm it works.
(startsWith 0 '(0 1 1 1 0)) ;#t
(startsWith 1 '(1 0 0 1 0)) ;#t
(startsWith 0 '(1 0 0 1 0)) ;#f
(startsWith 1 '(0 1 1 1 0)) ;#f
Pattern¶
Finding patterns can require a significant amount of clever design. The basic three questions still remain.
What do we do with the empty list?
What do we need to know about the first value?
What do we need to know about the rest of the list?
The pattern we are looking for in this example is a binary number pattern. Specifically, a binary number where the bit flips ever digit. For example, \(101010\) or \(010101\). Every \(1\) is followed by a \(0\) and every \(0\) is followed by a \(1\). We never have two repeated digits with the same value.
What do we do with the empty list? It is often hard to decide if the empty list fits a pattern or not. One way to ask the question is “is there anything wrong with the list?”. In the case of the empty list, it cannot have any repeated digits. It has no digits. We can consider the empty list true.
Note
Often, the answer for the empty list is not obvious. Sometimes it helps to think about the recursion. What do you need returned for the rest of the code to work?
Next, we need to think about the first and rest of the list. We want the first and second values to be different. Specifically, either \(01\) or \(10\). That means if the first value is \(0\), then the rest of the list must start with 0. Further, the rest of the list must match the pattern.
If the first value is \(1\), then the rest of the list must start with 1 and meet the pattern.
There are two special cases that don’t meet this pattern well. If the list is just '(1) then the rest doesn’t start with anything. We special case out the single element lists.
The recursive case can be implemented with out logic. If (startsWith 1 L) then (and (startsWith 0 (rest L)) (pattern (rest L))). If the list starts with 1, then the rest of the list must start with 0 and follow the pattern.
;Pattern
;Looks for pattern 10101010... or 01010101...
;input-contract: (list? L) and for all x in L (int? x)
;output-contact: (bool? (pattern L))
(define (pattern L)
(cond
[(null? L) #t];Default
[(or (equal? L '(1)) (equal? L '(0))) #t] ;Special Cases
[(startsWith 1 L) (and (startsWith 0 (rest L)) (pattern (rest L)))]
[(startsWith 0 L) (and (startsWith 1 (rest L)) (pattern (rest L)))]
[else #f]
)
)
We can test this code on a variety of inputs to see if it works correctly.
(pattern '(1 0 1 0 1 0)) ;#t
(pattern '(0 1 0 1 0 1)) ;#t
(pattern '(0 1 0 1 1 0)) ;#f
(pattern '(1 0 1 1 0 1)) ;#f
(pattern '(1 1 1 1 1)) ;#f