递归的递归之书：第五章到第九章

def binarySearch(needle, haystack, left=None, right=None):
    # By default, `left` and `right` are all of `haystack`:
    if left is None:
        left = 0 # `left` defaults to the 0 index.
    if right is None:
        right = len(haystack) - 1 # `right` defaults to the last index.
    print('Searching:', haystack[left:right + 1])
    if left > right: # BASE CASE
         return None # The `needle` is not in `haystack`.
    mid = (left + right) // 2
    if needle == haystack[mid]: # BASE CASE
         return mid # The `needle` has been found in `haystack`
    elif needle < haystack[mid]: # RECURSIVE CASE
         return binarySearch(needle, haystack, left, mid - 1)
    elif needle > haystack[mid]: # RECURSIVE CASE
         return binarySearch(needle, haystack, mid + 1, right)
print(binarySearch(13, [1, 4, 8, 11, 13, 16, 19, 19]))

<script type="text/javascript">
function binarySearch(needle, haystack, left, right) {
    // By default, `left` and `right` are all of `haystack`:
    if (left === undefined) {
        left = 0; // `left` defaults to the 0 index.
    }
    if (right === undefined) {
        right = haystack.length - 1; // `right` defaults to the last index.
    }
 document.write("Searching: [" + 
    haystack.slice(left, right + 1).join(", ") + "]<br />");
    if (left > right) { // BASE CASE
         return null; // The `needle` is not in `haystack`.
    }
    let mid = Math.floor((left + right) / 2);
    if (needle == haystack[mid]) { // BASE CASE
         return mid; // The `needle` has been found in `haystack`.
    } else if (needle < haystack[mid]) { // RECURSIVE CASE
         return binarySearch(needle, haystack, left, mid - 1);
    } else if (needle > haystack[mid]) { // RECURSIVE CASE
         return binarySearch(needle, haystack, mid + 1, right);
    }
}
document.write(binarySearch(13, [1, 4, 8, 11, 13, 16, 19, 19]));
</script>

Searching: [1, 4, 8, 11, 13, 16, 19, 19]
Searching: [13, 16, 19, 19]
Searching: [13]
4

def quicksort(items, left=None, right=None):
    # By default, `left` and `right` span the entire range of `items`:
    if left is None:
        left = 0 # `left` defaults to the 0 index.
    if right is None:
        right = len(items) - 1 # `right` defaults to the last index.
 print('\nquicksort() called on this range:', items[left:right + 1])
    print('................The full list is:', items)
    if right <= left: # ❶
        # With only zero or one item, `items` is already sorted.
        return  # BASE CASE
    # START OF THE PARTITIONING
    i = left # i starts at the left end of the range. ❷
    pivotValue = items[right] # Select the last value for the pivot.
    print('....................The pivot is:', pivotValue)
    # Iterate up to, but not including, the pivot:
    for j in range(left, right):
        # If a value is less than the pivot, swap it so that it's on the
        # left side of `items`:
        if items[j] <= pivotValue:
            # Swap these two values:
            items[i], items[j] = items[j], items[i] ❸
            i += 1
    # Put the pivot on the left side of `items`:
    items[i], items[right] = items[right], items[i]
    # END OF THE PARTITIONING
    print('....After swapping, the range is:', items[left:right + 1])
    print('Recursively calling quicksort on:', items[left:i], 'and', items[i + 1:right + 1])
    # Call quicksort() on the two partitions:
    quicksort(items, left, i - 1)   # RECURSIVE CASE
    quicksort(items, i + 1, right)  # RECURSIVE CASE
myList = [0, 7, 6, 3, 1, 2, 5, 4]
quicksort(myList)
print(myList)

<script type="text/javascript">
function quicksort(items, left, right) {
    // By default, `left` and `right` span the entire range of `items`:
    if (left === undefined) {
        left = 0; // `left` defaults to the 0 index.
    }
    if (right === undefined) {
        right = items.length - 1; // `right` defaults to the last index.
    }
    document.write("<br /><pre>quicksort() called on this range: [" + 
    items.slice(left, right + 1).join(", ") + "]</pre>");
    document.write("<pre>................The full list is: [" + items.join(", ") + "]</pre>");
    if (right <= left) { // ❶
        // With only zero or one item, `items` is already sorted.
 return; // BASE CASE
    }
    // START OF THE PARTITIONING
    let i = left; ❷ // i starts at the left end of the range.
    let pivotValue = items[right]; // Select the last value for the pivot.
    document.write("<pre>....................The pivot is: " + pivotValue.toString() + 
"</pre>");
    // Iterate up to, but not including, the pivot:
    for (let j = left; j < right; j++) {
        // If a value is less than the pivot, swap it so that it's on the
        // left side of `items`:
        if (items[j] <= pivotValue) {
            // Swap these two values:
            [items[i], items[j]] = [items[j], items[i]]; ❸
            i++;
        }
    }
    // Put the pivot on the left side of `items`:
    [items[i], items[right]] = [items[right], items[i]];
    // END OF THE PARTITIONING
    document.write("<pre>....After swapping, the range is: [" + items.slice(left, right + 1).join(", ") + "]</pre>");
    document.write("<pre>Recursively calling quicksort on: [" + items.slice(left, i).join(", ") + "] and [" + items.slice(i + 1, right + 1).join(", ") + "]</pre>");
    // Call quicksort() on the two partitions:
    quicksort(items, left, i - 1); // RECURSIVE CASE
    quicksort(items, i + 1, right); // RECURSIVE CASE
}
let myList = [0, 7, 6, 3, 1, 2, 5, 4];
quicksort(myList);
document.write("<pre>[" + myList.join(", ") + "]</pre>");
</script>

items:   [0, 7, 6, 3, 1, 2, 5, 4]
indices:  0  1  2  3  4  5  6  7
          ^
i = 0     i
j = 0     j

items:   [0, 7, 6, 3, 1, 2, 5, 4]
indices:  0  1  2  3  4  5  6  7
             ^
i = 1        i
j = 1        j

items:   [0, 7, 6, 3, 1, 2, 5, 4]
indices:  0  1  2  3  4  5  6  7
             ^
i = 1        i  ^
j = 2           j

items:   [0, 7, 6, 3, 1, 2, 5, 4]
indices:  0  1  2  3  4  5  6  7
             ^
i = 1        i     ^
j = 3              j

items:   [0, 3, 6, 7, 1, 2, 5, 4]
indices:  0  1  2  3  4  5  6  7
                ^
i = 2           i     ^
j = 4                 j

items:   [0, 3, 1, 7, 6, 2, 5, 4]
indices:  0  1  2  3  4  5  6  7
                   ^
i = 3              i     ^
j = 5                    j

items:   [0, 3, 1, 2, 6, 7, 5, 4]
indices:  0  1  2  3  4  5  6  7
                      ^
i = 4                 i     ^
j = 6                       j

items:   [0, 3, 1, 2, 6, 7, 5, 4]
indices:  0  1  2  3  4  5  6  7
                      ^
i = 4                 i        ^
j = 7                          j

items:   [0, 3, 1, 2, 4, 7, 5, 6]
indices:  0  1  2  3  4  5  6  7
                      ^
i = 4                 i        ^
j = 7                          j

