Stage 4 · Lesson 6 of 10
Recursion
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
- CoursePaidGrokking Data Structures & Algorithms for Coding Interviews
Design Gurus · Beginner · Subscription
Each structure built from first principles, with solutions in Python, Java, C++, JavaScript and C#
- CourseFreeCS50: Introduction to Computer Science
Harvard University · Beginner
Free: weeks 3 and 5 cover searching, sorting, linked lists, hash tables and trees
Practise
Keep handy
Also worth your time
Time and space complexity worked through five common algorithms