Article Preview

COLUMN

Stacks and Recursion

A look at stacks as a replacement for recursion

Issue: 2.3 (December/January 2003)
Author: Thomas Reed
Author Bio: Thomas Reed has been programming as a hobbyist for more than 20 years, and fell in love with the Mac in 1984.
Article Description: No description available.
Article Length (in bytes): 6,371
Starting Page Number: 34
Article Number: 2315
Resource File(s):

2315.zip Updated: 2013-03-11 19:07:57

Related Link(s): None

Excerpt of article text...

The stack is a data structure that is encountered frequently in software design. Although the basic idea of stacks is simple, applications are quite diverse. Stacks provide the foundation for function calls. They can be used to represent a deck of cards in a solitaire game. Undo and redo algorithms are based on stacks. In this article, I will discuss one particular practical application of stacks -- the use of stacks in recursion.

If you are not familiar with stacks, now is the time to flip back to this column in the very first issue of REALbasic Developer. In that issue, Matt Neuburg explained stacks, implementing them using a linked list. Although I will be using arrays to implement the stacks in my examples, the basic idea is the same.

Recursion is a very powerful technique that can be used to solve many different problems. The basic idea of recursion is that a function repeatedly calls itself to come up with a solution. For example, an implementation of the Pow function, used to raise an integer to a certain power, might look like this:

Function Pow(base as integer, exponent as integer) as Integer

if exponent = 0 then

return 1

...End of Excerpt. Please purchase the magazine to read the full article.