quicksort() called on this range: [0, 7, 6, 3, 1, 2, 5, 4]
................The full list is: [0, 7, 6, 3, 1, 2, 5, 4]
....................The pivot is: 4
....After swapping, the range is: [0, 3, 1, 2, 4, 7, 5, 6]
Recursively calling quicksort on: [0, 3, 1, 2] and [7, 5, 6]
quicksort() called on this range: [0, 3, 1, 2]
................The full list is: [0, 3, 1, 2, 4, 7, 5, 6]
....................The pivot is: 2
....After swapping, the range is: [0, 1, 2, 3]
Recursively calling quicksort on: [0, 1] and [3]
quicksort() called on this range: [0, 1]
................The full list is: [0, 1, 2, 3, 4, 7, 5, 6]
....................The pivot is: 1
....After swapping, the range is: [0, 1]
Recursively calling quicksort on: [0] and []
quicksort() called on this range: [0]
................The full list is: [0, 1, 2, 3, 4, 7, 5, 6]
quicksort() called on this range: []
................The full list is: [0, 1, 2, 3, 4, 7, 5, 6]
quicksort() called on this range: [3]
................The full list is: [0, 1, 2, 3, 4, 7, 5, 6]
quicksort() called on this range: [7, 5, 6]
................The full list is: [0, 1, 2, 3, 4, 7, 5, 6]
....................The pivot is: 6
....After swapping, the range is: [5, 6, 7]
Recursively calling quicksort on: [5] and [7]
quicksort() called on this range: [5]
................The full list is: [0, 1, 2, 3, 4, 5, 6, 7]
quicksort() called on this range: [7]
................The full list is: [0, 1, 2, 3, 4, 5, 6, 7]
Sorted: [0, 1, 2, 3, 4, 5, 6, 7]

import math
def mergeSort(items):
    print('.....mergeSort() called on:', items)
    # BASE CASE - Zero or one item is naturally sorted:
    if len(items) == 0 or len(items) == 1:
        return items # ❶
    # RECURSIVE CASE - Pass the left and right halves to mergeSort():
    # Round down if items doesn't divide in half evenly:
    iMiddle = math.floor(len(items) / 2) # ❷
    print('................Split into:', items[:iMiddle], 'and', items[iMiddle:])
    left = mergeSort(items[:iMiddle]) # ❸
    right = mergeSort(items[iMiddle:])
    # BASE CASE - Returned merged, sorted data:
    # At this point, left should be sorted and right should be
    # sorted. We can merge them into a single sorted list.
    sortedResult = []
    iLeft = 0
    iRight = 0
    while (len(sortedResult) < len(items)):
        # Append the smaller value to sortedResult.
        if left[iLeft] < right[iRight]: # ❹
            sortedResult.append(left[iLeft])
            iLeft += 1
        else:
            sortedResult.append(right[iRight])
            iRight += 1
        # If one of the pointers has reached the end of its list,
        # put the rest of the other list into sortedResult.
        if iLeft == len(left):
            sortedResult.extend(right[iRight:])
            break
        elif iRight == len(right):
            sortedResult.extend(left[iLeft:])
            break
    print('The two halves merged into:', sortedResult)
    return sortedResult # Returns a sorted version of items.
myList = [2, 9, 8, 5, 3, 4, 7, 6]
myList = mergeSort(myList)
print(myList)

<script type="text/javascript">
function mergeSort(items) {
    document.write("<pre>" + ".....mergeSort() called on: [" + 
    items.join(", ") + "]</pre>");
    // BASE CASE - Zero or one item is naturally sorted:
    if (items.length === 0 || items.length === 1) { // BASE CASE
        return items; // ❶
    }
    // RECURSIVE CASE - Pass the left and right halves to mergeSort():
    // Round down if items doesn't divide in half evenly:
    let iMiddle = Math.floor(items.length / 2); // ❷
    document.write("<pre>................Split into: [" + items.slice(0, iMiddle).join(", ") + 
    "] and [" + items.slice(iMiddle).join(", ") + "]</pre>");
    let left = mergeSort(items.slice(0, iMiddle)); // ❸
    let right = mergeSort(items.slice(iMiddle));
    // BASE CASE - Returned merged, sorted data:
    // At this point, left should be sorted and right should be
    // sorted. We can merge them into a single sorted list.
    let sortedResult = [];
    let iLeft = 0;
    let iRight = 0;
    while (sortedResult.length < items.length) {
        // Append the smaller value to sortedResult.
        if (left[iLeft] < right[iRight]) { // ❹
            sortedResult.push(left[iLeft]);
            iLeft++;
        } else {
            sortedResult.push(right[iRight]);
            iRight++;
        }
        // If one of the pointers has reached the end of its list,
        // put the rest of the other list into sortedResult.
        if (iLeft == left.length) {
            Array.prototype.push.apply(sortedResult, right.slice(iRight));
            break;
        } else if (iRight == right.length) {
            Array.prototype.push.apply(sortedResult, left.slice(iLeft));
            break;
        }
    }
    document.write("<pre>The two halves merged into: [" + sortedResult.join(", ") + 
    "]</pre>");
    return sortedResult; // Returns a sorted version of items.
}
let myList = [2, 9, 8, 5, 3, 4, 7, 6];
myList = mergeSort(myList);
document.write("<pre>[" + myList.join(", ") + "]</pre>");
</script>

sortedResult = []
      left: [2, 9]    right: [5, 8]
   indices:  0  1             0  1
 iLeft = 0   ^
iRight = 0                    ^

sortedResult = [2]
      left: [2, 9]    right: [5, 8]
   indices:  0  1             0  1
 iLeft = 1      ^
iRight = 0                    ^

sortedResult = [2, 5]
      left: [2, 9]    right: [5, 8]
 indices:  0  1             0  1
 iLeft = 1      ^
iRight = 1                       ^

sortedResult = [2, 5, 8]
      left: [2, 9]    right: [5, 8]
   indices:  0  1             0  1
 iLeft = 1      ^
iRight = 2                         ^

.....mergeSort() called on: [2, 9, 8, 5, 3, 4, 7, 6]
................Split into: [2, 9, 8, 5] and [3, 4, 7, 6]
.....mergeSort() called on: [2, 9, 8, 5]
................Split into: [2, 9] and [8, 5]
.....mergeSort() called on: [2, 9]
................Split into: [2] and [9]
.....mergeSort() called on: [2]
.....mergeSort() called on: [9]
The two halves merged into: [2, 9]
.....mergeSort() called on: [8, 5]
................Split into: [8] and [5]
.....mergeSort() called on: [8]
.....mergeSort() called on: [5]
The two halves merged into: [5, 8]
The two halves merged into: [2, 5, 8, 9]
.....mergeSort() called on: [3, 4, 7, 6]
................Split into: [3, 4] and [7, 6]
.....mergeSort() called on: [3, 4]
................Split into: [3] and [4]
.....mergeSort() called on: [3]
.....mergeSort() called on: [4]
The two halves merged into: [3, 4]
.....mergeSort() called on: [7, 6]
................Split into: [7] and [6]
.....mergeSort() called on: [7]
.....mergeSort() called on: [6]
The two halves merged into: [6, 7]
The two halves merged into: [3, 4, 6, 7]
The two halves merged into: [2, 3, 4, 5, 6, 7, 8, 9]
[2, 3, 4, 5, 6, 7, 8, 9]

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

