Home | | **Internet & World Wide Web HOW TO PROGRAM** | | **Internet Programming** | | **Web Programming** | Recursion - JavaScript(JS)

The programs we have discussed thus far are generally structured as functions that call one another in a disciplined, hierarchical manner.

**Recursion**

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"

**
**"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

**
**<!-- Fig. 9.11: FactorialTest.html
-->

**
**<!-- Factorial calculation with a
recursive function. -->

**
**<html xmlns = "http://www.w3.org/1999/xhtml">

**
**<head>

**
**<title>Recursive Factorial Function</title>

**
**<script type = "text/javascript">

**
**<!--

**
**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 1;

else

return number * factorial( number - 1 );

} // end function factorial

**
**// -->

**
**</script>

**
**</head><body></body>

</html>

**Fig. 9.11 **|** **Factorial** **calculation** **with** **a** **recursive function.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.