Recursion#

To download the demo code for this lecture, run:

$ dmget wb-recursion --demo

Introduction#

Goals#

  • Define recursion

  • Introduce idea of “call stack”

  • Look at lots of recursion examples

  • Strategies for doing recursion

What is Recursion?#

  • Recursion: when a function calls itself

    • A very powerful programming technique

    • Also a popular interview topic

Functions Calling Functions#

function a() {
  console.log("hello");
  b();
  console.log("coding");
}

function b() {
  console.log("world");
  c();
  console.log("love");
}

function c() {
  console.log("i");
}

a();

Call Stack

See this code in Code Visualizer

Each function call is like jumping through a portal into another universe.

When you return from that function, you go right back through the portal you came from and then continue where you left off.

The Call Stack#

Count to 3#

Using a loop:

function countTo3Loop() {
  let n = 1;

  while (n <= 3) {
    console.log(n);
    n += 1;
  }
}

Using recursion:

function countTo3Recursive(n = 1) {
  if (n > 3) {
    return;
  }
  console.log(n);
  countTo3Recursive(n + 1);
}

It turns out, any loop can be written instead with recursion (and vice versa).

See this code in Code Visualizer

Call Stack / Stack Frames#

function countTo3Recursive(n = 1) {
  if (n > 3) {
    return;
  }
  console.log(n);
  countTo3Recursive(n + 1);
}

Call Stack

More Counting#

function countTo3Recursive(n=1) {
  if (n > 3) {
    return;
  }
  console.log(n);
  countTo3Recursive(n + 1);
  console.log(-n);
}

Call Stack

Recursion Requirements#

Base Case#

  • Every recursive function needs a base case.

    • How do we know when we’re done?

    • Like a stop sign

function countTo3Recursive(n = 1) {
  if (n > 3) {
    return;
  }
  console.log(n);
  countTo3Recursive(n + 1);
}

This is a “hidden” base case — it’s not as obvious but it still works

function countRecursiveAlt(n=1) {
  if (n <= 3) {
    console.log(n);
    countRecursiveAlt(n + 1);
  }
}

Progress#

We have to be moving forward toward our stop sign

function countTo3Recursive(n = 1) {
  if (n > 3) {
    return;
  }
  console.log(n);
  countTo3Recursive(n + 1);
}

What If There’s No Base Case?#

function count(n=1) {
  console.log(n);
  count(n + 1);
}

Uncaught RangeError: Maximum call stack size exceeded

  • It will recurse forever.

  • The same thing will happen if you have a base case but don’t make progress toward it.

  • This error is also called a Stack Overflow error.

Strategies for Recursion#

Using recursion, find the sum of an array of numbers.

What’s the Base Case?#

Often a base case is an “empty case” — e.g. an empty array, null, a leaf in a tree, etc.

Here, a good base case would be an empty array.

Make the Problem Smaller and Smaller#

  • Many recursion problems involve “breaking off a piece” and making the problem smaller and smaller.

  • sum of numbers = first number + sum of rest of numbers

  • sumNums([1, 2, 3]) = 1 + sumNums([2, 3])

  • Then keep going: break off a piece from [2, 3].

Back Substitution

Strategy #1: “Backpack”#

function sumNums1(nums, total = 0) {
  if (nums.length === 0) {
    return total;
  }
  return sumNums1(nums.slice(1), total + nums[0]);
}

  • Add an parameter (with a default value) to store the result at each step — the “backpack” variable

  • When you break off a piece and make a recursive call, update this variable

  • When you reach the base case, return this variable

See this code in Code Visualizer

Strategy #2: “Breadcrumbs”#

function sumNums2(nums) {
  if (nums.length === 0) {
    return 0;
  }
  return nums[0] + sumNums2(nums.slice(1));
}

  • When you make a recursive call, leave a “breadcrumb” to pick up on the way back

  • After returning from each function call, pick up the “breadcrumbs”

  • In this example, return 0 when you reach the base case, because the sum of an empty list is 0

See this code in Code Visualizer

Recursive Length#

How would you use recursion to find the length of a list?

List Doubler#

The Problem#

“For every item in an array, print the value, doubled.”

  • The challenge is, some items in the array can be arrays themselves.

  • We want to “flatten” them and still print the doubled values.

    doubler([1, [2, 3], 4])  // should print 2 4 6 8

function doubler(arr) {
	for (const item of arr) {
  	if (Array.isArray(item)) {
    	for (const subitem of item) {
      	console.log(subitem * 2);
      }
    }
    else {
    	console.log(item * 2);
    }
  }
}

  • This works for 1 level of nesting, e.g. [1, [2, 3], 4]

  • But we want it to work no matter how many levels of nesting

  • We can’t have infinitely nested for loops

Non-Recursive Solution#

function doublerNonRecursive(arr) {
  stack = arr.toReversed();

  while (stack.length > 0) {
    const currentItem = stack.pop();
    if (Array.isArray(currentItem)) {
      for (const subitem of currentItem.toReversed()) {
        stack.push(subitem);
      }
    } else {
      console.log(currentItem * 2);
    }
  }
}

It works, but it’s pretty difficult to understand!

Diagram: Non-Recursive Solution#

Non-Recursive Doubler

Recursive Solution#

Non-Recursive Doubler

function doublerRecursive(arr) {
  for (const item of arr) {
    if (Array.isArray(item)) {
      doublerRecursive(item);
    } else {
      console.log(item * 2);
    }
  }
}

Doubler Call Stack

Applications of Recursion#

Trees#

Recursion works well for trees, because each node is the root of its own subtree.

Tree Diagram

trees-recursion.js#
class Node {
  constructor(data, children = []) {
    this.data = data;
    this.children = children;
  }
}
function listNodes(node) {
  console.log(node.data);
  for (const child of node.children) {
    listNodes(child);
  }
}

Indenting Recursively#

function indentList(node, depth = 0) {
  // List all nodes, indented.

  console.log('  '.repeat(depth) + node.data);
  for (const child of node.children) {
    indentList(child, depth + 1);
  }
}

/
  Users/
    jane/
      resume.txt
      recipes.txt
    jessica/
      server.py

PEMDAS#

1 × ( 2 + 3 × ( 4 + 5 × 6 ) + 7 )

Nested Data#

<html>
  <head>
    <title>Title</title>
  </head>
  <body>
    <h1>Body</h1>
    <ul>
      <li>One</li>
      <li>Two
        <ul>
            <li>Two A</li>
            <li>Two B</li>
        </ul>
      </li>
    </ul>
  </body>
</html>

Fractals#

Fractals