递归的递归之书：引言到第四章

print('Hello, world!')

<script type="text/javascript">
document.write("Hello, world!<br />");
</script>

def a():
    print('a() was called.')
    b()
    print('a() is returning.')
def b():
    print('b() was called.')
    c()
    print('b() is returning.')
def c():
    print('c() was called.')
    print('c() is returning.')
a()

<script type="text/javascript">
function a() {
    document.write("a() was called.<br />");
    b();
    document.write("a() is returning.<br />");
}
function b() {
    document.write("b() was called.<br />");
    c();
    document.write("b() is returning.<br />");
}
function c() {
    document.write("c() was called.<br />");
    document.write("c() is returning.<br />");
}
a();
</script>

a() was called.
b() was called.
c() was called.
c() is returning.
b() is returning.
a() is returning.

cardStack = [] # ❶
cardStack.append('5 of diamonds') # ❷
print(','.join(cardStack))
cardStack.append('3 of clubs')
print(','.join(cardStack))
cardStack.append('ace of hearts')
print(','.join(cardStack))
cardStack.pop() # ❸
print(','.join(cardStack))

<script type="text/javascript">
let cardStack = []; // ❶
cardStack.push("5 of diamonds"); // ❷
document.write(cardStack + "<br />");
cardStack.push("3 of clubs");
document.write(cardStack + "<br />");
cardStack.push("ace of hearts");
document.write(cardStack + "<br />");
cardStack.pop() // ❸
document.write(cardStack + "<br />");
</script>

5 of diamonds
5 of diamonds,3 of clubs
5 of diamonds,3 of clubs,ace of hearts
5 of diamonds,3 of clubs

def a():
    spam = 'Ant' # ❶
    print('spam is ' + spam) # ❷
    b() # ❸
    print('spam is ' + spam)
def b():
    spam = 'Bobcat' # ❹
    print('spam is ' + spam)
    c() # ❺
    print('spam is ' + spam)
def c():
    spam = 'Coyote' # ❻
    print('spam is ' + spam)
a() # ❼

<script type="text/javascript">
function a() {
    let spam = "Ant"; // ❶
    document.write("spam is " + spam + "<br />"); // ❷
    b(); // ❸
    document.write("spam is " + spam + "<br />");
}
function b() {
    let spam = "Bobcat";//# ❹
    document.write("spam is " + spam + "<br />");
    c(); // ❺
 document.write("spam is " + spam + "<br />");
}
function c() {
    let spam = "Coyote"; // ❻
    document.write("spam is " + spam + "<br />");
}
a(); // ❼
</script>

spam is Ant
spam is Bobcat
spam is Coyote
spam is Bobcat
spam is Ant

def shortest():
    shortest()
shortest()

<script type="text/javascript">
function shortest() {
    shortest();
}
shortest();
</script>

Traceback (most recent call last):
  File "shortest.py", line 4, in <module>
    shortest()
  File "shortest.py", line 2, in shortest
    shortest()
  File "shortest.py", line 2, in shortest
    shortest()
  File "shortest.py", line 2, in shortest
    shortest()
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Uncaught RangeError: Maximum call stack size exceeded
    at shortest (shortest.html:2)
    at shortest (shortest.html:3)
    at shortest (shortest.html:3)
    at shortest (shortest.html:3)
    at shortest (shortest.html:3)
    at shortest (shortest.html:3)
    at shortest (shortest.html:3)
    at shortest (shortest.html:3)
    at shortest (shortest.html:3)
    at shortest (shortest.html:3)

def shortestWithBaseCase(makeRecursiveCall):
    print('shortestWithBaseCase(%s) called.' % makeRecursiveCall)
    if not makeRecursiveCall:
        # BASE CASE
        print('Returning from base case.')
        return # ❶
    else:
        # RECURSIVE CASE
        shortestWithBaseCase(False) # ❷
        print('Returning from recursive case.')
        return
print('Calling shortestWithBaseCase(False):')
shortestWithBaseCase(False) # ❸
print()
print('Calling shortestWithBaseCase(True):')
shortestWithBaseCase(True) # ❹

<script type="text/javascript">
function shortestWithBaseCase(makeRecursiveCall) {
    document.write("shortestWithBaseCase(" + makeRecursiveCall + 
     ") called.<br />");
    if  (makeRecursiveCall === false) {
        // BASE CASE
        document.write("Returning from base case.<br />");
        return; // ❶
 } else {
        // RECURSIVE CASE
        shortestWithBaseCase(false); // ❷
        document.write("Returning from recursive case.<br />");
        return;
    }
}
document.write("Calling shortestWithBaseCase(false):<br />");
shortestWithBaseCase(false); // ❸
document.write("<br />");
document.write("Calling shortestWithBaseCase(true):<br />");
shortestWithBaseCase(true); // ❹
</script>

Calling shortestWithBaseCase(False):
shortestWithBaseCase(False) called.
Returning from base case.
Calling shortestWithBaseCase(True):
shortestWithBaseCase(True) called.
shortestWithBaseCase(False) called.
Returning from base case.
Returning from recursive case.

def countDownAndUp(number):
    print(number) # ❶
    if number == 0:
        # BASE CASE
        print('Reached the base case.') # ❷
        return
    else:
        # RECURSIVE CASE
        countDownAndUp(number - 1) # ❸
        print(number, 'returning') # ❹
        return
countDownAndUp(3) # ❺

<script type="text/javascript">
function countDownAndUp(number) {
    document.write(number + "<br />"); // ❶
    if (number === 0) {
        // BASE CASE
        document.write("Reached the base case.<br />"); // ❷
        return;
    } else {
        // RECURSIVE CASE
        countDownAndUp(number - 1); // ❸
        document.write(number + " returning<br />"); // ❹
        return;
    }
}
countDownAndUp(3); # ❺
</script>

3
2
1
0
Reached the base case.
1 returning
2 returning
3 returning

def factorial(number):
    product = 1
    for i in range(1, number + 1):
        product = product * i
    return product
print(factorial(5))

<script type="text/javascript">
function factorial(number) {
    let product = 1;
    for (let i = 1; i <= number; i++) {
        product = product * i;
    }
    return product;
}
document.write(factorial(5));
</script>

120

def factorial(number):
    if number == 1:
        # BASE CASE
        return 1
    else:
        # RECURSIVE CASE
        return number * factorial(number - 1) # ❶
print(factorial(5))

<script type="text/javascript">
function factorial(number) {
    if (number == 1) {
        // BASE CASE
        return 1;
 } else {
        // RECURSIVE CASE
        return number * factorial(number - 1); // ❶
    }
}
document.write(factorial(5));
</script>

120

def fibonacci(nthNumber):
    a, b = 1, 1 # ❶
    print('a = %s, b = %s' % (a, b))
    for i in range(1, nthNumber):
        a, b = b, a + b # Get the next Fibonacci number. # ❷
        print('a = %s, b = %s' % (a, b))
    return a
