# 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);

```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://stephanosterburg.gitbook.io/scrapbook/math/algorithm-khan-academy/recursion.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.