2013 April 12,

CS 254: Day 06

Carleton College, Spring 2013

Prof. Joshua R. Davis, , CMC 325, x4473

Introduction

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).

Hand in your four program files in your handin folder on the COURSES file server.

Singly recursive functions

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:

Test whether the input is a base case.
If the input is a base case, then return a special result.
If the input is not a base case:

Do some work, which I call "pre-processing".
Recursively call the function on the result of the pre-processing.
Do some more work, which I call "post-processing". It may depend on any quantity present in the function: the input, the pre-processing result, and/or the recursive result.
Return the result of the post-processing.

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.

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 implements the factorial? Specifically: Start a new Python file factorial.py. Paste the meta-function into the file, without altering it. In the file, define the four helper functions. At the end of the file, after all of the function definitions, add a "demo section", where you demonstrate that the meta-function computes factorials.

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: Start a new Python file euclidean.py. As in the previous exercise, paste the meta-function, define the helper functions, and add a demo section. (By the way, you do not need to understand the Euclidean algorithm, to complete this exercise. You just need to recognize patterns in code.)

Single recursion as iteration on a stack

Recall from CS 201 that a stack is a last-in-first-out data structure that supports these four operations:

creation: Makes a new, empty stack.
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) == 0
mystack.append(x)
x = mystack.pop()

C. Write a meta-function iterative, that performs identically to the meta-function recursive, but which doesn't use any recursion. Instead, your iterative meta-function should use iteration and a stack. The start of my solution is shown below. Paste your iterative meta-function into both factorial.py and euclidean.py, and augment their demo sections to demonstrate that your helper functions work with iterative exactly as they work with recursive. (By the way, my solution is 15 lines, excluding comments.)

def iterative(x):
    stack = []
    stack.append([x])
    while not len(stack) == 0:

Tail recursion

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.

D. Optional. 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. Paste your meta-function into euclidean.py and augment the demo section to demonstrate that it works. (By the way, my solution is 4 lines, excluding comments.)

Doubly recursive functions

Are we having fun yet? Yes, but not enough fun. 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".

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.

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 computes Fibonacci numbers? Specifically: Start a new Python file fibonacci.py, paste the meta-function, define the five helper functions, and add a demo section.

F. What should the five helper functions be, so that the meta-function recursive2 computes the combinatorial coefficients? Specifically: Start a new Python file choose.py, paste the meta-function, define the five helper functions, and add a demo section.

G. Optional. 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. Paste your iterative2 meta-function into both fibonacci.py and choose.py, and augment their demo sections to demonstrate that your helper functions work with iterative2 exactly as they work with recursive2. (By the way, my solution is 19 lines, excluding comments.)

Other recursive functions

There are also triply recursive functions, quadruply recursive functions, and so forth. There are also problems 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 variations on recursion can be implemented on a push-down automaton.