<script type="text/javascript">
function sumDivConq(numbers) {
    if (numbers.length === 0) { // BASE CASE
        return 0; // ❶
    } else if (numbers.length === 1) { // BASE CASE
        return numbers[0]; // ❷
    } else { // RECURSIVE CASE
        let mid = Math.floor(numbers.length / 2); // ❸
        let leftHalfSum = sumDivConq(numbers.slice(0, mid));
        let rightHalfSum = sumDivConq(numbers.slice(mid, numbers.length + 1));
        return leftHalfSum + rightHalfSum; // ❹
    }
}
let nums = [1, 2, 3, 4, 5];
document.write('The sum of ' + nums + ' is ' + sumDivConq(nums) + "<br />");
nums = [5, 2, 4, 8];
document.write('The sum of ' + nums + ' is ' + sumDivConq(nums) + "<br />");
nums = [1, 10, 100, 1000];
document.write('The sum of ' + nums + ' is ' + sumDivConq(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

>>> x = 5678
>>> y = 1234
>>> product = 0
>>> for i in range(x):
...     product += y
...
>>> product
7006652

import math
# Create a lookup table of all single-digit multiplication products:
MULT_TABLE = {} # ❶
for i in range(10):
    for j in range(10):
 MULT_TABLE[(i, j)] = i * j
def padZeros(numberString, numZeros, insertSide):
    """Return a string padded with zeros on the left or right side."""
    if insertSide == 'left':
        return '0' * numZeros + numberString
    elif insertSide == 'right':
        return numberString + '0' * numZeros
def karatsuba(x, y):
    """Multiply two integers with the Karatsuba algorithm. Note that
    the * operator isn't used anywhere in this function."""
    assert isinstance(x, int), 'x must be an integer'
    assert isinstance(y, int), 'y must be an integer'
    x = str(x)
    y = str(y)
    # At single digits, look up the products in the multiplication table:
    if len(x) == 1 and len(y) == 1: # BASE CASE
        print('Lookup', x, '*', y, '=', MULT_TABLE[(int(x), int(y))])
        return MULT_TABLE[(int(x), int(y))]
    # RECURSIVE CASE
    print('Multiplying', x, '*', y)
    # Pad with prepended zeros so that x and y are the same length:
    if len(x) < len(y): # ❷
        # If x is shorter than y, pad x with zeros:
        x = padZeros(x, len(y) - len(x), 'left')
    elif len(y) < len(x):
        # If y is shorter than x, pad y with zeros:
        y = padZeros(y, len(x) - len(y), 'left')
    # At this point, x and y have the same length.
    halfOfDigits = math.floor(len(x) / 2) # ❸
    # Split x into halves a & b, split y into halves c & d:
    a = int(x[:halfOfDigits])
    b = int(x[halfOfDigits:])
    c = int(y[:halfOfDigits])
    d = int(y[halfOfDigits:])
    # Make the recursive calls with these halves:
    step1Result = karatsuba(a, c) # ❹ # Step 1: Multiply a & c.
    step2Result = karatsuba(b, d) # Step 2: Multiply b & d.
    step3Result = karatsuba(a + b, c + d) # Step 3: Multiply a + b & c + d.
    # Step 4: Calculate Step 3 - Step 2 - Step 1:
    step4Result = step3Result - step2Result - step1Result # ❺
    # Step 5: Pad these numbers, then add them for the return value:
    step1Padding = (len(x) - halfOfDigits) + (len(x) - halfOfDigits)
    step1PaddedNum = int(padZeros(str(step1Result), step1Padding, 'right'))
    step4Padding = (len(x) - halfOfDigits)
 step4PaddedNum = int(padZeros(str(step4Result), step4Padding, 'right'))
    print('Solved', x, 'x', y, '=', step1PaddedNum + step2Result + step4PaddedNum)
    return step1PaddedNum + step2Result + step4PaddedNum # ❻
# Example: 1357 x 2468 = 3349076
print('1357 * 2468 =', karatsuba(1357, 2468))

<script type="text/javascript">
// Create a lookup table of all single-digit multiplication products:
let MULT_TABLE = {}; // ❶
for (let i = 0; i < 10; i++) {
    for (let j = 0; j < 10; j++) {
        MULT_TABLE[[i, j]] = i * j;
    }
}
function padZeros(numberString, numZeros, insertSide) {
    // Return a string padded with zeros on the left or right side.
    if (insertSide === "left") {
        return "0".repeat(numZeros) + numberString;
    } else if (insertSide === "right") {
        return numberString + "0".repeat(numZeros);
    }
}
function karatsuba(x, y) {
    // Multiply two integers with the Karatsuba algorithm. Note that
    // the * operator isn't used anywhere in this function.
    console.assert(Number.isInteger(x), "x must be an integer");
    console.assert(Number.isInteger(y), "y must be an integer");
    x = x.toString();
    y = y.toString();
    // At single digits, look up the products in the multiplication table:  
    if ((x.length === 1) && (y.length === 1)) { // BASE CASE
        document.write("Lookup " + x.toString() + " * " + y.toString() + " = " + 
        MULT_TABLE[[parseInt(x), parseInt(y)]] + "<br />");
        return MULT_TABLE[[parseInt(x), parseInt(y)]];
    }
    // RECURSIVE CASE
    document.write("Multiplying " + x.toString() + " * " + y.toString() + 
    "<br />");
    // Pad with prepended zeros so that x and y are the same length:
    if (x.length < y.length) { // ❷
        // If x is shorter than y, pad x with zeros:
        x = padZeros(x, y.length - x.length, "left");
    } else if (y.length < x.length) {
        // If y is shorter than x, pad y with zeros:
 y = padZeros(y, x.length - y.length, "left");
    }
    // At this point, x and y have the same length.
    let halfOfDigits = Math.floor(x.length / 2); // ❸
    // Split x into halves a & b, split y into halves c & d:
    let a = parseInt(x.substring(0, halfOfDigits));
    let b = parseInt(x.substring(halfOfDigits));
    let c = parseInt(y.substring(0, halfOfDigits));
    let d = parseInt(y.substring(halfOfDigits));
    // Make the recursive calls with these halves:
    let step1Result = karatsuba(a, c); // ❹ // Step 1: Multiply a & c.
    let step2Result = karatsuba(b, d); // Step 2: Multiply b & d.
    let step3Result = karatsuba(a + b, c + d); // Step 3: Multiply a + b & c + d.
    // Step 4: Calculate Step 3 - Step 2 - Step 1:
    let step4Result = step3Result - step2Result - step1Result; // ❺
    // Step 5: Pad these numbers, then add them for the return value:
    let step1Padding = (x.length - halfOfDigits) + (x.length - halfOfDigits);
    let step1PaddedNum = parseInt(padZeros(step1Result.toString(), step1Padding, "right"));
    let step4Padding = (x.length - halfOfDigits);
    let step4PaddedNum = parseInt(padZeros((step4Result).toString(), step4Padding, "right"));
    document.write("Solved " + x + " x " + y + " = " + 
    (step1PaddedNum + step2Result + step4PaddedNum).toString() + "<br />");
    return step1PaddedNum + step2Result + step4PaddedNum; // ❻
}
// Example: 1357 x 2468 = 3349076
document.write("1357 * 2468 = " + karatsuba(1357, 2468).toString() + "<br />");
</script>

Multiplying 1357 * 2468
Multiplying 13 * 24
Lookup 1 * 2 = 2
Lookup 3 * 4 = 12
Lookup 4 * 6 = 24
Solved 13 * 24 = 312
Multiplying 57 * 68
Lookup 5 * 6 = 30
Lookup 7 * 8 = 56
Multiplying 12 * 14
Lookup 1 * 1 = 1
Lookup 2 * 4 = 8
Lookup 3 * 5 = 15
Solved 12 * 14 = 168
Solved 57 * 68 = 3876
Multiplying 70 * 92
Lookup 7 * 9 = 63
Lookup 0 * 2 = 0
Multiplying 7 * 11
Lookup 0 * 1 = 0
Lookup 7 * 1 = 7
Lookup 7 * 2 = 14
Solved 07 * 11 = 77
Solved 70 * 92 = 6440
Solved 1357 * 2468 = 3349076
1357 * 2468 = 3349076

def getPerms(chars, indent=0):
    print('.' * indent + 'Start of getPerms("' + chars + '")')
    if len(chars) == 1: # ❶
        # BASE CASE
        print('.' * indent + 'When chars = "' + chars + '" base case returns', chars)
        return [chars]
    # RECURSIVE CASE
    permutations = []
    head = chars[0] # ❷
    tail = chars[1:]
 tailPermutations = getPerms(tail, indent + 1)
    for tailPerm in tailPermutations: # ❸
        print('.' * indent + 'When chars =', chars, 'putting head', head, 'in all places in', tailPerm)
        for i in range(len(tailPerm) + 1): # ❹
            newPerm = tailPerm[0:i] + head + tailPerm[i:]
            print('.' * indent + 'New permutation:', newPerm)
            permutations.append(newPerm)
    print('.' * indent + 'When chars =', chars, 'results are', permutations)
    return permutations
print('Permutations of "ABCD":')
print('Results:', ','.join(getPerms('ABCD')))

<script type="text/javascript">
function getPerms(chars, indent) {
    if (indent === undefined) {
        indent = 0;
    }
    document.write('.'.repeat(indent) + 'Start of getPerms("' + chars + '")<br />');
    if (chars.length === 1) { // ❶
        // BASE CASE
        document.write('.'.repeat(indent) + "When chars = \"" + chars + 
        "\" base case returns " + chars + "<br />");
        return [chars];
    }
    // RECURSIVE CASE
    let permutations = [];
    let head = chars[0]; // ❷
    let tail = chars.substring(1);
    let tailPermutations = getPerms(tail, indent + 1);
    for (tailPerm of tailPermutations) { // ❸
        document.write('.'.repeat(indent) + "When chars = " + chars + 
        " putting head " + head + " in all places in " + tailPerm + "<br />");
        for (let i = 0; i < tailPerm.length + 1; i++) { // ❹
            let newPerm = tailPerm.slice(0, i) + head + tailPerm.slice(i);
            document.write('.'.repeat(indent) + "New permutation: " + newPerm + "<br />");
            permutations.push(newPerm);
        }
    }
    document.write('.'.repeat(indent) + "When chars = " + chars + 
    " results are " + permutations + "<br />");
    return permutations;
}
document.write("<pre>Permutations of \"ABCD\":<br />");
document.write("Results: " + getPerms("ABCD") + "</pre>");
</script>

Permutations of "ABCD":
Start of getPerms("ABCD")
.Start of getPerms("BCD")
..Start of getPerms("CD")
...Start of getPerms("D")
...When chars = "D" base case returns D
..When chars = CD putting head C in all places in D
..New permutation: CD
..New permutation: DC
..When chars = CD results are ['CD', 'DC']
.When chars = BCD putting head B in all places in CD
.New permutation: BCD
.New permutation: CBD
.New permutation: CDB
.When chars = BCD putting head B in all places in DC
.New permutation: BDC
.New permutation: DBC
.New permutation: DCB
.When chars = BCD results are ['BCD', 'CBD', 'CDB', 'BDC', 'DBC', 'DCB']
# --snip--
When chars = ABCD putting head A in all places in DCB
New permutation: ADCB
New permutation: DACB
New permutation: DCAB
New permutation: DCBA
When chars = ABCD results are ['ABCD', 'BACD', 'BCAD', 'BCDA', 'ACBD', 'CABD', 'CBAD', 'CBDA', 'ACDB','CADB', 'CDAB', 'CDBA', 'ABDC', 'BADC', 'BDAC', 'BDCA', 'ADBC', 'DABC', 'DBAC', 'DBCA', 'ADCB', 'DACB', 'DCAB', 'DCBA']
Results: ABCD,BACD,BCAD,BCDA,ACBD,CABD,CBAD,CBDA,ACDB,CADB,CDAB,CDBA,ABDC,
BADC,BDAC,BDCA,ADBC,DABC,DBAC,DBCA,ADCB,DACB,DCAB,DCBA

for a in ['A', 'B', 'C', 'D', 'E']:
    for b in ['A', 'B', 'C', 'D', 'E']:
        for c in ['A', 'B', 'C', 'D', 'E']:
            for d in ['A', 'B', 'C', 'D', 'E']:
                print(a, b, c, d)

<script>
for (a of ['A', 'B', 'C', 'D', 'E']) {
    for (b of ['A', 'B', 'C', 'D', 'E']) {
        for (c of ['A', 'B', 'C', 'D', 'E']) {
            for (d of ['A', 'B', 'C', 'D', 'E']) {
                document.write(a + b + c + d + "<br />")
            }
        }
    }
}
</script>

A A A A
A A A B
A A A C
A A A D
A A A E
A A B A
A A B B
# --snip--
E E E C
E E E D
E E E E

def getPermsWithRep(chars, permLength=None, prefix=''):
    indent = '.' * len(prefix)
    print(indent + 'Start, args=("' + chars + '", ' + str(permLength) + ', "' + prefix + '")')
    if permLength is None:
        permLength = len(chars)
    # BASE CASE
    if (permLength == 0): # ❶
        print(indent + 'Base case reached, returning', [prefix])
        return [prefix]
    # RECURSIVE CASE
    # Create a new prefix by adding each character to the current prefix.
    results = []
    print(indent + 'Adding each char to prefix "' + prefix + '".')
    for char in chars:
        newPrefix = prefix + char # ❷
        # Decrease permLength by one because we added one character to the prefix.
        results.extend(getPermsWithRep (chars, permLength - 1, newPrefix)) # ❸
    print(indent + 'Returning', results)
    return results
print('All permutations with repetition of JPB123:')
print(getPermsWithRep('JPB123', 4))

<script type="text/javascript">
function getPermsWithRep(chars, permLength, prefix) {
    if (permLength === undefined) {
        permLength = chars.length;
    }
    if (prefix === undefined) {
        prefix = "";
    }
    let indent = ".".repeat(prefix.length);
    document.write(indent + "Start, args=(\"" + chars + "\", " + permLength + 
    ", \"" + prefix + "\")<br />");
    // BASE CASE
    if (permLength === 0) { // ❶
        document.write(indent + "Base case reached, returning " + [prefix] + "<br />");
        return [prefix];
    }
    // RECURSIVE CASE
    // Create a new prefix by adding each character to the current prefix.
    let results = [];
    document.write(indent + "Adding each char to prefix \"" + prefix + "\".<br />");
    for (char of chars) {
        let newPrefix = prefix + char; // ❷
        // Decrease permLength by one because we added one character to the prefix.
        results = results.concat(getPermsWithRep(chars, permLength - 1, newPrefix)); // ❸
    }
    document.write(indent + "Returning " + results + "<br />");
    return results;
}
document.write("<pre>All permutations with repetition of JPB123:<br />");
document.write(getPermsWithRep('JPB123', 4) + "</pre>");
</script>

All permutations with repetition of JPB123:
Start, args=("JPB123", 4, "")
Adding each char to prefix "".
.Start, args=("JPB123", 3, "J")
.Adding each char to prefix "J".
..Start, args=("JPB123", 2, "JJ")
..Adding each char to prefix "JJ".
...Start, args=("JPB123", 1, "JJJ")
...Adding each char to prefix "JJJ".
....Start, args=("JPB123", 0, "JJJJ")
....Base case reached, returning ['JJJJ']
....Start, args=("JPB123", 0, "JJJP")
....Base case reached, returning ['JJJP']
# --snip--
Returning ['JJJJ', 'JJJP', 'JJJB', 'JJJ1', 'JJJ2', 'JJJ3', 
'JJPJ', 'JJPP', 'JJPB', 'JJP1', 'JJP2', 'JJP3', 'JJBJ', 'JJBP', 
'JJBB', 'JJB1', 'JJB2', 'JJB3', 'JJ1J', 'JJ1P', 'JJ1B', 'JJ11', 
'JJ12', 'JJ13', 'JJ2J', 'JJ2P', 'JJ2B', 'JJ21', 'JJ22', 'JJ23', 
'JJ3J', 'JJ3P', 'JJ3B', 'JJ31', 'JJ32', 'JJ33', 'JPJJ', 
# --snip--

def getCombos(chars, k, indent=0):
    debugMsg = '.' * indent + "In getCombos('" + chars + "', " + str(k) + ")"
    print(debugMsg + ', start.')
    if k == 0:
        # BASE CASE
        print(debugMsg + " base case returns ['']")
        # If k asks for 0-combinations, return '' as the selection of
        # zero letters from chars.
        return ['']
    elif chars == '':
        # BASE CASE
        print(debugMsg + ' base case returns []')
        return [] # A blank chars has no combinations, no matter what k is.
    # RECURSIVE CASE
    combinations = []
    # First part, get the combos that include the head: # ❶
    head = chars[:1]
    tail = chars[1:]
    print(debugMsg + " part 1, get combos with head '" + head + "'")
    tailCombos = getCombos(tail, k - 1, indent + 1) # ❷
    print('.' * indent + "Adding head '" + head + "' to tail combos:")
    for tailCombo in tailCombos:
        print('.' * indent + 'New combination', head + tailCombo)
        combinations.append(head + tailCombo)
    # Second part, get the combos that don't include the head: # ❸
    print(debugMsg + " part 2, get combos without head '" + head + "')")
    combinations.extend(getCombos(tail, k, indent + 1)) # ❹
    print(debugMsg + ' results are', combinations)
    return combinations
print('2-combinations of "ABC":')
print('Results:', getCombos('ABC', 2))

<script type="text/javascript">
function getCombos(chars, k, indent) {
    if (indent === undefined) {
        indent = 0;
    }
    let debugMsg = ".".repeat(indent) + "In getCombos('" + chars + "', " + k + ")";
    document.write(debugMsg + ", start.<br />");
    if (k == 0) {
        // BASE CASE
        document.write(debugMsg + " base case returns ['']<br />");
        // If k asks for 0-combinations, return '' as the selection of zero letters from chars.
        return [""];
    } else if (chars == "") {
        // BASE CASE
        document.write(debugMsg + " base case returns []<br />");
 return []; // A blank chars has no combinations, no matter what k is.
    }
    // RECURSIVE CASE
    let combinations = [];
    // First part, get the combos that include the head: // ❶
    let head = chars.slice(0, 1);
    let tail = chars.slice(1, chars.length);
    document.write(debugMsg + " part 1, get combos with head '" + head + "'<br />");
    let tailCombos = getCombos(tail, k - 1, indent + 1); // ❷
    document.write(".".repeat(indent) + "Adding head '" + head + "' to tail combos:<br />");
    for (tailCombo of tailCombos) {
        document.write(".".repeat(indent) + "New combination " + head + tailCombo + "<br />");
        combinations.push(head + tailCombo);
    }
    // Second part, get the combos that don't include the head: // ❸
    document.write(debugMsg + " part 2, get combos without head '" + head + "')<br />");
    combinations = combinations.concat(getCombos(tail, k, indent + 1)); // ❹
    document.write(debugMsg + " results are " + combinations + "<br />");
    return combinations;
}
document.write('<pre>2-combinations of "ABC":<br />');
document.write("Results: " + getCombos("ABC", 2) + "<br /></pre>");
</script>

2-combinations of "ABC":
In getCombos('ABC', 2), start.
In getCombos('ABC', 2) part 1, get combos with head 'A'
.In getCombos('BC', 1), start.
.In getCombos('BC', 1) part 1, get combos with head 'B'
..In getCombos('C', 0), start.
..In getCombos('C', 0) base case returns ['']
.Adding head 'B' to tail combos:
.New combination B
.In getCombos('BC', 1) part 2, get combos without head 'B')
..In getCombos('C', 1), start.
..In getCombos('C', 1) part 1, get combos with head 'C'
...In getCombos('', 0), start.
...In getCombos('', 0) base case returns ['']
..Adding head 'C' to tail combos:
..New combination C
..In getCombos('C', 1) part 2, get combos without head 'C')
...In getCombos('', 1), start.
...In getCombos('', 1) base case returns []
..In getCombos('C', 1) results are ['C']
.In getCombos('BC', 1) results are ['B', 'C']
Adding head 'A' to tail combos:
New combination AB
New combination AC
In getCombos('ABC', 2) part 2, get combos without head 'A')
.In getCombos('BC', 2), start.
.In getCombos('BC', 2) part 1, get combos with head 'B'
..In getCombos('C', 1), start.
..In getCombos('C', 1) part 1, get combos with head 'C'
...In getCombos('', 0), start.
...In getCombos('', 0) base case returns ['']
..Adding head 'C' to tail combos:
..New combination C
..In getCombos('C', 1) part 2, get combos without head 'C')
...In getCombos('', 1), start.
...In getCombos('', 1) base case returns []
..In getCombos('C', 1) results are ['C']
.Adding head 'B' to tail combos:
.New combination BC
.In getCombos('BC', 2) part 2, get combos without head 'B')
..In getCombos('C', 2), start.
..In getCombos('C', 2) part 1, get combos with head 'C'
...In getCombos('', 1), start.
...In getCombos('', 1) base case returns []
..Adding head 'C' to tail combos:
..In getCombos('C', 2) part 2, get combos without head 'C')
...In getCombos('', 2), start.
...In getCombos('', 2) base case returns []
..In getCombos('C', 2) results are []
.In getCombos('BC', 2) results are ['BC']
In getCombos('ABC', 2) results are ['AB', 'AC', 'BC']
Results: ['AB', 'AC', 'BC']

