Recursion

The factorial function is defined for all positive integers, along with $0$. What value should $0!$ have? It's the product of all integers greater than or equal to $1$ and less than or equal to $0$. But there are no such integers. Therefore, we define 0! to equal the identity for multiplication, which is $1$. (Defining $0! = 1$ meshes nicely with the formula for choosing $k$ things out of nnn things. Suppose that we want to know how many ways there are to choose $n$ things out of nnnthings. That's easy, because there is only one way: choose all nnn things. So now we know that, using our formula, $n! / (n! \cdot (n-n)!)$should equal $1$. But $(n-n)!$ is $0!$, so now we know that $n! / (n! \cdot 0!)$ should equal $1$. If we cancel out the n!n!in both the numerator and denominator, we see that $1/(0!)$ should equal $1$, and it does because $0!$ equals $1$.)

So now we have a way to think about $n!$. It equals $1$ when $n = 0$ and it equals $1\cdot 2 \cdots (n-1) \cdot n$ when $n$ is positive.

var factorial = function(n) {
    var result = 1;

    for (var i = 1; i <= n; i++) {
        result *= i;
    }

    return result;
};

println("The value of 5! should be " + 5*4*3*2*1);
println("The value of 5! is " + factorial(5));
println("The value of 0! should be 1");
println("The value of 0! is " + factorial(0));

Program.assertEqual(factorial(5), 120);
Program.assertEqual(factorial(0), 1);

Here is the basic idea behind recursive algorithms:

To solve a problem, solve a subproblem that is a smaller instance of the same problem, and then use the solution to that smaller instance to solve the original problem.

var factorial = function(n) {
	// base case: 
	if (n === 0) {
	    return 1;
	}
	// recursive case:
	return factorial(n-1) * n;
}; 

println("The value of 0! is " + factorial(0) + ".");
println("The value of 5! is " + factorial(5) + ".");

Program.assertEqual(factorial(0), 1);
Program.assertEqual(factorial(5), 120);

We can distill the idea of recursion into two simple rules:

1. Each recursive call should be on a smaller instance of the same problem, that is, a smaller subproblem.

2. The recursive calls must eventually reach a base case, which is solved without further recursion.

Challenge: is a string a palindrome?

// Returns the first character of the string str
var firstCharacter = function(str) {
    return str.slice(0, 1);
};

// Returns the last character of a string str
var lastCharacter = function(str) {
    return str.slice(-1);
};

// Returns the string that results from removing the first
//  and last characters from str
var middleCharacters = function(str) {
    return str.slice(1, -1);
};

var isPalindrome = function(str) {
    // base case #1
    if (str.length <= 1){
        return true;
    }
    // base case #2
    if (firstCharacter(str) === lastCharacter(str)){
        return true;
    } else { 
        return false;
    }
    // recursive case
    return isPalindrome(middleCharacters(str));
};

var checkPalindrome = function(str) {
    println("Is this word a palindrome? " + str);
    println(isPalindrome(str));
};

checkPalindrome("a");
Program.assertEqual(isPalindrome("a"), true);
checkPalindrome("motor");
Program.assertEqual(isPalindrome("motor"), false);
checkPalindrome("rotor");
Program.assertEqual(isPalindrome("rotor"), true);
checkPalindrome("moon");

Recursive algorithm for computing $x^n$:

• The base case is when $n = 0$ and $x^0 = 1$.

• If $n$ is positive and even, recursively compute $y = x^{n/2}$, and then $x^n = y \cdot y$. Notice that you can get away with making just one recursive call in this case, computing $x^{n/2}$ just once, and then you multiply the result of this recursive call by itself.

• If $n$ is positive and odd, recursively compute $x^{n-1}$, so that the exponent either is $0$ or is positive and even. Then, $x^n = x^{n-1} \cdot x$.

• If $n$ is negative, recursively compute $x^{-n}$, so that the exponent becomes positive. Then, $x^n = 1 / x^{-n}$.

var isEven = function(n) {
    return n % 2 === 0;
};

var isOdd = function(n) {
    return !isEven(n);
};

var power = function(x, n) {
    println("Computing " + x + " raised to power " + n + ".");
    // base case
    if (n === 0){
        return 1;
    }
    // recursive case: n is odd
    if (isOdd(n)){
        return power(x, n-1) * x;
    }
    // recursive case: n is even
    if (isEven(n)) {
        var y = power(x, n/2);
        return y*y;
    }
    // recursive case: n is negative
    if (n < 0) {
        return 1 / power(x, -n);r
    }
};

var displayPower = function(x, n) {
    println(x + " to the " + n + " is " + power(x, n));
};

displayPower(3, 0);
Program.assertEqual(power(3, 0), 1);
displayPower(3, 1);
Program.assertEqual(power(3, 1), 3);
displayPower(3, 2);
Program.assertEqual(power(3, 2), 9);
displayPower(3, -1);
Program.assertEqual(power(3, -1), 1/3);