Recursion — Class 12 CBSE Computer Science revision notes
A 3-page visual revision sheet for Recursion, written for Class 12 CBSE Computer Science. Formulas, diagrams and the traps that cost marks, laid out to be read the night before rather than the term before. Free, and it opens inside CapCompass.
Page 1 as PDF
Recursion in one look
a function that calls itself, on a smaller version of the same problem, until one call finally can't
The base case and the recursive case
- a recursive function calls itself, directly or through another function, to solve a smaller version of the same problem
- the base case is the condition answered directly, with no further call
- the recursive case breaks the problem down and calls the function again on a smaller piece of it
- every recursive function needs both parts: a base case alone never calls itself, a recursive case alone never stops
fact(3), what actually happens
- fact(3) calls fact(2), waiting for its answer before it can multiply anything
- fact(2) calls fact(1), waiting the same way
- fact(1) is the base case, it returns 1 with no further call
- fact(2) resumes, computes 2 times 1, returns 2
- fact(3) resumes, computes 3 times 2, returns 6
Calls stack, then unwind
- each call gets its own space to remember its own local variables and its own place in the calculation
- a call waiting on another call sits paused, it can't finish until the one it called returns
- returns happen in the reverse order the calls were made, the last call in is the first call to finish
Infinite recursion and RecursionError
- a base case that's never reached, or a recursive call that never actually shrinks the problem, calls forever
- Python has a built-in limit on how deep calls can stack, roughly a thousand by default, and stops with a RecursionError once it's crossed
- hitting that limit is usually a sign the base case is wrong, missing, or unreachable, not that the limit needs raising
Recursive vs Iterative
- calls itself on a smaller version of the problem
- often reads closer to the problem's own definition, shorter to write
- each waiting call uses extra memory on the call stack, deep recursion can run out
- repeats with a loop, no repeated function calls
- uses a small, fixed amount of memory no matter how many repetitions
- can look less like the problem's own mathematical definition
Why choose one over the other
- recursion suits problems naturally defined in terms of smaller versions of themselves, like a factorial or a tree
- a loop is usually the safer choice when the depth could get large, since it never risks a RecursionError
- clarity is a real trade-off, some solutions are dramatically shorter and easier to trust when written recursively
Page 1 of 3. The full sheet, all 3 pages, opens free in the app.
What this Recursion sheet covers
- The base case and the recursive case
- Tracing fact(3), call by call
- fact(3), what actually happens
- Calls stack, then unwind
- Infinite recursion and RecursionError
- Recursive vs Iterative
- Recursive
- Iterative
- Why choose one over the other
- The idea behind memoisation
- fib(4) without memoisation, the repeats
- The four canonical recursive problems
- Factorial
- Fibonacci
- Sum of digits
- Binary search
- Sum of digits, sumdig(153)
- Binary search, recursively
- Traps that cost marks
- Tricks that save time
How CapCompass uses this sheet
These notes are not a standalone PDF. CapCompass plans Computer Science chapter by chapter against your real exam dates and free hours, and when the plan reaches Recursion the sheet opens inside the study block itself — at the page covering the sub-topic that block is on, with the timer still running. Revision arrives at the moment the plan says revise, instead of having to be gone looking for.