def getBalancedParens(pairs, openRem=None, closeRem=None, current='', indent=0):
    if openRem is None: # ❶
        openRem = pairs
    if closeRem is None:
        closeRem = pairs
    print('.' * indent, end='')
    print('Start of pairs=' + str(pairs) + ', openRem=' + 
    str(openRem) + ', closeRem=' + str(closeRem) + ', current="' + current + '"')
    if openRem == 0 and closeRem == 0: # ❷
        # BASE CASE
        print('.' * indent, end='')
        print('1st base case. Returning ' + str([current]))
        return [current] # ❸
    # RECURSIVE CASE
    results = []
    if openRem > 0: # ❹
        print('.' * indent, end='')
        print('Adding open parenthesis.')
        results.extend(getBalancedParens(pairs, openRem - 1, closeRem, 
        current + '(', indent + 1))
    if closeRem > openRem: # ❺
        print('.' * indent, end='')
        print('Adding close parenthesis.')
        results.extend(getBalancedParens(pairs, openRem, closeRem - 1, 
        current + ')', indent + 1))
    # BASE CASE
    print('.' * indent, end='')
    print('2nd base case. Returning ' + str(results))
    return results # ❻
print('All combinations of 2 balanced parentheses:')
print('Results:', getBalancedParens(2))

