Python Recursion for LeetCode
Understanding Recursion
Functions That Call Themselves
Imagine you have a set of Russian nesting dolls. You open the largest doll to find a slightly smaller one inside. You open that one and find another, and so on, until you reach the smallest doll that can't be opened. This is the core idea behind recursion in programming.
The process in which a function calls itself directly or indirectly is called recursion and the corresponding function is called a recursive function.
A recursive function is a function that solves a problem by calling itself with a smaller or simpler version of the same problem. Instead of using a loop to repeat an action, the function repeatedly invokes itself until it reaches a point where the problem is so simple it can be solved directly. Every recursive function needs two key components to work correctly.
The Two Key Ingredients
First, every recursive function must have a base case. This is the condition under which the function stops calling itself. It's the smallest, simplest version of the problem, the one that can be solved without any more recursion. In our nesting doll analogy, the base case is the tiny, solid doll that can't be opened. Without a base case, a recursive function would call itself forever, leading to an error called a stack overflow.
The base case is the condition that stops the recursion.
The second part is the recursive case (or recursive step). This is where the function calls itself, but with an input that moves it closer to the base case. The function takes the current problem, does a small piece of work, and then turns the rest of the problem over to a new call to itself. Each recursive call should break the problem down into a slightly simpler version.
The recursive case breaks the problem down and moves it closer to the base case.