2013 October 2,
Carleton College, Fall 2013, Prof. Joshua R. Davis,
In this assignment, you will implement recursion using iteration on a stack. Specifically, you will show that any singly or doubly recursive function can be implemented using an iterative function that simulates the recursive calls on a stack. This idea is fundamental to computer science, so you may have written code like this in a previous course. In this course, the purpose of the exercise is to develop a relationship between (some) recursive functions and push-down automata (which we're studying next).
Here is a classic recursive function:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
This function is singly recursive, meaning that it makes one recursive call to itself. All singly recursive functions follow this basic format:
In other words, all singly recursive functions can be implemented using the following meta-function. This meta-function uses four helper functions: criterion, base, pre, and post. The specific behavior of the meta-function depends on how the helper functions are defined. Copy the following code, and paste it into a Python file day06.py without alteration.
def recursive(x):
if criterion(x):
return base(x)
else:
prex = pre(x)
recx = recursive(prex)
return post(x, prex, recx)
A. What should the four helper functions be, so that the meta-function recursive computes the factorial, just as factorial does? Specifically: In day06.py, after the definition of recursive, define the four helper functions. Then write a short "demo section", to show that your code works.
The Euclidean algorithm, shown below, computes the greatest common divisor of two non-negative integers a and b that are not both zero. It is singly recursive. The algorithm naturally takes two inputs, not one; however, we can treat it as taking one input, if that input is a pair.
def euclidean(ab):
if ab[0] == 0:
return ab[1]
elif ab[1] == 0:
return ab[0]
else:
return euclidean([ab[1], ab[0] % ab[1]])
B. What should the four helper functions be, so that the meta-function recursive implements the Euclidean algorithm? Specifically: In day06.py, after the demo section for the factorial, redefine the four helper functions, and then write demo code showing that recursive now behaves exactly like euclidean. (By the way, you do not need to understand the Euclidean algorithm, to complete this exercise. You just need to recognize patterns in code.)
Recall from class (or CS 201, or Wikipedia) that a stack is a last-in-first-out data structure that supports these four operations:
isEmpty(): Returns True or False, indicating whether the stack is empty.push(x): Adds the object x to the top of the stack, and returns nothing.pop(): Removes the top item from the top of the stack, and returns it. If the stack is empty, then the behavior is undefined.In this next exercise, you will need a stack. If you like, you can implement your own stack class. Alternatively, as long as you promise not to tell your CS 201 professor, you can simply use a Python list, with these four code snippets standing in for the official stack operations:
mystack = []len(mystack) == 0mystack.append(x)x = mystack.pop()C. In day06.py, immediately after the code for recursive, write a meta-function iterative, that performs identically to recursive, but which doesn't use any recursion. Instead, your iterative meta-function should use iteration (looping) and a stack. The start of my solution is shown below. (By the way, my solution is 15 lines, excluding comments.) Then, augment the demo sections for factorials and the Euclidean algorithm, to demonstrate that your helper functions work with iterative exactly as they work with recursive. You should not need to alter the helper functions at all.
def iterative(x):
stack = []
stack.append([x])
while not len(stack) == 0:
Want a hint? .noitcnuf eht ot llac evisrucer ralucitrap taht rof ,selbairav lacol eht fo lla fo seulav eht serots hcihw ,tsil a si yrtne kcats hcaE .detelpmoc tey ton sah taht llac evisrucer a ot sdnopserroc kcats eht ni yrtne hcae ,si tahT .sllac evisrucer gnidnep eht fo lla serots kcats ehT
Tail recursion is a special kind of single recursion, in which the post-processing function post does no work, but simply returns the result of the recursive call. The function euclidean shown above is in tail-recursive form. The function factorial above is not tail-recursive, because it performs a multiplication after its recursive call.
D. Optional. In the file day06.py, immediately after the code for iterative, write a meta-function iterativeTail. It does not need to handle non-tail-recursive functions. For tail-recursive functions, it should perform identically to recursive and iterative. Like iterative it should use no recursion. In comparison to iterative, it should be highly optimized. (My solution is 4 lines, excluding comments.) Augment your demo section for the Euclidean algorithm to demonstrate that iterativeTail works just like euclidean when equipped with the Euclidean helper functions.
In addition to singly recursive functions, there are also doubly recursive functions, which call themselves twice. Here are two classic examples, that compute the Fibonacci numbers and the combinatorial coefficients "n choose k" (for any n ≥ 0 and any 0 ≤ k ≤ n).
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
def choose(nk):
if nk[0] == 0 or nk[1] == 0 or nk[0] == nk[1]:
return 1
else:
return choose([nk[0] - 1, nk[1]]) + choose([nk[0] - 1, nk[1] - 1])
Here is a meta-function that implements double recursion using double recursion. There is now a fifth helper function, mid, because some work may need to be done between the two recursive calls. Paste this code into your day06.py file, immediately after the code for iterative.
def recursive2(x):
if criterion(x):
return base(x)
else:
prex = pre(x)
recx = recursive2(prex)
midx = mid(x, prex, recx)
recx2 = recursive2(midx)
return post(x, prex, recx, midx, recx2)
E. What should the five helper functions be, so that the meta-function recursive2 behaves identically to fibonacci? Specifically: In day06.py, after the demo section for the Euclidean algorithm, define the five helper functions, and then write a demo section for them.
F. What should the five helper functions be, so that the meta-function recursive2 behaves identically to choose? Specifically: In day06.py, after the demo section for the Fibonacci numbers, define the five helper functions, and then write a demo section for them.
G. Optional. In day06.py, after the other meta-functions, write a meta-function iterative2, that performs identically to the meta-function recursive2, but which doesn't use any recursion. Instead, your iterative2 meta-function should use iteration and a stack. (By the way, my solution is 19 lines, excluding comments.) Then, augment the demo sections for Fibonacci numbers and combinatorial coefficients, to demonstrate that your helper functions work with iterative2 exactly as they work with recursive2.
To review, you should have a single Python file day06.py containing code in the following order. When the grader runs your program, the tests should execute, so that the grader can quickly ascertain whether they are working or not. Submit this file for grading by placing it in your handin folder on the COURSES file server.
recursive, iterative, and recursive2 (and optionally iterativeTail and iterative2).recursive and iterative.recursive and iterative (and optionally iterativeTail).recursive2 (and optionally iterative2).recursive2 (and optionally iterative2).There are also triply recursive functions, quadruply recursive functions, and so forth. There are also problems (such as parsing of expressions with operators of arbitrary arity) that lend themselves to recursive solutions where the number of recursive calls varies from one call to the next. All of these variations on recursion can be implemented using iteration on a single stack. As long as the work done in the helper functions is not too complicated, these recursive algorithms can be implemented on a push-down automaton.