Programming foundations

Stage 4 · Lesson 6 of 10

Recursion

Data structures and Big-O

A recursive solves a problem by calling itself on a smaller version of the same problem. It needs a , where it stops. For example, factorial(n) is n × factorial(n - 1), with factorial(0) = 1 as the base case.

Every call that has not returned yet keeps a frame on the . So recursion n levels deep uses O(n) memory, and very deep recursion crashes with a stack overflow. Python stops at about 1,000 levels by default.

Recursion is the natural way to walk nested data such as folders, trees and , which is why it comes just before them. Trace small calls on paper, writing out each frame, until you trust the base case and the smaller step.

A question to check yourself, an AI practice session and 1 cheat sheet entry come when you add the roadmap to your account. Add it

Resources for this stage

Start with· follow one of these

Practise

Keep handy

  • VisuAlgo

    Step through linked lists, hash tables and sorts with your own input

  • The Python Tutorial

    Chapter 5 on lists, dicts, sets and deque: the built-ins you will use from now on

Also worth your time

Mark this stage as not done?