Recursion

JavaScript 9: Recursion

Recursion is a technique whereby a process is defined in terms of itself. Recursion is usually implemented in a computer program by having a function call itself. Mutual recursion is where two functions call each other. There must be a condition to stop the recursion otherwise, once started, it will not stop until it has exhausted the system resources available (memory or stack memory). Recursion is useful when defining routines which process recursive data structures such as a tree.

A simple example of recursion is as follows:

function walk (left, right){
while (brain != 'stop') {
  forward left;
  forward right;
  walk (left. right)
}}

This is how one walks - one puts the left foot forward and then the right and then repeats the process until one stops. This is just another way of defining a loop structure but for some algorithms a recursive solution is more natural and elegant than a plain while or for loop.

A recursive function for printing a sequence of numbers might be:

function recnumbersa(n){
if (n!=0){
astr+= ' '+n;
recnumbersa(n-1)
}
document.recnums.recout.value=astr;
}

This simple routine takes an initial value such as 10, prints its current value (or adds it to the string of values to be output at the end) and then calls the process again with 10-1. The recursive call only takes place if the current value is not zero. To add a little interest and to show another potentially useful technique two versions of the recursive function have been defined and a choice is made between them on the basis of a value of a random number. The full code is:

function recnumbersa(n){
if (n!=0){
astr+= ' '+n;
recnumbersa(n-1)
}
document.recnums.recout.value=astr;
}
function recnumbersb(n){
if (n!=0){
recnumbersb(n-1);
astr+= ' '+n;
}
document.recnums.recout.value=astr;
}

Can you see the difference between recnumbersa and recnumbersb? They differ only in the position of the astr+= statement: in recnumbersa the string is set before the recursive call while in recnumbersb the string is set after the recursive call. This results in output of '10 9 8...1' on the one hand and '1 2 3...10' on the other - can you see why?

The random number is generated in the form and an if{}else{} statement is included in the onClick handler:

<FORM NAME="recnums">
<INPUT TYPE="button" NAME="start" VALUE="Recursive Numbers" 
onClick="astr='';if (Math.random()>=0.5){recnumbersa(10);}else{recnumbersb(10);}">
<INPUT TYPE="text" NAME="recout" SIZE=25 MAXLENGTH=25>
</FORM>

Note also that the if statement includes the instruction astr=''; which resets the contents of the string each time one of the functions is called.

Recursion relies on the way that many programming languages implement function calls and the way that the scope of variables is limited to the bounds of the function. Each time a function is called the the location in memory of the current instruction is stored in a special area of memory called the stack. Any variables created inside the function are stored on the stack and are removed and destroyed when the function finishes. When a function calls itself recursively, say five times, there are five copies of function variables in the stack, along with the address of where processing finished in the previous function call. At this point none of the function calls has reached the closing statement and each one is still open. At this point the condition for stopping further recursion is reached and the fifth function call, in this case, is completed. The last statement in each function call may take some action which has so far been delayed and only now, as each function call is completed, is this executed and the effect seen. This highlights the difference between taking an action before a recursive function call and taking one after the call.

The algorithm for finding the greatest common divisor of two integers can be defined in a recursive manner. In the non-recursive version we studied earlier there was a while loop to continue the process of finding the gcd; in the recursive version a function is called from within itself until the gcd is found. In the non-recursive version we had to switch the values manually, as in: c=a%b;a=b;b=c;; in the recursive version we pass the values of b and c into the next function call where they become a and b. This should make more sense when you see it but first confirm that it works:

Enter 2 integers, one in each box, to find their greatest common divisor:

Greatest Common Divisor:

The code is as follows:

function recursivegcd(a,b){
var c=a%b; var res;
if (c==0){
  if (b==1){astr='No gcd other than 1';}
  else {astr='gcd is '+b;}
  document.recgcdform.gcdout.value=astr;}
if (c!=0){res=recursivegcd(b,c);}
}

The function consists of two if statements. If (c=a%b) is zero then a check is performed to see whether a gcd was found, other than 1, and output is made. If (c=a%b) is not zero then a recursive call is made to the function passing variables b and c. The function header has paramters (a,b) so new a takes the value of previous b and new b takes the value of previous c.

Recursion and the Fibonacci Sequence

Recursion can be used to calculate numbers in the Fibonacci sequence in an ingenious way. This is the code:

function callfib(n){
var t;
if (n>0) {document.fibform.output.value=fib(n-1)}
else {document.fibform.output.value="numbers > 0 only";}
}

function fib (n){
if (n<2){return n}
else 
{return fib(n-2)+fib(n-1)}
}

