Every repeated computation so far has used
while or for. Recursion is a second, entirely different way to express repetition: a function that calls itself, on a smaller version of the same problem, until it reaches a case simple enough to answer directly. Recursion is not exotic or "advanced" — it is a natural translation of a certain kind of mathematical definition (define a value in terms of the same function applied to smaller inputs), and it is often the most readable way to express a solution once a problem has that recursive shape. This note builds recursion from the classic factorial and Fibonacci examples through to string palindrome-checking, which introduces the divide-and-conquer problem-solving pattern that recurs throughout the rest of this vault's algorithms content.Learning objectives. By the end of this note you should be able to:
- identify the base case(s) and recursive case(s) in a recursive definition, and translate a recursive mathematical definition directly into a recursive function;
- explain why a recursive function terminates by identifying how each recursive call moves strictly closer to a base case;
- trace a recursive call by hand, including cases with more than one recursive call per invocation (e.g. Fibonacci);
- apply the divide-and-conquer pattern (break a problem into smaller subproblems, solve each, combine the solutions) via a helper-function decomposition, as in palindrome checking.
In this lesson
- Base cases and recursive cases
- More than one base case, more than one recursive call
- Divide-and-conquer: recursion on non-numeric data
Before you start
The full lesson, with worked examples and exercise solutions, is for members.
Read the full lessonNew to SelfMadeQuant.com? See membership options or browse the Python for Quantitative Finance syllabus.