print(fibonacci(10))

<script type="text/javascript">
function fibonacci(nthNumber) {
    let a = 1, b = 1; // ❶
    let nextNum;
    document.write('a = ' + a + ', b = ' + b + '<br />');
    for (let i = 1; i < nthNumber; i++) {
        nextNum = a + b; // Get the next Fibonacci number. // ❷
        a = b;
        b = nextNum;
 document.write('a = ' + a + ', b = ' + b + '<br />');
    }
    return a;
};
document.write(fibonacci(10));
</script>

a = 1, b = 1
a = 1, b = 2
a = 2, b = 3
# --snip--
a = 34, b = 55
55

def fibonacci(nthNumber):
    print('fibonacci(%s) called.' % (nthNumber))
    if nthNumber == 1 or nthNumber == 2: # ❶
        # BASE CASE
        print('Call to fibonacci(%s) returning 1.' % (nthNumber))
        return 1
    else:
        # RECURSIVE CASE
        print('Calling fibonacci(%s) and fibonacci(%s).' % (nthNumber - 1, nthNumber - 2))
        result = fibonacci(nthNumber - 1) + fibonacci(nthNumber - 2)
        print('Call to fibonacci(%s) returning %s.' % (nthNumber, result))
        return result
print(fibonacci(10))

<script type="text/javascript">
function fibonacci(nthNumber) {
    document.write('fibonacci(' + nthNumber + ') called.<br />');
    if (nthNumber === 1 || nthNumber === 2) { // ❶
        // BASE CASE
        document.write('Call to fibonacci(' + nthNumber + ') returning 1.<br />');
        return 1;
    }
    else {
        // RECURSIVE CASE
        document.write('Calling fibonacci(' + (nthNumber - 1) + ') and fibonacci(' + (nthNumber - 2) + ').<br />');
        let result = fibonacci(nthNumber - 1) + fibonacci(nthNumber - 2);
        document.write('Call to fibonacci(' + nthNumber + ') returning ' + result + '.<br />');
        return result;
    }
}
document.write(fibonacci(10) + '<br />');
</script>

fibonacci(10) called.
Calling fibonacci(9) and fibonacci(8).
fibonacci(9) called.
Calling fibonacci(8) and fibonacci(7).
fibonacci(8) called.
Calling fibonacci(7) and fibonacci(6).
fibonacci(7) called.
# --snip--
Call to fibonacci(6) returning 8.
Call to fibonacci(8) returning 21.
Call to fibonacci(10) returning 55.
55

callStack = [] # The explicit call stack, which holds "frame objects". ❶
callStack.append({'returnAddr': 'start', 'number': 5}) # "Call" the "factorial() function". ❷
returnValue = None
while len(callStack) > 0:
    # The body of the "factorial() function":
    number = callStack[-1]['number'] # Set number parameter.
    returnAddr = callStack[-1]['returnAddr']
    if returnAddr == 'start':
        if number == 1:
            # BASE CASE
            returnValue = 1
            callStack.pop() # "Return" from "function call". ❸
            continue
        else:
            # RECURSIVE CASE
            callStack[-1]['returnAddr'] = 'after recursive call'
            # "Call" the "factorial() function":
            callStack.append({'returnAddr': 'start', 'number': number - 1}) # ❹
            continue
    elif returnAddr == 'after recursive call':
        returnValue = number * returnValue
        callStack.pop() # "Return from function call". ❺
        continue
print(returnValue)

<script type="text/javascript">
let callStack = []; // The explicit call stack, which holds "frame objects". // ❶
callStack.push({"returnAddr": "start", "number": 5}); // "Call" the "factorial() function". // ❷
let returnValue;
while (callStack.length > 0) {
// The body of the "factorial() function":
    let number = callStack[callStack.length - 1]["number"]; // Set number parameter.
    let returnAddr = callStack[callStack.length - 1]["returnAddr"];
    if (returnAddr == "start") {
        if (number === 1) {
            // BASE CASE
            returnValue = 1;
            callStack.pop(); // "Return" from "function call". // ❸
            continue;
        } else {
            // RECURSIVE CASE
 callStack[callStack.length - 1]["returnAddr"] = "after recursive call";
            // "Call" the "factorial() function":
            callStack.push({"returnAddr": "start", "number": number - 1}); // ❹
            continue;
        }
    } else if (returnAddr == "after recursive call") {
        returnValue = number * returnValue;
        callStack.pop(); // "Return from function call". // ❺
        continue;
    }
}
document.write(returnValue + "<br />");
</script>

print('Code in a loop:')
i = 0
while i < 5:
    print(i, 'Hello, world!')
    i = i + 1
print('Code in a function:')
def hello(i=0):
    print(i, 'Hello, world!')
    i = i + 1
    if i < 5:
        hello(i) # RECURSIVE CASE
 else:
        return # BASE CASE
hello()

<script type="text/javascript">
document.write("Code in a loop:<br />");
let i = 0;
while (i < 5) {
    document.write(i + " Hello, world!<br />");
    i = i + 1;
}
document.write("Code in a function:<br />");
function hello(i) {
    if (i === undefined) {
        i = 0; // i defaults to 0 if unspecified.
    }
    document.write(i + " Hello, world!<br />");
    i = i + 1;
    if (i < 5) {
        hello(i); // RECURSIVE CASE
    }
    else {
        return; // BASE CASE
    }
}
hello();
</script>

Code in a loop:
0 Hello, world!
1 Hello, world!
2 Hello, world!
3 Hello, world!
4 Hello, world!
Code in a function:
0 Hello, world!
1 Hello, world!
2 Hello, world!
3 Hello, world!
4 Hello, world!

def findSubstringIterative(needle, haystack):
    i = 0
    while i < len(haystack):
        if haystack[i:i + len(needle)] == needle:
            return i # Needle found.
        i = i + 1
    return -1 # Needle not found.
def findSubstringRecursive(needle, haystack, i=0):
    if i >= len(haystack):
        return -1 # BASE CASE (Needle not found.)
    if haystack[i:i + len(needle)] == needle:
        return i # BASE CASE (Needle found.)
    else:
        # RECURSIVE CASE
        return findSubstringRecursive(needle, haystack, i + 1)
print(findSubstringIterative('cat', 'My cat Zophie'))
print(findSubstringRecursive('cat', 'My cat Zophie'))

