Recursion

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):
    if n <= 0:
        print('Blastoff!')
    else:
        print(n)
        countdown(n-1)
        
countdown(3)

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("a",10)

aaaaaaaaaa

by Ed:

Rercusive functions follow a pattern:

• Return the function value immediately if the argument is simple enough. For example if a list argument is empty or a numeric argument has the desired final value (often zero or one).
• Otherwise compute the return value as a function of one or more calls to the same function with simpler arguments. The simplification must ensure that the recursion will eventually terminate (e.g. call the function recursively with a shorter list or a smaller numeric argument).

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).