﻿ CS 254: Recursion

2014 April 21,

# CS 254: Recursion

Carleton College, Prof. Joshua R. Davis,

## Introduction

In this assignment, you will implement recursion using stacks. 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 studied it in a previous course such as CS 208 or CS 251. In this course, the purpose of the exercise is to develop a relationship between recursive functions, push-down automata, and eventually parse trees. CS 254 students fall into two camps:

• If you have already mastered this concept, then this assignment has little educational value for you. But at least the assignment won't take much time — half an hour?
• If you have not mastered this concept, then here is a chance to practice. It's better to practice now than during a job interview.

## 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 recursion.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 recursion.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 recursion.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 with 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 recursion.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 alter the helper functions at all.

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

Want a hint? .kcats a ni seulav eseht fo stes gnireffid erots tsum ew taht ,llac ot llac morf reffid seulav eseht esuaceb si tI .noitcnuf eht rof selbairav lacol rehto dna sretemarap eht fo seulav eht serots taht ,tsil a si kcats eht ni meti hcaE .)ti edisni llac evisrucer a yb detpurretni saw ti esuaceb( dehsinif ton tub detrats neeb sah taht llac evisrucer a ot sdnopserroc kcats eht ni meti hcae ,si tahT .sllac evisrucer gnidnep 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. In the file recursion.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 recursion.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 recursion.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 recursion.py, after the demo section for the Fibonacci numbers, define the five helper functions, and then write a demo section for them.

G. In recursion.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 recursion.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.