You are here

Repetitive Algorithms

10 February, 2015 - 15:43

"In general, there are two approaches to writing repetitive algorithms. One uses loops; the other uses recursion. Recursion is a repetitive process in which a function calls itself. Both approaches provide repetition, and either can be converted to the other's approach."3 Iteration is one of the categories of control structures. It allows for the processing of some action zero to many times. Iteration is also known as looping and repetition. The math term "to iterate" means to perform the statement parts of the loop. Many problems/tasks require the use of repetitive algorithms. With most programming languages this can be done with either:

  1. looping control structures, specifcally the for loop (an iterative approach)
  2. recursive calling of a function

Using repetitive algorithms as the solution method occurs in many mathematical oriented problems. These in include factorial, Fibonacci numbers, and the Towers of Hanoi problem. Solutions to these problems are often only presented in terms of using the recursive method. However, "... you should understand the two major limitations of recursion. First, recursive solutions may involve extensive overhead because they use function calls. Second, each time you make a call you use up some of your memory allocation. If the recursion is deep that is, if there is a large number of recursive calls then you may run out of memory. Both the factorial and Fibonacci numbers solutions are better developed iteratively." 1

Understanding how recursion or the iterative approaches work will be left to others. They are usually covered in detail as part of studying data structures. Our goal in covering them is to:

  1. Provide you with a definition of recursion
  2. Introduce the alternate solution approach of iteration

The following demonstration program shows both solutions for 8! (eight factorial).