<script type="text/javascript">
function getBalancedParens(pairs, openRem, closeRem, current, indent) {
    if (openRem === undefined) { // ❶
        openRem = pairs;
    }
    if (closeRem === undefined) {
        closeRem = pairs;
    }
    if (current === undefined) {
        current = "";
    }
 if (indent === undefined) {
        indent = 0;
    }
    document.write(".".repeat(indent) + "Start of pairs=" + 
    pairs + ", openRem=" + openRem + ", closeRem=" + 
    closeRem + ", current=\"" + current + "\"<br />");
    if (openRem === 0 && closeRem === 0) { // ❷
        // BASE CASE
        document.write(".".repeat(indent) + 
        "1st base case. Returning " + [current] + "<br />");
        return [current]; // ❸
    }
    // RECURSIVE CASE
    let results = [];
    if (openRem > 0) { // ❹
        document.write(".".repeat(indent) + "Adding open parenthesis.<br />");
        Array.prototype.push.apply(results, getBalancedParens(
        pairs, openRem - 1, closeRem, current + '(', indent + 1));
    }
    if (closeRem > openRem) { // ❺
        document.write(".".repeat(indent) + "Adding close parenthesis.<br />");
        results = results.concat(getBalancedParens(
        pairs, openRem, closeRem - 1, current + ')', indent + 1));
    }
    // BASE CASE
    document.write(".".repeat(indent) + "2nd base case. Returning " + results + "<br />");
    return results; // ❻
}
document.write(<pre>"All combinations of 2 balanced parentheses:<br />");
document.write("Results: ", getBalancedParens(2), "</pre>");
</script>