<script type="text/javascript">
function findSubstringIterative(needle, haystack) {
    let i = 0;
    while (i < haystack.length) {
        if (haystack.substring(i, i + needle.length) == needle) {
            return i; // Needle found.
        }
        i = i + 1
    }
    return -1; // Needle not found.
}
function findSubstringRecursive(needle, haystack, i) {
    if (i === undefined) {
        i = 0;
    }
    if (i >= haystack.length) {
        return -1; // # BASE CASE (Needle not found.)
    }
    if (haystack.substring(i, i + needle.length) == needle) {
        return i; // # BASE CASE (Needle found.)
    } else {
        // RECURSIVE CASE
        return findSubstringRecursive(needle, haystack, i + 1);
    }
}
document.write(findSubstringIterative("cat", "My cat Zophie") + "<br />");
document.write(findSubstringRecursive("cat", "My cat Zophie") + "<br />");
</script>

3
3

def exponentByIteration(a, n):
    result = 1
    for i in range(n):
        result *= a
    return result
print(exponentByIteration(3, 6))
print(exponentByIteration(10, 3))
print(exponentByIteration(17, 10))

<script type="text/javascript">
function exponentByIteration(a, n) {
    let result = 1;
    for (let i = 0; i < n; i++) {
 result *= a;
    }
    return result;
}
document.write(exponentByIteration(3, 6) + "<br />");
document.write(exponentByIteration(10, 3) + "<br />");
document.write(exponentByIteration(17, 10) + "<br />");
</script>

729
1000
2015993900449

