The programs we have discussed thus far are generally structured as functions that call one another in a disciplined, hierarchical manner. A recursive function is a function that calls itself, either directly, or indirectly through another function. Recursion is an important topic discussed at length in computer science courses. In this section, we present a simple example of recursion.
We consider recursion conceptually first; then we examine several programs con-taining recursive functions. Recursive problem-solving approaches have a number of ele-ments in common. A recursive function is called to solve a problem. The function actually knows how to solve only the simplest case(s), or base case(s). If the function is called with a base case, the function returns a result. If the function is called with a more complex problem, it divides the problem into two conceptual pieces—a piece that the function knows how to process (the base case) and a piece that the function does not know how to process. To make recursion feasible, the latter piece must resemble the original problem, but be a simpler or smaller version it. Because this new problem looks like the original problem, the function invokes (calls) a fresh copy of itself to go to work on the smaller problem; this invocation is referred to as a recursive call, or the recursion step. The recur-sion step also normally includes the keyword return, because its result will be combined with the portion of the problem the function knew how to solve to form a result that will be passed back to the original caller.
The recursion step executes while the original call to the function is still open (i.e., it has not finished executing). The recursion step can result in many more recursive calls as the function divides each new subproblem into two conceptual pieces. For the recursion eventually to terminate, each time the function calls itself with a simpler version of the original problem, the sequence of smaller and smaller problems must converge on the base case. At that point, the function recognizes the base case, returns a result to the previous copy of the function, and a sequence of returns ensues up the line until the original func-tion call eventually returns the final result to the caller. This process sounds exotic when compared with the conventional problem solving we have performed to this point.
As an example of these concepts at work, let us write a recursive program to perform a popular mathematical calculation. The factorial of a nonnegative integer n, written n! (and pronounced “n factorial”), is the product
n · (n – 1) · (n – 2) · … · 1
where 1! is equal to 1 and 0! is defined as 1. For example, 5! is the product 5 · 4 · 3 · 2 · 1, which is equal to 120.
The factorial of an integer (number in the following example) greater than or equal to zero can be calculated iteratively (nonrecursively) using a for statement, as follows:
var factorial = 1;
for ( var counter = number; counter >= 1; --counter ) factorial *= counter;
A recursive definition of the factorial function is arrived at by observing the following relationship:
n! = n · (n – 1)!
For example, 5! is clearly equal to 5 * 4!, as is shown by the following equations:
5! = 5 · 4 · 3 · 2 · 1 5! = 5 · (4 · 3 · 2 · 1) 5! = 5 · (4!)
The evaluation of 5! would proceed as shown in Fig. 9.10. Figure 9.10 (a) shows how the succession of recursive calls proceeds until 1! is evaluated to be 1, which terminates the recursion. Figure 9.10 (b) shows the values returned from each recursive call to its caller until the final value is calculated and returned.
Figure 9.11 uses recursion to calculate and print the factorials of the integers 0 to 10. The recursive function factorial first tests (line 24) whether a terminating condition is true, i.e., whether number is less than or equal to 1. If so, factorial returns 1, no further recursion is necessary and the function returns. If number is greater than 1, line 27 expresses the problem as the product of number and the value returned by a recursive call to factorial evaluating the factorial of number - 1. Note that factorial( number - 1 ) is a simpler problem than the original calculation, factorial( number ).
Function factorial (lines 22–28) receives as its argument the value for which to cal-culate the factorial. As can be seen in the screen capture in Fig. 9.11, factorial values become large quickly.
<?xml version = "1.0" encoding = "utf-8"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
<!-- Fig. 9.11: FactorialTest.html -->
<!-- Factorial calculation with a recursive function. -->
<html xmlns = "http://www.w3.org/1999/xhtml">
<title>Recursive Factorial Function</title>
document.writeln( "<h1>Factorials of 1 to 10</h1>" );
document.writeln( "<table>" );
for ( var i = 0; i <= 10; i++ )
document.writeln( "<tr><td>" + i + "!</td><td>" +
factorial( i ) + "</td></tr>" );
document.writeln( "</table>" );
// Recursive definition of function factorial
function factorial( number )
if ( number <= 1 ) // base case
return number * factorial( number - 1 );
} // end function factorial
Fig. 9.11 | Factorial calculation with a recursive function.
Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.