Recursion at Work

Recursion on things shaped like folders inside folders, when a loop reads better instead, and memoization: writing an answer down so it's never worked out twice.

Updated

Nested Data

  1. Sections Inside Sections: Recursion on Nested Data (Journeyman): Put a restaurant's menu online, with sections inside sections to any depth: add up one of everything, and print the menu as an outline with every section indented under the one that holds it, using one function per job that works at any depth.

Choosing

  1. 5,000 Folders Deep: Recursion or a Loop? (Journeyman): Keep the folder tool working on a folder thousands of levels deep, where recursion runs out of call stack: why a bigger limit and a plain loop both fall short, how a loop with a pile of its own does the job, and how to choose between recursion and a loop for any task.
  2. Asking the Same Question Twice: Memoization (Journeyman): Speed up a recursive function that answers 10 stairs at once, 40 in half a minute and 50 in about an hour: why a faster computer and a loop with your own stack don't help, where the time really goes, and how writing each answer down, memoization, makes it instant.

Exercise: Menus Inside Menus

  1. Exercise: Menus Inside Menus (Journeyman): A restaurant is putting its menu online, with sections inside sections and a tasting menu ten levels deep on the way: count every dish, find the chef's pick, and print the whole menu as an outline, with code that works at any depth. The tests check all three, ten levels down included.