17.1 Recursion vs iteration

Repetitive algorithms

"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." Behrouz A. Forouzan and Richard F. Gilberg, Computer Science A Structured Approach using C++ Second Edition (United States of America: Thompson – Brooks/Cole, 2004) 265. 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, specifically 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." Behrouz A. Forouzan and Richard F. Gilberg, Computer Science A Structured Approach using C++ Second Edition (United States of America: Thompson – Brooks/Cole, 2004) 272.

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).

Demonstration program in c++

Creating a folder or sub-folder for source code files

Depending on your compiler/IDE, you should decide where to download and store source code files for processing. Prudence dictates that you create these folders as needed prior to downloading source code files. A suggested sub-folder for the Bloodshed Dev-C++ 5 compiler/IDE might be named:

• Demo_Programs

If you have not done so, please create the folder(s) and/or sub-folder(s) as appropriate.

Download the demo program

Download and store the following file(s) to your storage device in the appropriate folder(s). Following the methods of your compiler/IDE, compile and run the program(s). Study the source code file(s) in conjunction with other learning materials.

Download from Connexions: Demo_Factorial.cpp

Definitions

recursion

A repetitive process in which a function calls itself.

factorial

A math problem that often is solved using recursion.