Core · Module 7 · Lesson 3 of 4
Recursion vs iteration
Any recursion can become a loop and any loop a recursion. Tail calls turn into loops with an accumulator, and general recursion into a loop over an explicit stack. Choose by clarity, depth and cost.
By the end you can
- Turn a tail-recursive function into a loop with an accumulator
- Turn general recursion into a loop over an explicit stack
- Choose between recursion and iteration by clarity, depth and cost
Builds on Base cases and recursion trees.
01 · A question first
Every recursive function can be written as a loop, and every loop as a recursive function. So why do tree algorithms read so naturally as recursion, while summing a long list recursively is a bad idea in Python?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- Two ways to say the same thing
- Tail calls become loops
- General recursion becomes an explicit stack
- Choosing
- Memory as well as time
- Pseudocode & Multi-Language Implementations (C++, Java, Python)
- Complexity Derivation, Edge Cases & Common Mistakes
03 · Practice
Something wrong with this lesson? Report a problem