$19\mathrm{.}14$ Lab $11$: A general method of removing recursion

Recursion: A Recursive Definition

In programming, a recursive function is one that calls itself. Many students find recursion challenging, but it can be a powerful tool when used effectively.

Some programming languages rely entirely on recursion for iteration. Today, we will explore the opposite concept: removing recursion entirely.

Two Cases of Recursion

When removing recursion, there are two main cases to address:

$1.$ Tail Recursion

Tail recursion occurs when the recursive call is the last operation executed in the function. Consider this simple example:

void recursiveFunction$($int x$,$ int y$)\{$ if $($x $>0$ && y $>0)\{$ cout $<<$ x $<<$ y $<<$ endl; recursiveFunction$($x $-1,$ y $/2)$; $\}\}$

Tail recursion is relatively easy to eliminate. Some compilers automatically optimize tail$-$recursive functions by transforming them into loops during code generation.

To manually eliminate tail recursion, you can replace the recursive call with a loop and update the function$$s variables accordingly:

void nonRecursiveFunction$($int x$,$ int y$)\{$ while $($x $>0$ && y $>0)\{$ cout $<<$ x $<<$ y $<<$ endl; x $=$ x $-1$; y $=$ y $/2$; $\}\}$

This transformation often results in faster code, as the overhead of function calls is generally higher than that of a loop and variable assignments. While the performance improvement might be small, it is still meaningful.

$2.$ General Recursion

In cases where the recursive call is not the final operation in the function, removing recursion becomes more complex. This situation typically requires the use of a stack.

Recursion relies on the runtime call stack to store information until it is needed. By simulating this behavior with an explicit stack, we can eliminate recursion and reduce the risk of exhausting the call stack, which is finite.

Lab Exercise

The focus of today$$s lab is to practice removing recursion. We$$ve encountered this technique before, such as when implementing iterators for binary tree objects. By the end of this exercise, you$$ll understand how to replace recursive logic with iterative approaches while preserving functionality.

Start by reviewing the downloadable programs lab$11$a$.$ccp and lab$11$b$.$cpp which feature recursion. They are solving the same problem but b adds animation element.

Then begin looking at the lab and focus on the one function where you have to use a stack rather than recursion.