A method of solving a problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such problems by using functions that call themselves from within their own code.


Base case

A terminating scenario that does not use recursion to produce an answer. The base case is the simplest, smallest instance of the problem, that can’t be decomposed any further. Recursive functions require a base case to prevent infinite recursion.

Recursive step

A set of rules that reduces all successive cases toward the base case. Decomposes a larger instance of the problem into simpler or smaller instances that can be solved by recursive calls, and then recombines the results of those subproblems to produce the solution to the original problem.

Iterative vs recursive thinking

Any recursion can be rewritten as a loop. Recursive algorithms require execution contexts and thus requires memory. Loop-based algorithms do not and are therefore more memory-saving.

Recursive Structures

A recursive data structure is a structure that replicates itself in parts.