﻿ CS 254: Day 06

2013 October 2,

# CS 254: Day 06

Carleton College, Fall 2013, Prof. Joshua R. Davis,

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

## 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:

1. Test whether the input is a base case.
2. If the input is a base case, then return a special result.
3. If the input is not a base case:
1. Do some work, which I call "pre-processing".
2. Recursively call the function on the result of the pre-processing.
3. 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.
4. 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. 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.)

## Single recursion as iteration on a stack

Recall from class (or CS 201, or Wikipedia) that a stack is a last-in-first-out data structure that supports these four operations:

• constructor: 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. 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

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.

## Doubly recursive 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 ≤ kn).

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

## Conclusion

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.

1. Code for `recursive`, `iterative`, and `recursive2` (and optionally `iterativeTail` and `iterative2`).
2. Helper functions for factorials, and their demo section using `recursive` and `iterative`.
3. Helper functions for the Euclidean algorithm, and their demo section using `recursive` and `iterative` (and optionally `iterativeTail`).
4. Helper functions for Fibonacci numbers, and their demo section using `recursive2` (and optionally `iterative2`).
5. Helper functions for combinatorial coefficients, and their demo section using `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.