Taken from the book Think Python (2e):
http://greenteapress.com/wp/think-python-2e/
It is legal for one function to call another; it is also legal for a function to call itself. It may not be obvious why that is a good thing, but it turns out to be one of the most magical things a program can do. For example, look at the following function:
def countdown(n):
#print(f"called with {n}")
if n <= 0:
print('Blastoff!')
else:
print(n)
countdown(n-1)
countdown(8)
8 7 6 5 4 3 2 1 Blastoff!
A function that calls itself is recursive; the process of executing it is called recursion.
As another example, we can write a function that prints a string n times.
def print_n(s, n):
if n <= 0:
return
print(s,end='')
print_n(s, n-1)
print_n("abc ",10)
abc abc abc abc abc abc abc abc abc abc
by Ed:
Rercusive functions follow a pattern:
It's often easier and clearer to define a recursive solution than to use loops and variables.
The the function can take multiple arguments or the argument passed to the function can contain multiple values.
If the recursive call is the last statement in the function ("tail call") then recursion may not require space on the stack and there is no limit to the number of recursive calls (true in some languages, but unfortunately not in Python). Otherwise the maximum call stack depth may limit the amount of recursion (e.g. to 1000 nested calls).
Many types of problems can be defined as a graph with a tree structure.
To solve these problem we search through the tree for a node representing a solution (or often, the best solution).
Recursive algorithms are often used to search trees because each node can be the root of another tree. The recursive search algorithm is:
The tree may be a static data structure such as nested lists in Python or linked lists in C. In other cases the branches from each node can be computed. In this case we only need to keep track of the state of each node in the path to the current node.