Math 60 -- Notes A3: Recursion vs. Iteration

Notes A3: Recursion vs. Iteration

Math 60 -- D. C. Smolarski, S.J.
Santa Clara University, Department of Mathematics and Computer Science

[Return to Math 60 Homepage | Return to Notes Listing Page]

Overview
Recursion
Iteration
Comments

Overview

Repetition in computer programs is accomplished in one of two ways: either through recursion or through iteration. Both approaches result in a process being repeated several times. In general, recursion tends to be a more natural approach if the problem/question/formula is initially expressed in a recursive manner, and iteration tends to be a more natural approach if the problem/question/formula is expressed as a process done a specified number of times.

Recursion tends to be more problematic for a computer to implement (but easier for a programmer to code!), however, while iteration is much more efficient for a computer to implement.

Recursion

As noted before, recursion refers to an approach in which something refers to itself, but in a slightly simpler format. A mathematical definition of a function is recursive if the function is defined in terms of itself (with a slightly smaller argument), and a computer function (subroutine) is recursive if it invokes itself (with slightly different arguments).

Every recursive definition must have a base case along with the more general recursive definition. Thus,

          n! = n * (n-1)!
      and 1! = 1


          a^b = a * a^b-1
      and a¹ = a

Recursive codes have no loops. Repetition is achieved when the subprogram calls itself repeatedly until it reaches the base case.

Iteration

Iterative codes usually refers to codes that contain explicit iteration processes, that is, loops.

A loop must have some sort of stopping criterion. Usually it is of one of two type:

predetermined number of iterations through the loop;
an error tolerance that is achieved.

In an interative version of a process such as finding the factorial of n or raising a to the power of b, one can determine an upper bound to the number of times a loop is performed. In other contexts, one would like the loop to be repeated until two successive answers are more or less equal, that is, until two successive answers are within "epsilon" of each other.

Comments

Recursion is the mathematical version of the "divide and conquer" approach to algorithm design. This is the approach in which a problem (of size n) is divided into a slightly smaller problem (of size n-1) and some operation. For example, finding n! is the same as first finding (n-1)! and then multiplying this result by n. To solve the larger problem (for size n), one assumes one can solve the slightly smaller problem (for size n-1) and perform some other (relatively easy) operation.

There are well-known mathematical functions defined recursively, such as the fibonacci sequence:


          f₀ = f₁ = 1
	  f_n = f_n-1 + f_n-2

There are also other well-known problems defined recursively, such as the Towers of Hanoi problem. (This is the problem of moving n disks of decreasing diameter from one peg to another peg, under the restrictions that (1) one can only move one disk at a time, and (2) that one cannot put a larger disk on top of a smaller disk.) The problem is solved recursively, by assuming that one knows how to move n-1 disks and also knows how to move a single disk.

In general, recursive code can be simpler and shorter than iterative code. But recursive programs can run into the problem of increasing the run time (because of the overhead involved in multiple subprogram calls), and of running out of memory (because of the unseen stack that keeps track of variables and return locations).