Skip to the main content
PeabodyMake a free story

🤖 Code & Robots, level 11

What the trails say and what they ask. Print it for the class, or put the same questions on the board with a live quiz.

Code & Robots, level 11

🪆 Recursion

How can a function solve a problem by calling itself?

  • How can a function solve a problem by calling itself? The technique is called recursion, and the NIST Dictionary of Algorithms and Data Structures defines it as an algorithmic technique where a function, in order to accomplish a task, calls itself with some part of the task. The idea is to break a large problem into a slightly smaller version of the same problem, solve that smaller version in exactly the same way, and keep going until the problem becomes so simple that it can be answered directly. That simplest situation is called the base case, and every recursive solution needs at least one of them. The other part, where the function calls itself on a smaller piece of the problem, is called the recursive case, and together the two parts describe the complete solution.
  • A classic example is the factorial, which mathematicians write with an exclamation mark after the number. The factorial of a whole number is the product of every whole number from 1 up to it, so 4! means 4 times 3 times 2 times 1, which equals 24. Notice that 4! is simply 4 times 3!, and 3! is 3 times 2!. A recursive function can use that pattern: factorial(n) returns 1 when n is 1, which is its base case, and otherwise returns n times factorial(n minus 1). To find factorial(4), the function needs factorial(3), which needs factorial(2), which in turn needs factorial(1), and each of those calls must wait, unfinished, until the call beneath it returns an answer. That final call reaches the base case and returns 1. Then the answers travel back up the chain: 2 times 1 is 2, 3 times 2 is 6, and finally 4 times 6 is 24.
  • What happens if a programmer forgets the base case? Each call would make another call, which would make another, with nothing ever telling the chain to stop, so in theory the calls would continue forever. In practice, a computer keeps track of every unfinished call in a region of memory called the call stack, and that space is limited, so the program eventually runs out of room and stops with an error, often called a stack overflow. Programmers prevent this by checking two things: that a base case exists, and that every recursive call moves closer to it, the way factorial(n minus 1) moves one step nearer to 1. Recursion is especially useful for problems that naturally contain smaller copies of themselves, such as searching through folders that are stored inside other folders.

Try it at home: Stack a few nesting cups or boxes and open them one by one, saying which one is the base case, then work out 5 factorial together.

Questions and answers

Recursion

  1. A function that solves a task by calling itself with some part of the task is using… recursion
  2. 🧱 The simplest case, which a recursive function answers directly without calling itself, is called the… base case (The base case is simple enough to solve directly, so the chain of calls can stop.)
  3. The part where a function calls itself on a smaller piece of the problem is called the… recursive case
  4. 🧮 What does 4 factorial equal? 24 (4 times 3 times 2 times 1 is 24.)
  5. Which statement is true about factorials? 4 factorial is 4 times 3 factorial
  6. 🪆 To work out factorial of 4, which call reaches the base case first? factorial of 1 (The calls go 4, 3, 2, then 1, and factorial of 1 returns 1 directly.)