All combinations of 2 balanced parentheses:
Start of pairs=2, openRem=2, closeRem=2, current=""
Adding open parenthesis.
.Start of pairs=2, openRem=1, closeRem=2, current="("
.Adding open parenthesis.
..Start of pairs=2, openRem=0, closeRem=2, current="(("
..Adding close parenthesis.
...Start of pairs=2, openRem=0, closeRem=1, current="(()"
...Adding close parenthesis.
....Start of pairs=2, openRem=0, closeRem=0, current="(())"
....1st base case. Returning ['(())']
...2nd base case. Returning ['(())']
..2nd base case. Returning ['(())']
.Adding close parenthesis.
..Start of pairs=2, openRem=1, closeRem=1, current="()"
..Adding open parenthesis.
...Start of pairs=2, openRem=0, closeRem=1, current="()("
...Adding close parenthesis.
....Start of pairs=2, openRem=0, closeRem=0, current="()()"
....1st base case. Returning ['()()']
...2nd base case. Returning ['()()']
..2nd base case. Returning ['()()']
.2nd base case. Returning ['(())', '()()']
2nd base case. Returning ['(())', '()()']
Results: ['(())', '()()']

def getPowerSet(chars, indent=0):
    debugMsg = '.' * indent + 'In getPowerSet("' + chars + '")'
    print(debugMsg + ', start.')
    if chars == '': # ❶
        # BASE CASE
        print(debugMsg + " base case returns ['']")
        return ['']
    # RECURSIVE CASE
    powerSet = []
    head = chars[0]
    tail = chars[1:]
    # First part, get the sets that don't include the head:
    print(debugMsg, "part 1, get sets without head '" + head + "'")
    tailPowerSet = getPowerSet(tail, indent + 1) # ❷
    # Second part, get the sets that include the head:
    print(debugMsg, "part 2, get sets with head '" + head + "'")
    for tailSet in tailPowerSet:
        print(debugMsg, 'New set', head + tailSet)
        powerSet.append(head + tailSet) # ❸
    powerSet = powerSet + tailPowerSet
    print(debugMsg, 'returning', powerSet)
    return powerSet # ❹
print('The power set of ABC:')
print(getPowerSet('ABC'))

<script type="text/javascript">
function getPowerSet(chars, indent) {
    if (indent === undefined) {
        indent = 0;
    }
    let debugMsg = ".".repeat(indent) + 'In getPowerSet("' + chars + '")';
    document.write(debugMsg + ", start.<br />");
    if (chars == "") { // ❶
        // BASE CASE
        document.write(debugMsg + " base case returns ['']<br />");
        return [''];
    }
    // RECURSIVE CASE
    let powerSet = [];
    let head = chars[0];
    let tail = chars.slice(1, chars.length);
 // First part, get the sets that don't include the head:
    document.write(debugMsg + 
    " part 1, get sets without head '" + head + "'<br />");
    let tailPowerSet = getPowerSet(tail, indent + 1); // ❷
    // Second part, get the sets that include the head:
    document.write(debugMsg + 
    " part 2, get sets with head '" + head + "'<br />");
    for (tailSet of tailPowerSet) {
        document.write(debugMsg + " New set " + head + tailSet + "<br />");
        powerSet.push(head + tailSet); // ❸
    }
    powerSet = powerSet.concat(tailPowerSet);
    document.write(debugMsg + " returning " + powerSet + "<br />");
    return powerSet; // ❹
}
document.write("<pre>The power set of ABC:<br />")
document.write(getPowerSet("ABC") + "<br /></pre>");
</script>

The power set of ABC:
In getPowerSet("ABC"), start.
In getPowerSet("ABC") part 1, get sets without head 'A'
.In getPowerSet("BC"), start.
.In getPowerSet("BC") part 1, get sets without head 'B'
..In getPowerSet("C"), start.
..In getPowerSet("C") part 1, get sets without head 'C'
...In getPowerSet(""), start.
...In getPowerSet("") base case returns ['']
..In getPowerSet("C") part 2, get sets with head 'C'
..In getPowerSet("C") New set C
..In getPowerSet("C") returning ['C', '']
.In getPowerSet("BC") part 2, get sets with head 'B'
.In getPowerSet("BC") New set BC
.In getPowerSet("BC") New set B
.In getPowerSet("BC") returning ['BC', 'B', 'C', '']
In getPowerSet("ABC") part 2, get sets with head 'A'
In getPowerSet("ABC") New set ABC
In getPowerSet("ABC") New set AB
In getPowerSet("ABC") New set AC
In getPowerSet("ABC") New set A
In getPowerSet("ABC") returning ['ABC', 'AB', 'AC', 'A', 'BC', 'B', 'C', '']
['ABC', 'AB', 'AC', 'A', 'BC', 'B', 'C', '']

>>> def subtract(number1, number2):
...     return number1 - number2
...
>>> subtract(123, 987)
-864

>>> TOTAL = 0
>>> def addToTotal(amount):
...     global TOTAL
...     TOTAL += amount
...     return TOTAL
...
>>> addToTotal(10)
10
>>> addToTotal(10)
20
>>> TOTAL
20

fibonacciCache = {} # ❶ # Create the global cache.
def fibonacci(nthNumber, indent=0):
    global fibonacciCache
    indentation = '.' * indent
    print(indentation + 'fibonacci(%s) called.' % (nthNumber))
    if nthNumber in fibonacciCache:
        # If the value was already cached, return it.
        print(indentation + 'Returning memoized result: %s' % (fibonacciCache[nthNumber]))
        return fibonacciCache[nthNumber] # ❷
    if nthNumber == 1 or nthNumber == 2:
        # BASE CASE
        print(indentation + 'Base case fibonacci(%s) returning 1.' % (nthNumber))
        fibonacciCache[nthNumber] = 1 # ❸ # Update the cache.
        return 1
    else:
        # RECURSIVE CASE
        print(indentation + 'Calling fibonacci(%s) (nthNumber - 1).' % (nthNumber - 1))
        result = fibonacci(nthNumber - 1, indent + 1)
        print(indentation + 'Calling fibonacci(%s) (nthNumber - 2).' % (nthNumber - 2))
        result = result + fibonacci(nthNumber - 2, indent + 1)
        print('Call to fibonacci(%s) returning %s.' % (nthNumber, result))
        fibonacciCache[nthNumber] = result # ❹ # Update the cache.
        return result
