Algorithms at Khan Academy part 2

Recursive algorithms
The technique recursion is an algorithm to solve a problem by solving a smaller instance of the same problem, unless the problem is so small that we can just solve it directly.

The factorial function = very useful for when we're trying to count how many different orders there are for things or how many different ways we can combine things.

Iterative factorial

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

    return result;
};

A recursive solution would involve the function calling itself
Induction starts from the base case(s) and works up, while recursion starts from the top and works downwards until it hits a base case.

With induction we know we started on a solid foundation of the base cases, but with recursion we have to be careful when we design the algorithm to make sure that we eventually hit a base case.

Recursive factorial

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

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);
Program.assertEqual(factorial(4), 24);
Program.assertEqual(factorial(3), 6);

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.

A palindrome is a word that is spelled the same forward and backward. For example, rotor and redder.

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 false;}
    // recursive case
    return isPalindrome(middleCharacters(str));
};

var checkPalindrome = function(str) {
    println("Is this word a palindrome? " + str);
    println(isPalindrome(str));
};
 
recursive algorithm for computing $x^n$x​n​​x, start superscript, n, end superscript:

• The base case is when $n = 0$n, equals, 0, and $x^0 = 1$x, start superscript, 0, end superscript, equals, 1.
• If $n$nn is positive and even, recursively compute $y = x^{n/2}$​​y, equals, x, start superscript, n, slash, 2, end superscript, and then $x^n=y\cdot y$x, start superscript, n, end superscript, equals, y, dot, y. Notice that you can get away with making just one recursive call in this case, computing $x^{n\mathrm{/}2}$​​x, start superscript, n, slash, 2, end superscript just once, and then you multiply the result of this recursive call by itself.
• If $n$nn is positive and odd, recursively compute $x^{n-1}$​​x, start superscript, n, minus, 1, end superscript, so that the exponent either is 0 or is positive and even. Then, $x^n=x^{n-1}$x, start superscript, n, end superscript, equals, x, start superscript, n, minus, 1, end superscript, dot, x.
• If $n$nn is negative, recursively compute $x^{-n}$x​−n​​x, start superscript, minus, n, end superscript, so that the exponent becomes positive. Then, $x^n=1\mathrm{/}{x}^{-n}$​​x, start superscript, n, end superscript, equals, 1, slash, x, start superscript, minus, n, end superscript.

Challenge: Recursive powers

 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 && x^0 === 1){return 1^n;}
    // recursive case: n is negative
    if(n < 0) {
        return 1 / (power(x, abs(n))); //Make sure it's float AND abs
    }

    if(isOdd(n)) { return(power(x,n-1) * x);}
    // recursive case: n is odd
    if (isEven(n)) {
var abc = power(x, n/2);
return(abc*abc);
}
   
    return x * power(x, n-1);

};

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

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

Challenge: Solve Hanoi recursively

var solveHanoi = function(numDisks, fromPeg, toPeg) {
    // base case:  no disks to move
    if(numDisks === 0){
        return 1;}
    // recursive case:
    var sparePeg = hanoi.getSparePeg(fromPeg, toPeg);
solveHanoi(numDisks - 1, fromPeg, sparePeg);
hanoi.moveDisk(fromPeg, toPeg);
solveHanoi(numDisks - 1, sparePeg, toPeg);
};

solveHanoi(5, "A", "B");
Program.assertEqual(hanoi.isSolved("B"),true);