2024 April 8,
Spring 2024, Carleton College, Joshua R. Davis
A push-down automaton is essentially an NFA equipped with a stack. It's a stepping stone between the simplest machines that we study (DFAs, NFAs) and the most sophisticated machines (Turing machines). But it's an important stepping stone, because stacks are crucial to how computer programs are parsed and interpreted.
This tutorial gives one example of how stacks appear in programming: as call stacks for recursive (and non-recursive) functions. In this tutorial, you show that any once- or twice-recursive function can be implemented using an iterative function that simulates the recursive calls on a stack. In my experience, CS 254 students fall into two camps:
You are asked to submit a single Python file with your solutions to problems A-F below. You are not asked to solve problem G (although it's good practice too).
Here is a classic recursive function in Python:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
This function is once-recursive, meaning that it makes one recursive call to itself. All once-recursive functions follow this basic format:
In other words, all once-recursive functions can be implemented using the following meta-function recursive. 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 demonstration, 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. (You don't actually need to understand how it works.) It is once-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.
Recall from CS 201 that a stack is a last-in-first-out data structure that supports these four operations:
In this next exercise, you need a Python 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:
Now here's the crucial idea. We can implement recursion using iteration (looping) and a stack. The stack stores all pending (unfinished) recursive calls. More precisely, each item in the stack is a stack frame corresponding to a recursive call. The stack frame stores the values of the parameters and other local variables, for that particular recursive call.
For simplicity, each stack frame can be implemented as a Python list. The length of this list can change over time, as more local variables are defined. For example, when the recursive call completes and we get a value for recx, then recx can be appended to the stack frame.
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 and a stack as described above. 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 len(stack) != 0:
Tail recursion is a special kind of 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.
In addition to once-recursive functions, there are also twice-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 twice-recursion using twice-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. This exercise is optional. 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.
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 through Moodle.
By the way, there are also thrice-recursive functions, four-times-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, in which the number of recursive calls varies from one call to the next. All of these variations on recursion can be implemented using iteration with a single stack. In fact, this is how function calls, recursive or not, are implemented in an actual computer.
If the work done in the helper functions is "not too complicated", then all of this can be implemented on a push-down automaton. If the helper functions are too complicated, then a more sophisticated computational model, such as a Turing machine, is required.