print(fibonacci(10))
print(fibonacci(10)) # ❺

<script type="text/javascript">
let fibonacciCache = {}; // Create the global cache. // ❶
function fibonacci(nthNumber, indent) {
    if (indent === undefined) {
        indent = 0;
    }
    let indentation = '.'.repeat(indent);
    document.write(indentation + "fibonacci(" + nthNumber + ") called.
<br />");
    if (nthNumber in fibonacciCache) {
        // If the value was already cached, return it.
        document.write(indentation +
        "Returning memoized result: " + fibonacciCache[nthNumber] + "<br />");
        return fibonacciCache[nthNumber]; // ❷
    }
    if (nthNumber === 1 || nthNumber === 2) {
        // BASE CASE
        document.write(indentation + 
        "Base case fibonacci(" + nthNumber + ") returning 1.<br />");
        fibonacciCache[nthNumber] = 1; // Update the cache. // ❸
        return 1;
 } else {
        // RECURSIVE CASE
        document.write(indentation + 
        "Calling fibonacci(" + (nthNumber - 1) + ") (nthNumber - 1).<br />");
        let result = fibonacci(nthNumber - 1, indent + 1);
        document.write(indentation + 
        "Calling fibonacci(" + (nthNumber - 2) + ") (nthNumber - 2).<br />");
        result = result + fibonacci(nthNumber - 2, indent + 1);
        document.write(indentation + "Returning " + result + ".<br />");
        fibonacciCache[nthNumber] = result; // Update the cache. // ❹
        return result;
    }
}
document.write("<pre>");
document.write(fibonacci(10) + "<br />");
document.write(fibonacci(10) + "<br />"); // ❺
document.write("</pre>");
</script>

fibonacci(10) called.
Calling fibonacci(9) (nthNumber - 1).
.fibonacci(9) called.
.Calling fibonacci(8) (nthNumber - 1).
..fibonacci(8) called.
..Calling fibonacci(7) (nthNumber - 1).
# --snip--
.......Calling fibonacci(2) (nthNumber - 1).
........fibonacci(2) called.
........Base case fibonacci(2) returning 1.
.......Calling fibonacci(1) (nthNumber - 2).
........fibonacci(1) called.
........Base case fibonacci(1) returning 1.
Call to fibonacci(3) returning 2.
......Calling fibonacci(2) (nthNumber - 2).
.......fibonacci(2) called.
.......Returning memoized result: 1
# --snip--
Calling fibonacci(8) (nthNumber - 2).
.fibonacci(8) called.
.Returning memoized result: 21
Call to fibonacci(10) returning 55.
55
fibonacci(10) called.
Returning memoized result: 55
55

import functools
@functools.lru_cache()
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) (nthNumber - 1).' % (nthNumber - 1))
        result = fibonacci(nthNumber - 1)
        print('Calling fibonacci(%s) (nthNumber - 2).' % (nthNumber - 2))
        result = result + fibonacci(nthNumber - 2)
        print('Call to fibonacci(%s) returning %s.' % (nthNumber, result))
        return result
print(fibonacci(99))

import functools, time, datetime
@functools.lru_cache()
def getCurrentTime():
    # This nondeterministic function returns different values each time
    # it's called.
    return datetime.datetime.now()
@functools.lru_cache()
def printMessage():
    # This function displays a message on the screen as a side effect.
 print('Hello, world!')
print('Getting the current time twice:')
print(getCurrentTime())
print('Waiting two seconds...')
time.sleep(2)
print(getCurrentTime())
print()
print('Displaying a message twice:')
printMessage()
printMessage()

Getting the current time twice:
2022-07-30 16:25:52.136999
Waiting two seconds...
2022-07-30 16:25:52.136999
Displaying a message twice:
Hello, world!

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

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

def rev(theString, accum=''): # ❶
    if len(theString) == 0:
        # BASE CASE
        return accum # ❷
    else:
        # RECURSIVE CASE
        head = theString[0]
        tail = theString[1:]
        return rev(tail, head + accum) # ❸
text = 'abcdef'
print('The reverse of ' + text + ' is ' + rev(text))

<script type="text/javascript">
function rev(theString, accum='') { // ❶
    if (theString.length === 0) {
        // BASE CASE
        return accum; // ❷
    } else {
        // RECURSIVE CASE
        let head = theString[0];
        let tail = theString.substring(1, theString.length);
        return rev(tail, head + accum); // ❸
    }
}
let text = "abcdef";
document.write("The reverse of " + text + " is " + rev(text) + "<br />");
</script>

# --snip--
    elif n % 2 == 0:
        # RECURSIVE CASE (when n is even)
        result = exponentByRecursion(a, n / 2)
        return result * result
# --snip--

