# 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.

```javascript
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.

```javascript
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?

```javascript
// 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}$$.

```javascript
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);

```