Saltar al contenido ForoHackers

Recursion explained with a stack of plates

AlgoritmosEnseñanza de la informáticaEnseñanza y aprendizaje
#1095 · byte_sized_owl · · Denunciar

Teaching recursion to beginners, my current explanation: every call puts a plate on a stack, and a function can only finish when the plates above it are gone.

def countdown(n):
    if n == 0:
        print("liftoff")
        return
    print(n)
    countdown(n - 1)

countdown(3)

Trace it with plates. countdown(3) puts a plate marked n=3 on the stack, prints 3, and calls countdown(2), which puts a plate n=2 on top, and so on. When n == 0 it prints "liftoff" and returns, the top plate is removed and we are back in the call with n=1, which has nothing left to do and returns, then n=2, then n=3.

Two things students need to see, and plates show both:

  1. The base case is the plate that does not call anyone. Without it, the pile grows until the table (the stack) breaks. In Python that is RecursionError, by default after about a thousand plates.
  2. Each plate has its own n. They do not share it. That is why recursion works without any clever bookkeeping: the bookkeeping is the stack.

Once that clicks, factorial and tree traversal stop being magic and become "the same pile of plates, with a different instruction on each one".

#1736 · rubber_duck_supervisor · · Denunciar

Lovely. A question I ask after this explanation: what changes if the print(n) comes after the recursive call? Ask students to predict, then run. The plates make the answer (it counts up on the way back down the pile) feel obvious.

#1737 · off_by_two · · Denunciar

Bonus puzzle for the class: write countdown so it prints 3 2 1 liftoff 1 2 3 using one recursive call and no list. (Print before and after the call.)

#1738 · ElProfeDeRedes · · Denunciar

Me lo llevo para mis clases de programación. En redes la imagen del montón me sirve para la encapsulación: cada capa pone su cabecera encima al enviar, y al recibir se van quitando en orden inverso, como los platos.

#1739 · lambda_llama · · Denunciar

Gentle nudge for later in the course: once recursion is comfortable, show a tail call, where the plate on the pile can be replaced instead of stacked on. Some languages guarantee that optimisation and some (Python) deliberately do not. A good moment to discuss why.

#1740 · byte_sized_owl · · Denunciar

Yes to all of these. Printing after the call is exactly my second exercise, and the tail-call discussion is the week after. Thanks for the puzzle, it is going in the worksheet.

Inicia sesión o únete para responder.