# --snip-- 
  } else if (n % 2 === 0) {
        // RECURSIVE CASE (when n is even)
        result = exponentByRecursion(a, n / 2);
        return result * result; 
# --snip--

# --snip--
return exponentByRecursion(a, n / 2) * exponentByRecursion(a, n / 2)
# --snip--

def isOdd(number):
    if number == 0:
        # BASE CASE
        return False
    else:
        # RECURSIVE CASE
        return not isOdd(number - 1)
print(isOdd(42))
print(isOdd(99))
# --snip--

<script type="text/javascript">
function isOdd(number) {
    if (number === 0) {
        // BASE CASE
        return false;
 } else {
        // RECURSIVE CASE
        return !isOdd(number - 1);
    }
}
document.write(isOdd(42) + "<br />");
document.write(isOdd(99) + "<br />");
# --snip--

# --snip--
def isOddTailCall(number, inversionAccum=False):
    if number == 0:
        # BASE CASE
        return inversionAccum
    else:
        # RECURSIVE CASE
        return isOddTailCall(number - 1, not inversionAccum)
print(isOddTailCall(42))
print(isOddTailCall(99))

# --snip--
function isOddTailCall(number, inversionAccum) {
    if (inversionAccum === undefined) {
        inversionAccum = false;
    }
    if (number === 0) {
        // BASE CASE
        return inversionAccum;
    } else {
 // RECURSIVE CASE
        return isOddTailCall(number - 1, !inversionAccum);
    }
}
document.write(isOdd(42) + "<br />");
document.write(isOdd(99) + "<br />");
</script>

import turtle
turtle.tracer(1, 0) # Makes the turtle draw faster.
for i in range(360):
    turtle.forward(i)
    turtle.left(59)
turtle.exitonclick() # Pause until user clicks in the window.

for (let i = 0; i < 360; i++) { t.fd(i); t.lt(59) }

import turtle
turtle.tracer(100, 0) # Increase the first argument to speed up the drawing.
turtle.setworldcoordinates(0, 0, 700, 700)
turtle.hideturtle()
MIN_SIZE = 4 # Try changing this to decrease/increase the amount of recursion.
def midpoint(startx, starty, endx, endy):
    # Return the x, y coordinate in the middle of the four given parameters.
    xDiff = abs(startx - endx)
    yDiff = abs(starty - endy)
    return (min(startx, endx) + (xDiff / 2.0), min(starty, endy) + (yDiff / 2.0))
def isTooSmall(ax, ay, bx, by, cx, cy):
    # Determine if the triangle is too small to draw.
    width = max(ax, bx, cx) - min(ax, bx, cx)
    height = max(ay, by, cy) - min(ay, by, cy)
    return width < MIN_SIZE or height < MIN_SIZE
def drawTriangle(ax, ay, bx, by, cx, cy):
    if isTooSmall(ax, ay, bx, by, cx, cy):
        # BASE CASE
        return
    else:
        # RECURSIVE CASE
        # Draw the triangle.
        turtle.penup()
        turtle.goto(ax, ay)
        turtle.pendown()
        turtle.goto(bx, by)
        turtle.goto(cx, cy)
        turtle.goto(ax, ay)
        turtle.penup()
        # Calculate midpoints between points A, B, and C.
        mid_ab = midpoint(ax, ay, bx, by)
        mid_bc = midpoint(bx, by, cx, cy)
        mid_ca = midpoint(cx, cy, ax, ay)
        # Draw the three inner triangles.
        drawTriangle(ax, ay, mid_ab[0], mid_ab[1], mid_ca[0], mid_ca[1])
        drawTriangle(mid_ab[0], mid_ab[1], bx, by, mid_bc[0], mid_bc[1])
        drawTriangle(mid_ca[0], mid_ca[1], mid_bc[0], mid_bc[1], cx, cy)
        return
# Draw an equilateral Sierpinski triangle.
drawTriangle(50, 50, 350, 650, 650, 50)
# Draw a skewed Sierpinski triangle.
#drawTriangle(30, 250, 680, 600, 500, 80)
turtle.exitonclick()

import turtle
turtle.tracer(10, 0) # Increase the first argument to speed up the drawing.
turtle.setworldcoordinates(0, 0, 700, 700)
turtle.hideturtle()
MIN_SIZE = 6 # Try changing this to decrease/increase the amount of recursion.
DRAW_SOLID = True
def isTooSmall(width, height):
    # Determine if the rectangle is too small to draw.
    return width < MIN_SIZE or height < MIN_SIZE
def drawCarpet(x, y, width, height):
    # The x and y are the lower-left corner of the carpet.
    # Move the pen into position.
    turtle.penup()
    turtle.goto(x, y)
    # Draw the outer rectangle.
    turtle.pendown()
    if DRAW_SOLID:
        turtle.fillcolor('black')
        turtle.begin_fill()
    turtle.goto(x, y + height)
    turtle.goto(x + width, y + height)
    turtle.goto(x + width, y)
    turtle.goto(x, y)
    if DRAW_SOLID:
        turtle.end_fill()
    turtle.penup()
    # Draw the inner rectangles.
    drawInnerRectangle(x, y, width, height)
def drawInnerRectangle(x, y, width, height):
    if isTooSmall(width, height):
        # BASE CASE
        return
    else:
        # RECURSIVE CASE
        oneThirdWidth = width / 3
        oneThirdHeight = height / 3
        twoThirdsWidth = 2 * (width / 3)
        twoThirdsHeight = 2 * (height / 3)
 # Move into position.
        turtle.penup()
        turtle.goto(x + oneThirdWidth, y + oneThirdHeight)
        # Draw the inner rectangle.
        if DRAW_SOLID:
            turtle.fillcolor('white')
            turtle.begin_fill()
        turtle.pendown()
        turtle.goto(x + oneThirdWidth, y + twoThirdsHeight)
        turtle.goto(x + twoThirdsWidth, y + twoThirdsHeight)
        turtle.goto(x + twoThirdsWidth, y + oneThirdHeight)
        turtle.goto(x + oneThirdWidth, y + oneThirdHeight)
        turtle.penup()
        if DRAW_SOLID:
            turtle.end_fill()
        # Draw the inner rectangles across the top.
        drawInnerRectangle(x, y + twoThirdsHeight, oneThirdWidth, oneThirdHeight)
        drawInnerRectangle(x + oneThirdWidth, y + twoThirdsHeight, oneThirdWidth, oneThirdHeight)
        drawInnerRectangle(x + twoThirdsWidth, y + twoThirdsHeight, oneThirdWidth, oneThirdHeight)
        # Draw the inner rectangles across the middle.
        drawInnerRectangle(x, y + oneThirdHeight, oneThirdWidth, 
        oneThirdHeight)
        drawInnerRectangle(x + twoThirdsWidth, y + oneThirdHeight, oneThirdWidth, 
        oneThirdHeight)
        # Draw the inner rectangles across the bottom.
        drawInnerRectangle(x, y, oneThirdWidth, oneThirdHeight)
        drawInnerRectangle(x + oneThirdWidth, y, oneThirdWidth, oneThirdHeight)
        drawInnerRectangle(x + twoThirdsWidth, y, oneThirdWidth, 
        oneThirdHeight)
drawCarpet(50, 50, 600, 600)
turtle.exitonclick()

import random
import time
import turtle
turtle.tracer(1000, 0) # Increase the first argument to speed up the drawing.
turtle.setworldcoordinates(0, 0, 700, 700)
turtle.hideturtle()
def drawBranch(startPosition, direction, branchLength):
    if branchLength < 5:
        # BASE CASE
        return
    # Go to the starting point & direction.
    turtle.penup()
    turtle.goto(startPosition)
    turtle.setheading(direction)
    # Draw the branch (thickness is 1/7 the length).
    turtle.pendown()
    turtle.pensize(max(branchLength / 7.0, 1))
    turtle.forward(branchLength)
    # Record the position of the branch's end.
    endPosition = turtle.position()
    leftDirection = direction + LEFT_ANGLE
    leftBranchLength = branchLength - LEFT_DECREASE
    rightDirection = direction - RIGHT_ANGLE
    rightBranchLength = branchLength - RIGHT_DECREASE
 # RECURSIVE CASE
    drawBranch(endPosition, leftDirection, leftBranchLength)
    drawBranch(endPosition, rightDirection, rightBranchLength)
seed = 0
while True:
    # Get pseudorandom numbers for the branch properties.
    random.seed(seed)
    LEFT_ANGLE     = random.randint(10,  30)
    LEFT_DECREASE  = random.randint( 8,  15)
    RIGHT_ANGLE    = random.randint(10,  30)
    RIGHT_DECREASE = random.randint( 8,  15)
    START_LENGTH   = random.randint(80, 120)
    # Write out the seed number.
    turtle.clear()
    turtle.penup()
    turtle.goto(10, 10)
    turtle.write('Seed: %s' % (seed))
    # Draw the tree.
    drawBranch((350, 10), 90, START_LENGTH)
    turtle.update()
    time.sleep(2)
    seed = seed + 1

>>> import random
>>> random.seed(42)
>>> [random.randint(0, 9) for i in range(20)]
 [1, 0, 4, 3, 3, 2, 1, 8, 1, 9, 6, 0, 0, 1, 3, 3, 8, 9, 0, 8]
>>> [random.randint(0, 9) for i in range(20)]
 [3, 8, 6, 3, 7, 9, 4, 0, 2, 6, 5, 4, 2, 3, 5, 1, 1, 6, 1, 5]
>>> random.seed(42)
>>> [random.randint(0, 9) for i in range(20)]
 [1, 0, 4, 3, 3, 2, 1, 8, 1, 9, 6, 0, 0, 1, 3, 3, 8, 9, 0, 8]

# Record the position of the branch's end.
    endPosition = turtle.position()
    leftDirection = direction + random.randint(10, 30)
    leftBranchLength = branchLength - random.randint(8, 15)
    rightDirection = direction - random.randint(10, 30)
    rightBranchLength = branchLength - random.randint(8, 15)