6.101 Fall 2022: Recursion and Iteration
This reading examines recursion more closely by comparing and contrasting it with iteration. Both approaches create repeated patterns of computation. Recursion produces repeated computation by calling the same function recursively, on a simpler or smaller subproblem. Iteration produces repeated computation using for loops or while loops. If we can come up with an iterative version, do we need recursion at all? In one sense, no, we don’t need recursion – any function we can write recursively could also be written iteratively. But some problems lend themselves naturally to a recursive solution. When we try to solve those kinds of problems iteratively instead, we find ourselves simulating recursion anyway, using an explicit agenda to keep track of what we need to do next. For those kinds of problems, it’s more straightforward to express the recursive algorithm directly, letting Python handle the agenda bookkeeping using its call stack. The converse is also true: any function we can write