What is recursion
Recursion is a programming technique you can apply as a natural, simple solution to a whole range of situations that would otherwise be difficult to solve. It is a powerful technique, which unfortunately is not easy to understand at first.
 A recursive function is the function which at some point of execution calls itself.
Look at the example below. The function DoSomething() calls itself, so it's a recursive function.
function DoSomething (n)
{
…
DoSomething (n-1);
}
|
When we experience recursion for the first time, we are usually puzzled. An example of recursion is a magazine cover showing a TV screen showing a magazine cover. The image within an image would be repeated few times before becoming too small to see. Another example is walking between two mirrors. The mirrors are causing mutual recursion. The reflection in the mirror is repeated several times, each one smaller than the previous, before becoming too small to see.
Base (stopper) case
If the function simply called itself it would never terminate. To end the recursion every recursive function has to have at least one base case. A Base (or Stopper) Case is simple to calculate or has a known solution. It does not require any further recursive calls, and therefore stops the recursion. The base case helps build the solution for the whole problem.
Each recursive call must simplify the problem, leading one step closer to the base case(s).
Algorithm
The recursive algorithm usually has the following pattern:
 if we reached the base case(s) solve the problem
else simplify the problem using recursion
To assist you in coding a recursive function, here are the 4 questions you should ask yourself:
1. What are my base cases?
2. Can I define the rest of the problem as the smaller version of the original problem?
3. Does the recursive call lead towards the base cases?
4. How can the base cases help me build the solution towards the original problem?
Example
Recursion comes as a natural solution to the calculation of factorial numbers.
Problem: write a function factorial(n), which given the number n calculates its factorial.
Mathematically, the problem can be expressed like this:
0! = 1
n! = n * (n-1)! for n > 0
To paraphrase: factorial of 0 is 1; factorial of any other positive number n is n multiplied by the factorial of n-1.
Examples:
0!=1
3! = 3*2*1 = 6
5! = 5*4*3*2*1 = 120
8! = 8*7*6*5*4*3*2*1 = 40320
The recursive solution to the factorial problem is a program of only few lines of code. Any non-recursive solution would be a lot bigger and more complex.
function factorial (n)
{
if(n==0) return(1);
return (n * factorial (n-1) );
}
document.write(factorial(5));
|
To run the code, paste it into JavaScript Editor, and click the Execute button.
To make understanding of the concept easier, the code above is a simplified version without any error-checking. Calling the function with a negative number: factorial(-1); would result in an infinite recursion because the stop case is never reached. In practice, the program would "hang" after exhausting the available stack.
The factorial function below is a complete implementation, including checking for error conditions.
function factorial(aNumber)
{
// If the number is not an integer, round it down.
aNumber = Math.floor(aNumber);
// The number must be equal to or bigger than zero
if (aNumber < 0)
{
return "undefined";
}
if ((aNumber == 0) || (aNumber == 1))
{ // If the number is 0 or 1, its factorial is 1.
return 1;
}
else
{ // Make a recursive call
return (aNumber * factorial(aNumber - 1));
}
}
number = prompt("Enter a number:", "5")
document.write(factorial(number));
|
To run the code, paste it into JavaScript Editor, and click the Execute button. Entering 5 produces the result of 5*4*3*2*1 = 120
More on recursion... a LOT more...
You now know the mechanism of writing recursive code.
However, it is likely that you are still not comfortable writing recursive functions, or have trouble recognizing all the cases that warrant using recursion naturally. Please keep in mind that of all the programming concepts recursion is perhaps the hardest to understand.
Mastering recursion is worthwhile: there are so many cases when using it is by far the easiest solution that you cannot say, "I'll never use recursion in my scripts!"
Because recursion is such an essential tool in your programming arsenal, we placed extra efforts into the "Learning Recursion through JavaScript" application. It is an intelligent tutoring system that:
Shows you a range of cases best solved by recursion: great if you wish to cut your programming time in half.
Keeps track of your progress: the instruction you receive is tailored to your needs, allowing you to master recursion in no time.
Explains recursion in detail. See how to you recursion turns from a foreign concept to second nature, and
Provides you with plenty of examples and hands-on coding experience.
Click here to learn more and obtain your "Learning Recursion through JavaScript" program.
Next
|