def exponentByRecursion(a, n):
    if n == 1:
        # BASE CASE
        return a
    elif n % 2 == 0:
        # RECURSIVE CASE (When n is even.)
        result = exponentByRecursion(a, n // 2)
        return result * result
    elif n % 2 == 1:
        # RECURSIVE CASE (When n is odd.)
        result = exponentByRecursion(a, n // 2)
        return result * result * a
print(exponentByRecursion(3, 6))
print(exponentByRecursion(10, 3))
print(exponentByRecursion(17, 10))

<script type="text/javascript">
function exponentByRecursion(a, n) {
    if (n === 1) {
        // BASE CASE
        return a;
    } else if (n % 2 === 0) {
        // RECURSIVE CASE (When n is even.)
        result = exponentByRecursion(a, n / 2);
        return result * result;
    } else if (n % 2 === 1) {
        // RECURSIVE CASE (When n is odd.)
        result = exponentByRecursion(a, Math.floor(n / 2));
        return result * result * a;
    }
}
document.write(exponentByRecursion(3, 6));
document.write(exponentByRecursion(10, 3));
document.write(exponentByRecursion(17, 10));
</script>

729
1000
2015993900449

def exponentWithPowerRule(a, n):
    # Step 1: Determine the operations to be performed.
    opStack = []
    while n > 1:
        if n % 2 == 0:
            # n is even.
            opStack.append('square')
            n = n // 2
        elif n % 2 == 1:
            # n is odd.
            n -= 1
            opStack.append('multiply')
    # Step 2: Perform the operations in reverse order.
    result = a # Start result at `a`.
    while opStack:
        op = opStack.pop()
        if op == 'multiply':
            result *= a
        elif op == 'square':
            result *= result
    return result
print(exponentWithPowerRule(3, 6))
print(exponentWithPowerRule(10, 3))
print(exponentWithPowerRule(17, 10))

<script type="text/javascript">
function exponentWithPowerRule(a, n) {
    // Step 1: Determine the operations to be performed.
    let opStack = [];
    while (n > 1) {
 if (n % 2 === 0) {
            // n is even.
            opStack.push("square");
            n = Math.floor(n / 2);
        } else if (n % 2 === 1) {
            // n is odd.
            n -= 1;
            opStack.push("multiply");
        }
    }
    // Step 2: Perform the operations in reverse order.
    let result = a; // Start result at `a`.
    while (opStack.length > 0) {
        let op = opStack.pop();
        if (op === "multiply") {
            result = result * a;
        } else if (op === "square") {
            result = result * result;
        }
    }
    return result;
}
document.write(exponentWithPowerRule(3, 6) + "<br />");
document.write(exponentWithPowerRule(10, 3) + "<br />");
document.write(exponentWithPowerRule(17, 10) + "<br />");
</script>

729
1000
2015993900449

def sum(numbers):
    if len(numbers) == 0: # BASE CASE
        return 0 # ❶
    else: # RECURSIVE CASE
        head = numbers[0] # ❷
        tail = numbers[1:] # ❸
        return head + sum(tail) # ❹
nums = [1, 2, 3, 4, 5]
print('The sum of', nums, 'is', sum(nums))
nums = [5, 2, 4, 8]
print('The sum of', nums, 'is', sum(nums))
nums = [1, 10, 100, 1000]
print('The sum of', nums, 'is', sum(nums))

<script type="text/javascript">
function sum(numbers) {
    if (numbers.length === 0) { // BASE CASE
        return 0; // ❶
    } else { // RECURSIVE CASE
        let head = numbers[0]; // ❷
        let tail = numbers.slice(1, numbers.length); // ❸
        return head + sum(tail); // ❹
    }
}
let nums = [1, 2, 3, 4, 5];
document.write('The sum of ' + nums + ' is ' + sum(nums) + "<br />");
nums = [5, 2, 4, 8];
document.write('The sum of ' + nums + ' is ' + sum(nums) + "<br />");
nums = [1, 10, 100, 1000];
document.write('The sum of ' + nums + ' is ' + sum(nums) + "<br />");
</script>

The sum of [1, 2, 3, 4, 5] is 15
The sum of [5, 2, 4, 8] is 19
The sum of [1, 10, 100, 1000] is 1111

def rev(theString):
    return rev(theString) # This won't magically work.

def rev(theString):
    if len(theString) == 0 or len(theString) == 1: # ❶
        # BASE CASE
        return theString
    else:
        # RECURSIVE CASE
        head = theString[0] # ❷
        tail = theString[1:] # ❸
        return rev(tail) + head # ❹
print(rev('abcdef'))
print(rev('Hello, world!'))
print(rev(''))
print(rev('X'))

<script type="text/javascript">
function rev(theString) {
    if (theString.length === 0 || theString.length === 1) { // ❶
        // BASE CASE
        return theString;
    } else {
        // RECURSIVE CASE
        var head = theString[0]; // ❷
        var tail = theString.substring(1, theString.length); // ❸
   return rev(tail) + head; // ❹
    }
}
document.write(rev("abcdef") + "<br />");
document.write(rev("Hello, world!") + "<br />");
document.write(rev("") + "<br />");
document.write(rev("X") + "<br />");
</script>

fedcba
!dlrow ,olleH
X

def isPalindrome(theString):
    if len(theString) == 0 or len(theString) == 1:
        # BASE CASE
        return True
    else:
        # RECURSIVE CASE
        head = theString[0] # ❶
        middle = theString[1:-1] # ❷
        last = theString[-1] # ❸
        return head == last and isPalindrome(middle) # ❹
text = 'racecar'
print(text + ' is a palindrome: ' + str(isPalindrome(text)))
text = 'amanaplanacanalpanama'
print(text + ' is a palindrome: ' + str(isPalindrome(text)))
text = 'tacocat'
print(text + ' is a palindrome: ' + str(isPalindrome(text)))
text = 'zophie'
print(text + ' is a palindrome: ' + str(isPalindrome(text)))

<script type="text/javascript">
function isPalindrome(theString) {
    if (theString.length === 0 || theString.length === 1) {
        // BASE CASE
        return true;
    } else {
        // RECURSIVE CASE
        var head = theString[0]; // ❶
        var middle = theString.substring(1, theString.length -1); // ❷
        var last = theString[theString.length - 1]; // ❸
        return head === last && isPalindrome(middle); // ❹
    }
}
text = "racecar";
document.write(text + " is a palindrome: " + isPalindrome(text) + "<br />");
text = "amanaplanacanalpanama";
document.write(text + " is a palindrome: " + isPalindrome(text) + "<br />");
text = "tacocat";
document.write(text + " is a palindrome: " + isPalindrome(text) + "<br />");
text = "zophie";
document.write(text + " is a palindrome: " + isPalindrome(text) + "<br />");
</script>

racecar is a palindrome: True
amanaplanacanalpanama is a palindrome: True
tacocat is a palindrome: True
zophie is a palindrome: False

import sys
# Set up towers A, B, and C. The end of the list is the top of the tower.
  TOTAL_DISKS = 6 ❶
# Populate Tower A:
  TOWERS = {'A': list(reversed(range(1, TOTAL_DISKS + 1))), ❷
          'B': [],
          'C': []}
def printDisk(diskNum):
    # Print a single disk of width diskNum.
    emptySpace = ' ' * (TOTAL_DISKS - diskNum)
    if diskNum == 0:
        # Just draw the pole.
        sys.stdout.write(emptySpace + '||' + emptySpace)
    else:
        # Draw the disk.
        diskSpace = '@' * diskNum
        diskNumLabel = str(diskNum).rjust(2, '_')
        sys.stdout.write(emptySpace + diskSpace + diskNumLabel + diskSpace + emptySpace)
def printTowers():
    # Print all three towers.
 for level in range(TOTAL_DISKS, -1, -1):
        for tower in (TOWERS['A'], TOWERS['B'], TOWERS['C']):
            if level >= len(tower):
                printDisk(0)
            else:
                printDisk(tower[level])
        sys.stdout.write('\n')
    # Print the tower labels A, B, and C.
    emptySpace = ' ' * (TOTAL_DISKS)
    print('%s A%s%s B%s%s C\n' % (emptySpace, emptySpace, emptySpace, emptySpace, emptySpace))
def moveOneDisk(startTower, endTower):
    # Move the top disk from startTower to endTower.
    disk = TOWERS[startTower].pop()
    TOWERS[endTower].append(disk)
def solve(numberOfDisks, startTower, endTower, tempTower):
    # Move the top numberOfDisks disks from startTower to endTower.
    if numberOfDisks == 1:
        # BASE CASE
        moveOneDisk(startTower, endTower) ❸
        printTowers()
        return
    else:
        # RECURSIVE CASE
        solve(numberOfDisks - 1, startTower, tempTower, endTower) ❹
        moveOneDisk(startTower, endTower) ❺
        printTowers()
        solve(numberOfDisks - 1, tempTower, endTower, startTower) ❻
        return
# Solve:
printTowers()
solve(TOTAL_DISKS, 'A', 'B', 'C')
# Uncomment to enable interactive mode:
#while True:
#    printTowers()
#    print('Enter letter of start tower and the end tower. (A, B, C) Or Q to quit.')
#    move = input().upper()
#    if move == 'Q':
#        sys.exit()
#    elif move[0] in 'ABC' and move[1] in 'ABC' and move[0] != move[1]:
#        moveOneDisk(move[0], move[1])

<script type="text/javascript">
// Set up towers A, B, and C. The end of the array is the top of the tower.
  var TOTAL_DISKS = 6; // ❶
  var TOWERS = {"A": [], // ❷
              "B": [],
              "C": []};
// Populate Tower A:
for (var i = TOTAL_DISKS; i > 0; i--) {
    TOWERS["A"].push(i);
}
function printDisk(diskNum) {
    // Print a single disk of width diskNum.
    var emptySpace = " ".repeat(TOTAL_DISKS - diskNum);
    if (diskNum === 0) {
        // Just draw the pole.
        document.write(emptySpace + "||" + emptySpace);
    } else {
        // Draw the disk.
        var diskSpace = "@".repeat(diskNum);
        var diskNumLabel = String("___" + diskNum).slice(-2);
        document.write(emptySpace + diskSpace + diskNumLabel + diskSpace + emptySpace);
    }
}
function printTowers() {
    // Print all three towers.
    var towerLetters = "ABC";
    for (var level = TOTAL_DISKS; level >= 0; level--) {
        for (var towerLetterIndex = 0; towerLetterIndex < 3; towerLetterIndex++) {
            var tower = TOWERS[towerLetters[towerLetterIndex]];
            if (level >= tower.length) {
                printDisk(0);
            } else {
                printDisk(tower[level]);
            }
        }
        document.write("<br />");
    }
    // Print the tower labels A, B, and C.
    var emptySpace = " ".repeat(TOTAL_DISKS);
    document.write(emptySpace + " A" + emptySpace + emptySpace +
" B" + emptySpace + emptySpace + " C<br /><br />");
}
function moveOneDisk(startTower, endTower) {
    // Move the top disk from startTower to endTower.
    var disk = TOWERS[startTower].pop();
    TOWERS[endTower].push(disk);
}
function solve(numberOfDisks, startTower, endTower, tempTower) {
    // Move the top numberOfDisks disks from startTower to endTower.
    if (numberOfDisks == 1) {
        // BASE CASE
        moveOneDisk(startTower, endTower); ❸
        printTowers();
        return;
    } else {
        // RECURSIVE CASE
        solve(numberOfDisks - 1, startTower, tempTower, endTower); ❹
 moveOneDisk(startTower, endTower); ❺
        printTowers();
        solve(numberOfDisks - 1, tempTower, endTower, startTower); ❻
        return;
    }
}
// Solve:
document.write("<pre>");
printTowers();
solve(TOTAL_DISKS, "A", "B", "C");
document.write("</pre>");
</script>

||            ||            ||      
     @_1@           ||            ||      
    @@_2@@          ||            ||      
   @@@_3@@@         ||            ||      
  @@@@_4@@@@        ||            ||      
 @@@@@_5@@@@@       ||            ||      
@@@@@@_6@@@@@@      ||            ||      
       A             B             C
      ||            ||            ||      
      ||            ||            ||      
    @@_2@@          ||            ||      
   @@@_3@@@         ||            ||      
  @@@@_4@@@@        ||            ||      
 @@@@@_5@@@@@       ||            ||      
@@@@@@_6@@@@@@      ||           @_1@     
       A             B             C
--snip--
      ||            ||            ||      
      ||            ||            ||      
      ||            ||            ||      
      ||            ||            ||      
      ||          @@_2@@          ||      
     @_1@        @@@_3@@@         ||      
@@@@@@_6@@@@@@  @@@@_4@@@@   @@@@@_5@@@@@ 
--snip--
       A             B             C
      ||            ||            ||      
      ||           @_1@           ||      
      ||          @@_2@@          ||      
      ||         @@@_3@@@         ||      
      ||        @@@@_4@@@@        ||      
      ||       @@@@@_5@@@@@       ||      
      ||      @@@@@@_6@@@@@@      ||      
       A             B             C

import sys
# Create the image (make sure it's rectangular!)
im = [list('..########################...........'), # ❶
      list('..#......................#...#####...'),
      list('..#..........########....#####...#...'),
      list('..#..........#......#............#...'),
      list('..#..........########.........####...'),
      list('..######......................#......'),
      list('.......#..#####.....###########......'),
      list('.......####...#######................')]
HEIGHT = len(im)
WIDTH = len(im[0])
def floodFill(image, x, y, newChar, oldChar=None):
    if oldChar == None:
        # oldChar defaults to the character at x, y.
        oldChar = image[y][x] # ❷
    if oldChar == newChar or image[y][x] != oldChar:
        # BASE CASE
        return
    image[y][x] = newChar # Change the character.
    # Uncomment to view each step:
    #printImage(image)
    # Change the neighboring characters.
    if y + 1 < HEIGHT and image[y + 1][x] == oldChar:
        # RECURSIVE CASE
        floodFill(image, x, y + 1, newChar, oldChar) # ❸
    if y - 1 >= 0 and image[y - 1][x] == oldChar:
        # RECURSIVE CASE
        floodFill(image, x, y - 1, newChar, oldChar) # ❹
    if x + 1 < WIDTH and image[y][x + 1] == oldChar:
        # RECURSIVE CASE
        floodFill(image, x + 1, y, newChar, oldChar) # ❺
    if x - 1 >= 0 and image[y][x - 1] == oldChar:
        # RECURSIVE CASE
        floodFill(image, x - 1, y, newChar, oldChar) # ❻
    return # BASE CASE # ❼
def printImage(image):
    for y in range(HEIGHT):
        # Print each row.
        for x in range(WIDTH):
            # Print each column.
            sys.stdout.write(image[y][x])
        sys.stdout.write('\n')
    sys.stdout.write('\n')
printImage(im)
floodFill(im, 3, 3, 'o')
printImage(im)

<script type="text/javascript">
// Create the image (make sure it's rectangular!)
var im = ["..########################...........".split(""), // ❶
          "..#......................#...#####...".split(""),
          "..#..........########....#####...#...".split(""),
          "..#..........#......#............#...".split(""),
          "..#..........########.........####...".split(""),
          "..######......................#......".split(""),
          ".......#..#####.....###########......".split(""),
          ".......####...#######................".split("")];
var HEIGHT = im.length;
var WIDTH = im[0].length;
function floodFill(image, x, y, newChar, oldChar) {
    if (oldChar === undefined) {
        // oldChar defaults to the character at x, y.
        oldChar = image[y][x]; // ❷
    }
    if ((oldChar == newChar) || (image[y][x] != oldChar)) {
        // BASE CASE
        return;
    }
    image[y][x] = newChar; // Change the character.
    // Uncomment to view each step:
    //printImage(image);
    // Change the neighboring characters.
    if ((y + 1 < HEIGHT) && (image[y + 1][x] == oldChar)) {
        // RECURSIVE CASE
        floodFill(image, x, y + 1, newChar, oldChar); // ❸
    }
    if ((y - 1 >= 0) && (image[y - 1][x] == oldChar)) {
        // RECURSIVE CASE
        floodFill(image, x, y - 1, newChar, oldChar); // ❹
    }
    if ((x + 1 < WIDTH) && (image[y][x + 1] == oldChar)) {
        // RECURSIVE CASE
        floodFill(image, x + 1, y, newChar, oldChar); // ❺
    }
    if ((x - 1 >= 0) && (image[y][x - 1] == oldChar)) {
        // RECURSIVE CASE
        floodFill(image, x - 1, y, newChar, oldChar); // ❻
    }
    return; // BASE CASE # ❼
}
function printImage(image) {
    document.write("<pre>");
    for (var y = 0; y < HEIGHT; y++) {
        // Print each row.
        for (var x = 0; x < WIDTH; x++) {
            // Print each column.
            document.write(image[y][x]);
        }
        document.write("\n");
    }
    document.write("\n</ pre>");
}
printImage(im);
floodFill(im, 3, 3, "o");
printImage(im);
</script>

..########################...........
..#......................#...#####...
..#..........########....#####...#...
..#..........#......#............#...
..#..........########.........####...
..######......................#......
.......#..#####.....###########......
.......####...#######................
..########################...........
..#oooooooooooooooooooooo#...#####...
..#oooooooooo########oooo#####ooo#...
..#oooooooooo#......#oooooooooooo#...
..#oooooooooo########ooooooooo####...
..######oooooooooooooooooooooo#......
.......#oo#####ooooo###########......
.......####...#######................

def ackermann(m, n, indentation=None):
    if indentation is None:
        indentation = 0
    print('%sackermann(%s, %s)' % (' ' * indentation, m, n))
    if m == 0:
        # BASE CASE
        return n + 1
    elif m > 0 and n == 0:
        # RECURSIVE CASE
 return ackermann(m - 1, 1, indentation + 1)
    elif m > 0 and n > 0:
        # RECURSIVE CASE
        return ackermann(m - 1, ackermann(m, n - 1, indentation + 1), indentation + 1)
print('Starting with m = 1, n = 1:')
print(ackermann(1, 1))
print('Starting with m = 2, n = 3:')
print(ackermann(2, 3))

<script type="text/javascript">
function ackermann(m, n, indentation) {
    if (indentation === undefined) {
        indentation = 0;
    }
    document.write(" ".repeat(indentation) + "ackermann(" + m + ", " + n + ")\n");
    if (m === 0) {
        // BASE CASE
        return n + 1;
    } else if ((m > 0) && (n === 0)) {
        // RECURSIVE CASE
        return ackermann(m - 1, 1, indentation + 1);
    } else if ((m > 0) && (n > 0)) {
        // RECURSIVE CASE
        return ackermann(m - 1, ackermann(m, n - 1, indentation + 1), indentation + 1);
    }
}
document.write("<pre>");
document.write("Starting with m = 1, n = 1:<br />");
document.write(ackermann(1, 1) + "<br />");
document.write("Starting with m = 2, n = 3:<br />");
document.write(ackermann(2, 3) + "<br />");
document.write("</pre>");
</script>

Starting with m = 1, n = 1:
ackermann(1, 1)
 ackermann(1, 0)
  ackermann(0, 1)
 ackermann(0, 2)
3
Starting with m = 2, n = 3:
ackermann(2, 3)
 ackermann(2, 2)
  ackermann(2, 1)
   ackermann(2, 0)
--snip--
    ackermann(0, 6)
   ackermann(0, 7)
  ackermann(0, 8)
9

...##########....................................
    ...#........#....####..................##########
    ...#........#....#..#...############...#........#
    ...##########....#..#...#..........#...##.......#
    .......#....#....####...#..........#....##......#
    .......#....#....#......############.....##.....#
    .......######....#........................##....#
    .................####........####..........######

root  = {'data': 'A', 'children': []}
node2 = {'data': 'B', 'children': []}
node3 = {'data': 'C', 'children': []}
node4 = {'data': 'D', 'children': []}
node5 = {'data': 'E', 'children': []}
node6 = {'data': 'F', 'children': []}
node7 = {'data': 'G', 'children': []}
node8 = {'data': 'H', 'children': []}
root['children'] = [node2, node3]
node2['children'] = [node4]
node3['children'] = [node5, node6]
node5['children'] = [node7, node8]

root = {'data': 'A', 'children': [{'data': 'B', 'children': 
[{'data': 'D', 'children': []}]}, {'data': 'C', 'children': 
[{'data': 'E', 'children': [{'data': 'G', 'children': []}, 
{'data': 'H', 'children': []}]}, {'data': 'F', 'children': []}]}]}

>>> root['children'][1]['data']
'C'
>>> root['children'][1]['children'][0]['data']
'E'

root = {'data': 'A', 'children': [{'data': 'B', 'children': 
[{'data': 'D', 'children': []}]}, {'data': 'C', 'children': 
[{'data': 'E', 'children': [{'data': 'G', 'children': []}, 
{'data': 'H', 'children': []}]}, {'data': 'F', 'children': []}]}]}
def preorderTraverse(node):
    print(node['data'], end=' ') # Access this node's data.
    if len(node['children']) > 0: # ❶
        # RECURSIVE CASE
        for child in node['children']:
            preorderTraverse(child) # Traverse child nodes.
    # BASE CASE
    return # ❷
preorderTraverse(root)

<script type="text/javascript">
root = {"data": "A", "children": [{"data": "B", "children": 
[{"data": "D", "children": []}]}, {"data": "C", "children": 
[{"data": "E", "children": [{"data": "G", "children": []}, 
{"data": "H", "children": []}]}, {"data": "F", "children": []}]}]};
function preorderTraverse(node) {
    document.write(node["data"] + " "); // Access this node's data.
    if (node["children"].length > 0) { // ❶
        // RECURSIVE CASE
        for (let i = 0; i < node["children"].length; i++) {
 preorderTraverse(node["children"][i]); // Traverse child nodes.
        }
    }
    // BASE CASE
    return; // ❷
}
preorderTraverse(root);
</script>

A B D C E G H F

root = {'data': 'A', 'children': [{'data': 'B', 'children': 
[{'data': 'D', 'children': []}]}, {'data': 'C', 'children': 
[{'data': 'E', 'children': [{'data': 'G', 'children': []}, 
{'data': 'H', 'children': []}]}, {'data': 'F', 'children': []}]}]}
def postorderTraverse(node):
    for child in node['children']:
        # RECURSIVE CASE
        postorderTraverse(child) # Traverse child nodes.
    print(node['data'], end=' ') # Access this node's data.
    # BASE CASE
    return
postorderTraverse(root)

<script type="text/javascript">
root = {"data": "A", "children": [{"data": "B", "children": 
[{"data": "D", "children": []}]}, {"data": "C", "children": 
[{"data": "E", "children": [{"data": "G", "children": []}, 
{"data": "H", "children": []}]}, {"data": "F", "children": []}]}]};
function postorderTraverse(node) {
    for (let i = 0; i < node["children"].length; i++) {
        // RECURSIVE CASE
        postorderTraverse(node["children"][i]); // Traverse child nodes.
    }
    document.write(node["data"] + " "); // Access this node's data.
    // BASE CASE
    return;
}
postorderTraverse(root);
</script>

D B G H E F C A

root = {'data': 'A', 'children': [{'data': 'B', 'children': 
[{'data': 'D', 'children': []}]}, {'data': 'C', 'children': 
[{'data': 'E', 'children': [{'data': 'G', 'children': []}, 
{'data': 'H', 'children': []}]}, {'data': 'F', 'children': []}]}]}
def inorderTraverse(node):
    if len(node['children']) >= 1:
        # RECURSIVE CASE
 inorderTraverse(node['children'][0]) # Traverse the left child.
    print(node['data'], end=' ') # Access this node's data.
    if len(node['children']) >= 2:
        # RECURSIVE CASE
        inorderTraverse(node['children'][1]) # Traverse the right child.
    # BASE CASE
    return
inorderTraverse(root)

<script type="text/javascript">
root = {"data": "A", "children": [{"data": "B", "children": 
[{"data": "D", "children": []}]}, {"data": "C", "children": 
[{"data": "E", "children": [{"data": "G", "children": []}, 
{"data": "H", "children": []}]}, {"data": "F", "children": []}]}]};
function inorderTraverse(node) {
    if (node["children"].length >= 1) {
        // RECURSIVE CASE
        inorderTraverse(node["children"][0]); // Traverse the left child.
    }
    document.write(node["data"] + " "); // Access this node's data.
    if (node["children"].length >= 2) {
        // RECURSIVE CASE
        inorderTraverse(node["children"][1]); // Traverse the right child.
    }
    // BASE CASE
    return;
}
inorderTraverse(root);
</script>

D B A G E H C F

root = {'name': 'Alice', 'children': [{'name': 'Bob', 'children': 
[{'name': 'Darya', 'children': []}]}, {'name': 'Caroline', 
'children': [{'name': 'Eve', 'children': [{'name': 'Gonzalo', 
'children': []}, {'name': 'Hadassah', 'children': []}]}, {'name': 'Fred', 'children': []}]}]}
def find8LetterName(node):
    print(' Visiting node ' + node['name'] + '...')
    # Preorder depth-first search:
    print('Checking if ' + node['name'] + ' is 8 letters...')
    if len(node['name']) == 8: return node['name'] # BASE CASE # ❶
    if len(node['children']) > 0:
        # RECURSIVE CASE
        for child in node['children']:
            returnValue = find8LetterName(child)
            if returnValue != None:
                return returnValue
 # Postorder depth-first search:
    #print('Checking if ' + node['name'] + ' is 8 letters...')
    #if len(node['name']) == 8: return node['name'] # BASE CASE # ❷
    # Value was not found or there are no children.
    return None # BASE CASE
print('Found an 8-letter name: ' + str(find8LetterName(root)))

<script type="text/javascript">
root = {'name': 'Alice', 'children': [{'name': 'Bob', 'children': 
[{'name': 'Darya', 'children': []}]}, {'name': 'Caroline', 
'children': [{'name': 'Eve', 'children': [{'name': 'Gonzalo', 
'children': []}, {'name': 'Hadassah', 'children': []}]}, {'name': 'Fred', 'children': []}]}]};
function find8LetterName(node, value) {
    document.write("Visiting node " + node.name + "...<br />");
    // Preorder depth-first search:
    document.write("Checking if " + node.name + " is 8 letters...<br />");
    if (node.name.length === 8) return node.name; // BASE CASE // ❶
    if (node.children.length > 0) {
        // RECURSIVE CASE
        for (let child of node.children) {
            let returnValue = find8LetterName(child);
            if (returnValue != null) {
                return returnValue;
            }
        }
    }
    // Postorder depth-first search:
    document.write("Checking if " + node.name + " is 8 letters...<br />");
    //if (node.name.length === 8) return node.name; // BASE CASE // ❷
    // Value was not found or there are no children.
    return null; // BASE CASE
}
document.write("Found an 8-letter name: " + find8LetterName(root));
</script>

Visiting node Alice...
Checking if Alice is 8 letters...
Visiting node Bob...
Checking if Bob is 8 letters...
Visiting node Darya...
Checking if Darya is 8 letters...
Visiting node Caroline...
Checking if Caroline is 8 letters...
Found an 8-letter name: Caroline

Visiting node Alice...
Visiting node Bob...
Visiting node Darya...
Checking if Darya is 8 letters...
Checking if Bob is 8 letters...
Visiting node Caroline...
Visiting node Eve...
Visiting node Gonzalo...
Checking if Gonzalo is 8 letters...
Visiting node Hadassah...
Checking if Hadassah is 8 letters...
Found an 8-letter name: Hadassah

root = {'data': 'A', 'children': [{'data': 'B', 'children': 
[{'data': 'D', 'children': []}]}, {'data': 'C', 'children': 
[{'data': 'E', 'children': [{'data': 'G', 'children': []}, 
{'data': 'H', 'children': []}]}, {'data': 'F', 'children': []}]}]}
def getDepth(node):
    if len(node['children']) == 0:
        # BASE CASE
        return 0
    else:
        # RECURSIVE CASE
        maxChildDepth = 0
        for child in node['children']:
            # Find the depth of each child node:
            childDepth = getDepth(child)
            if childDepth > maxChildDepth:
                # This child is deepest child node found so far:
                maxChildDepth = childDepth
        return maxChildDepth + 1
print('Depth of tree is ' + str(getDepth(root)))

<script type="text/javascript">
root = {"data": "A", "children": [{"data": "B", "children": 
[{"data": "D", "children": []}]}, {"data": "C", "children": 
[{"data": "E", "children": [{"data": "G", "children": []}, 
{"data": "H", "children": []}]}, {"data": "F", "children": []}]}]};
function getDepth(node) {
    if (node.children.length === 0) {
        // BASE CASE
        return 0;
    } else {
        // RECURSIVE CASE
        let maxChildDepth = 0;
        for (let child of node.children) {
            // Find the depth of each child node:
 let childDepth = getDepth(child);
            if (childDepth > maxChildDepth) {
                // This child is deepest child node found so far:
                maxChildDepth = childDepth;
            }
        }
        return maxChildDepth + 1;
    }
}
document.write("Depth of tree is " + getDepth(root) + "<br />");
</script>

Depth of tree is 3

# Create the maze data structure:
# You can copy-paste this from inventwithpython.com/examplemaze.txt
MAZE = """
#######################################################################
#S#                 #       # #   #     #         #     #   #         #
# ##### ######### # ### ### # # # # ### # # ##### # ### # # ##### # ###
# #   #     #     #     #   # # #   # #   # #       # # # #     # #   #
# # # ##### # ########### ### # ##### ##### ######### # # ##### ### # #
#   #     # # #     #   #   #   #         #       #   #   #   #   # # #
######### # # # ##### # ### # ########### ####### # # ##### ##### ### #
#       # # # #     # #     # #   #   #   #     # # #   #         #   #
# # ##### # # ### # # ####### # # # # # # # ##### ### ### ######### # #
# # #   # # #   # # #     #     #   #   #   #   #   #     #         # #
### # # # # ### # # ##### ####### ########### # ### # ##### ##### ### #
#   # #   # #   # #     #   #     #       #   #     # #     #     #   #
# ### ####### ##### ### ### ####### ##### # ######### ### ### ##### ###
#   #         #     #     #       #   # #   # #     #   # #   # #   # #
### ########### # ####### ####### ### # ##### # # ##### # # ### # ### #
#   #   #       # #     #   #   #     #       # # #     # # #   # #   #
# ### # # ####### # ### ##### # ####### ### ### # # ####### # # # ### #
#     #         #     #       #           #     #           # #      E#
#######################################################################
""".split('\n')
# Constants used in this program:
EMPTY = ' '
START = 'S'
EXIT = 'E'
PATH = '.'
# Get the height and width of the maze:
HEIGHT = len(MAZE)
WIDTH = 0
for row in MAZE: # Set WIDTH to the widest row's width.
    if len(row) > WIDTH:
        WIDTH = len(row)
# Make each row in the maze a list as wide as the WIDTH:
for i in range(len(MAZE)):
    MAZE[i] = list(MAZE[i])
    if len(MAZE[i]) != WIDTH:
        MAZE[i] = [EMPTY] * WIDTH # Make this a blank row.
def printMaze(maze):
    for y in range(HEIGHT):
        # Print each row.
        for x in range(WIDTH):
            # Print each column in this row.
            print(maze[y][x], end='')
        print() # Print a newline at the end of the row.
    print()
def findStart(maze):
    for x in range(WIDTH):
        for y in range(HEIGHT):
            if maze[y][x] == START:
                return (x, y) # Return the starting coordinates.
def solveMaze(maze, x=None, y=None, visited=None):
    if x == None or y == None:
        x, y = findStart(maze)
        maze[y][x] = EMPTY # Get rid of the 'S' from the maze.
    if visited == None:
        visited = [] # Create a new list of visited points.  # ❶
    if maze[y][x] == EXIT:
         return True # Found the exit, return True.
    maze[y][x] = PATH # Mark the path in the maze.
    visited.append(str(x) + ',' + str(y))  # ❷
    #printMaze(maze) # Uncomment to view each forward step. # ❸
    # Explore the north neighboring point:
    if y + 1 < HEIGHT and maze[y + 1][x] in (EMPTY, EXIT) and \
    str(x) + ',' + str(y + 1) not in visited:
        # RECURSIVE CASE
        if solveMaze(maze, x, y + 1, visited):
            return True # BASE CASE
    # Explore the south neighboring point:
    if y - 1 >= 0 and maze[y - 1][x] in (EMPTY, EXIT) and \
    str(x) + ',' + str(y - 1) not in visited:
        # RECURSIVE CASE
        if solveMaze(maze, x, y - 1, visited):
            return True # BASE CASE
 # Explore the east neighboring point:
    if x + 1 < WIDTH and maze[y][x + 1] in (EMPTY, EXIT) and \
    str(x + 1) + ',' + str(y) not in visited:
        # RECURSIVE CASE
        if solveMaze(maze, x + 1, y, visited):
            return True # BASE CASE
    # Explore the west neighboring point:
    if x - 1 >= 0 and maze[y][x - 1] in (EMPTY, EXIT) and \
    str(x - 1) + ',' + str(y) not in visited:
        # RECURSIVE CASE
        if solveMaze(maze, x - 1, y, visited):
            return True # BASE CASE
    maze[y][x] = EMPTY # Reset the empty space.
    #printMaze(maze) # Uncomment to view each backtrack step. # ❹
    return False # BASE CASE
printMaze(MAZE)
solveMaze(MAZE)
printMaze(MAZE)

<script type="text/javascript">
// Create the maze data structure:
// You can copy-paste this from inventwithpython.com/examplemaze.txt
let MAZE = `
#######################################################################
#S#                 #       # #   #     #         #     #   #         #
# ##### ######### # ### ### # # # # ### # # ##### # ### # # ##### # ###
# #   #     #     #     #   # # #   # #   # #       # # # #     # #   #
# # # ##### # ########### ### # ##### ##### ######### # # ##### ### # #
#   #     # # #     #   #   #   #         #       #   #   #   #   # # #
######### # # # ##### # ### # ########### ####### # # ##### ##### ### #
#       # # # #     # #     # #   #   #   #     # # #   #         #   #
# # ##### # # ### # # ####### # # # # # # # ##### ### ### ######### # #
# # #   # # #   # # #     #     #   #   #   #   #   #     #         # #
### # # # # ### # # ##### ####### ########### # ### # ##### ##### ### #
#   # #   # #   # #     #   #     #       #   #     # #     #     #   #
# ### ####### ##### ### ### ####### ##### # ######### ### ### ##### ###
#   #         #     #     #       #   # #   # #     #   # #   # #   # #
### ########### # ####### ####### ### # ##### # # ##### # # ### # ### #
#   #   #       # #     #   #   #     #       # # #     # # #   # #   #
# ### # # ####### # ### ##### # ####### ### ### # # ####### # # # ### #
#     #         #     #       #           #     #           # #      E#
#######################################################################
`.split("\n");
// Constants used in this program:
const EMPTY = " ";
const START = "S";
const EXIT = "E";
const PATH = ".";
// Get the height and width of the maze:
const HEIGHT = MAZE.length;
let maxWidthSoFar = MAZE[0].length;
for (let row of MAZE) { // Set WIDTH to the widest row's width.
    if (row.length > maxWidthSoFar) {
        maxWidthSoFar = row.length;
    }
}
const WIDTH = maxWidthSoFar;
// Make each row in the maze a list as wide as the WIDTH:
for (let i = 0; i < MAZE.length; i++) {
    MAZE[i] = MAZE[i].split("");
    if (MAZE[i].length !== WIDTH) {
        MAZE[i] = EMPTY.repeat(WIDTH).split(""); // Make this a blank row.
    }
}
function printMaze(maze) {
    document.write("<pre>");
    for (let y = 0; y < HEIGHT; y++) {
        // Print each row.
        for (let x = 0; x < WIDTH; x++) {
            // Print each column in this row.
            document.write(maze[y][x]);
        }
        document.write("\n"); // Print a newline at the end of the row.
    }
    document.write("\n</ pre>");
}
function findStart(maze) {
    for (let x = 0; x < WIDTH; x++) {
        for (let y = 0; y < HEIGHT; y++) {
            if (maze[y][x] === START) {
                return [x, y]; // Return the starting coordinates.
            }
        }
    }
}
function solveMaze(maze, x, y, visited) {
    if (x === undefined || y === undefined) {
        [x, y] = findStart(maze);
        maze[y][x] = EMPTY; // Get rid of the 'S' from the maze.
    }
    if (visited === undefined) {
        visited = []; // Create a new list of visited points. // ❶
    }
    if (maze[y][x] == EXIT) {
         return true; // Found the exit, return true.
    }
    maze[y][x] = PATH; // Mark the path in the maze.
    visited.push(String(x) + "," + String(y));  // ❷
   //printMaze(maze) // Uncomment to view each forward step. # ❸
    // Explore the north neighboring point:
    if ((y + 1 < HEIGHT) && ((maze[y + 1][x] == EMPTY) || 
    (maze[y + 1][x] == EXIT)) && 
    (visited.indexOf(String(x) + "," + String(y + 1)) === -1)) {
        // RECURSIVE CASE
        if (solveMaze(maze, x, y + 1, visited)) {
            return true; // BASE CASE
        }
    }
    // Explore the south neighboring point:
    if ((y - 1 >= 0) && ((maze[y - 1][x] == EMPTY) || 
    (maze[y - 1][x] == EXIT)) && 
    (visited.indexOf(String(x) + "," + String(y - 1)) === -1)) {
        // RECURSIVE CASE
        if (solveMaze(maze, x, y - 1, visited)) {
            return true; // BASE CASE
        }
    }
    // Explore the east neighboring point:
    if ((x + 1 < WIDTH) && ((maze[y][x + 1] == EMPTY) || 
    (maze[y][x + 1] == EXIT)) && 
    (visited.indexOf(String(x + 1) + "," + String(y)) === -1)) {
        // RECURSIVE CASE
        if (solveMaze(maze, x + 1, y, visited)) {
            return true; // BASE CASE
        }
    }
    // Explore the west neighboring point:
    if ((x - 1 >= 0) && ((maze[y][x - 1] == EMPTY) || 
    (maze[y][x - 1] == EXIT)) && 
    (visited.indexOf(String(x - 1) + "," + String(y)) === -1)) {
        // RECURSIVE CASE
        if (solveMaze(maze, x - 1, y, visited)) {
            return true; // BASE CASE
        }
    }
    maze[y][x] = EMPTY; // Reset the empty space.
    //printMaze(maze); // Uncomment to view each backtrack step. # ❹
    return false; // BASE CASE
}
printMaze(MAZE);
solveMaze(MAZE);
printMaze(MAZE);
</script>