4] selections - recursion
> write loop to do something
- example multiple num * by 10
> put loop into function ( pass in arg)
5] recursion
function factorial(n) {
if (n === 0) {
return 1;
}
// This is it! Recursion!!
return n * factorial(n - 1);
}
There are a few key features of recursion that must be included in order for it to work properly.
The first is a base case: this is a statement, usually within a conditional clause like if, that stops the recursion. If you don't have a base case, the recursion will go on infinitely and your program will crash. Crash = bad.
The second is a recursive case: this is the statement where the recursion actually happens: where the recursive function is called on itself.
function factorial(n) {
// This is our Base Case - when n is equal to 0, we stop the recursion
if (n === 0) {
return 1;
}
// This is our Recursive Case
// It will run for all other conditions except when n is equal to 0
return n * factorial(n - 1);
}
7] One other useful (and often necessary) feature of a recursive function is a termination condition.
This is a specific statement that will explicitly stop the recursion. The base case is a form of termination condition, though for our purposes here I will use termination condition to describe a statement that will cancel recursion in the event of bad input or other potential error.
To put this into practice, look at the factorial function. What would happen if we called it on a negative integer? Since the recursion will only stop when n is equal to 0, and that would never happen with a negative integer, our program would crash.
In order to protect against this, we use a termination condition to ensure that the value passed to the function is valid, and will not crash our program. As a programmer, you must constantly be thinking about how to prepare for any type of situation and ensure that your code can handle it correctly.
function factorial(n) {
if (n < 0) {
// Termination condition to prevent infinite recursion
console.log("NO negative numbers");
return;
}
// Base case
if (n === 0) {
return 1;
}
// Recursive case
return n * factorial(n -1);
}
factorial(-1);
factorial(5);
8] arguements in recursion
When building your recursive case (the code that will be repeated), one of the rules of thumb is to ensure that the arguments you use for the recursion will lead to your base case.
If the value we pass to the recursive function call is the same as the initial value, chances are our code will enter an infinite loop. And then, crash. Bad.
So, the question you have to ask yourself is "does the recursive case modify my arguments in such a way that each recursion brings it one step closer to the base case?"
// What's wrong with this picture? Why won't this recursion work?
return n * factorial(n);
// CORRECTED
return n * factorial(n-1);
9] try from scratch
Now that we've covered the bare essentials, try rebuilding the factorial() function we've been working on, but this time write it all from scratch. To help you along, here are five questions that you can use whenever using recursion in your code:
// recursive function with arg
function factorial(n) {
console.log(n);
// termination condition
if ( n < 1){
console.log("no negative numbers")
}
// base case
if (n === 0) {
return 1;
}
// return
// ERROR return factorial(n-1);
return n * factorial(n-1);
}
To start deconstructing recursion, let's first take a look at the difference between loops and recursive functions. In many situations, they are effectively interchangeable.
In fact, many programming languages don't have loops like for or while, but use recursion for everything.
In this example, each function does the same thing. One uses a loop, the other uses recursion.
ID: 5327
NAME: CREATE-article
DESCRIPTION: recursion -
START DATE TIME: 2015-06-25 09:01:46
EST DURATION: 01:00:00
END DATE TIME: 2015-06-25 10:01:46
STATUS:
PRIORITY: -5
OWNER ID: 1