And this is the form:

<form name="fibform">
Enter a number for the Fibonacci term you want:
<input type="text" name="input" size=20><P>
<input type ="button" value="click to calc fib number" onclick="callfib(document.fibform.input.value)">
<input type="text" name="output" size=20>
</form>

The form asks the user to enter the position of a number in the sequence and the number is then calculated and displayed. The function callfib() is used as a point from which to call the main function. The main function, fib(), checks to see if the current value of the user's input is less than 2, in which case the value is returned - this will be either 0 or 1. If the value is 2 or more the program continues with the recursive call fib(n-2)+fib(n-1). This is based on the notion that any given number in the Fibonacci sequence is calculated by adding the previous 2, that is fib[n-2]+fib[n-1]. The second part of callfib() checks to see if the user entered zero, in which case the Fibonacci number is set to zero; for other user inputs the Fibonacci number is set to whatever the function fib() returns.

It is worth taking some time to understand what is happening here. Firstly, the indexing of the sequence begins at zero so the first term, 0, is fib[0]=0, the second term is fib[1]=1, and so on.

If the user asks for the first term in the sequence (0) we must find fib[user_input - 1] or fib[0].

The first call to fib() passes n=0 (1-1) so the first test (n<2?) succeeds, the call returns 0 and the output is 0, the correct answer.

If the user asks for the second term in the sequence (1) we must find fib[user_input - 1] or fib[1].

The first call to fib() passes n=1 (2-1) so the first test (n<2?) succeeds, the call returns 1 and the output is 1, the correct answer.

If the user asks for the third term in the sequence (1) we must find fib[user_input - 1] or fib[2].

The first call to fib() passes n=2 (3-1) so the first test (n<2?) fails and the program continues to the else part of the function. Here the program calls fib(2-2) which leads to a return of zero. Control then passes to the +fib(n-1) part which is +fib(2-1) which leads to a return of 1. Thus 1 was added to zero and the correct answer of 1 was returned for the third term in the sequence.

If the user asks for the fourth term in the sequence (2) we must find fib[user_input - 1] or fib[3].

The first call to fib() passes n=3 (4-1) so the first test (n<2?) fails and the program continues to the else part of the function. Here the program calls fib(3-2) which leads to a return of 1. Control then passes to the +fib(n-1) part which is +fib(3-1). This leads to a further call of fib(n-2) with a value of 2 which as we have seen returns a value of 0. There is now a further call of +fib(2-1) which returns a value of 1. Thus 1 is added to zero and 1 giving a result of 2.

In diagram form:

Find term 3 (1) - callfib(3-1):

         fib(2)
        /      \
   fib(2-2)  +  fib(2-1)


Find term 4 (2) - callfib(4-1):

                    fib(3)
                  /       \
                 /         \
                /           \
               /             \
          fib(3-2):1   +    fib(3-1)
                           /        \
                      fib(2-2):0 +  fib(2-1):1


Find term 5 (3) - callfib(5-1):

                    fib(4)
                  /       \
                 /          \
                /             \
               /                \
          fib(4-2)        +      fib(4-1)
         /        \             /        \
   fib(2-2):0  +  fib(2-1):1   /          \
                              /            \
                      fib(3-2):1    +     fib(3-1)
                                         /        \
                                  fib(2-2):0  +  fib(2-1):1

Each call of fib(n-2)+fib(n-1) gives rise to a tree where 0 is added to 1.

The call fib(4) invokes fib(4-2)+fib(4-1) which breaks down into the tree for fib(2) and fib(3).

The call fib(3) invokes fib(3-2)+fib(3-1) which breaks down into the trees for fib(1) and fib(2). fib(1) returns 1 while fib(2) invokes fib(0)+fib(1) which returns 0 + 1.

The bigger the number in the Fibonacci sequence the more calls are made which produce these trees. The sum of 1s and 0s in the trees add up to the correct value for the term in the sequence requested. This introduces the valuable idea of the tree data structure and the notion of 'traversing' a tree. Each tree here is a binary tree and the traversal is left-centre-right. In this case the central node includes the plus operator which adds the contents of left and right nodes.

Recursion relies on nested calls to functions and storage of variables from each function call on a stack. Excessive calls to the function may lead to stack overflow, loss of data and failure of the program. Stack overflow provides one way to crash a program and a test for the protection afforded by an operating system to its memory resources. It also provides a way to compare processor speeds. Is the recursive algorithm more or less efficient than the non-recursive ones we saw earlier? Run the program a few times with inputs of 25 or more to find out (don't put in silly values like 2000, etc., or even 100).

Return to Javascript Menu