Skip to content
Workshopy.io
Join a classSign inStart free
  • Official
  • Beginner
  • English
  • About 75 min
  • 10 steps · 2 quizzes

Recursion, Visualized

A visual first lesson on recursion: functions that call themselves. Students open nesting dolls, watch the call stack grow and shrink, crash it on purpose…

Start learningSee the steps
  • Free
  • No account needed
  • Stop any time, pick up where you left off
0 comments
Workshopy.io

WorkshopyOfficial

28 lessons · used by 2 teachers

For teachers

Teaching this? Run it live with your class.

  • Students join with a code — no accounts
  • See who’s done and who’s stuck, step by step
  • It’s your copy — change anything before class
Use this lesson

Sign in to copy it to your workspace. It’s free.

Your path

10 steps · 2 quizzes · about 75 minutes · open any step

  1. A problem inside a problemStart hereSome problems contain a smaller copy of themselves. Open a nesting doll and inside is… another doll, just smaller. Try it: open the dolls one by one, then close them all.InteractiveHands-on · 5 min
  2. Two parts: base case and recursive caseEvery recursive function needs both: - a base case — so small it's answered directly, with no more calls; - a recursive case — call yourself on a smaller input.InteractiveHands-on · 5 min
  3. The call stack: waiting for answersHow does Python remember where each call was? It keeps a call stack: one frame per call, each with its own n. A frame waits until the call it made returns an answer. Try it: step through factorial(4). Watch the frames pile up, then the answers travel back up.InteractiveHands-on · 5 min
  4. Forget the base case: stack overflowWithout a base case, nothing ever says "stop": every call makes another one and the stack keeps growing. Python protects itself with a limit of about 1,000 nested calls. Try it: run it with the base case. Then switch the base case off and run it again.InteractiveHands-on · 5 min
  5. Check: the basicsQuiz · 4 questions
  6. Two calls at once: the Fibonacci treeSome functions call themselves twice. In the Fibonacci sequence (0, 1, 1, 2, 3, 5, 8…) each number is the sum of the two before itInteractiveHands-on · 6 min
  7. Remember answers: memoizationThe fix: write each answer down the first time, and look it up the next time. This is called memoization. Python does it for you with one line, @cacheInteractiveHands-on · 7 min
  8. Recursion draws: a fractal treeRecursion isn't only for numbers. To draw a tree: draw a trunk, then draw two smaller trees at its tip. The base case: depth 0 draws nothing.InteractiveHands-on · 9 min
  9. Lists inside listsRecursion shines on nested data: folders inside folders, replies to replies, lists inside lists. A box can hold numbers and other boxes — so to add it all up, add the numbers and call yourself on every inner box.InteractiveHands-on · 8 min
  10. Towers of HanoiMove the whole tower from A to C. Only one disk at a time, and never a bigger disk on a smaller one. Try it: solve it by hand with 3 disks. Then press Watch the recursive solution and follow the calls shown above the buttons.InteractiveHands-on · 7 min

Comments 0

You’ll sign in with Google before it’s posted.Comments are public — don’t name your students.
0 / 1,500

No comments yet. Be the first to say how it went.

Using it

Workshopy shares this lesson under CC BY 4.0. Anyone may use and change it, with credit to you. Anyone can learn it here, free. A copy in your workspace is yours to change and run live; your students never need an account.

Versions

  1. 1

    Version 1Current

    · First published

Copies are made from the current version. A copy you already have doesn’t change.

More from Workshopy

All 28 lessons