上QQ阅读APP看书，第一时间看更新

Recursive functions

When a function calls itself to produce a result, it is said to be recursive. Sometimes recursive functions are very useful in that they make it easier to write code. Some algorithms are very easy to write using the recursive paradigm, while others are not. There is no recursive function that cannot be rewritten in an iterative fashion, so it's usually up to the programmer to choose the best approach for the case at hand.

The body of a recursive function usually has two sections: one where the return value depends on a subsequent call to itself, and one where it doesn't (called a base case).

As an example, we can consider the (hopefully familiar by now) factorial function, N!. The base case is when N is either 0 or 1. The function returns 1 with no need for further calculation. On the other hand, in the general case, N! returns the product 1 * 2 * ... * (N-1) * N. If you think about it, N! can be rewritten like this: N! = (N-1)! * N. As a practical example, consider 5! = 1 * 2 * 3 * 4 * 5 = (1 * 2 * 3 * 4) * 5 = 4! * 5.

Let's write this down in code:

# recursive.factorial.py
def factorial(n):
    if n in (0, 1):  # base case
        return 1
    return factorial(n - 1) * n  # recursive case

When writing recursive functions, always consider how many nested calls you make, since there is a limit. For further information on this, check out sys.getrecursionlimit() and sys.setrecursionlimit().

Recursive functions are used a lot when writing algorithms and they can be really fun to write. As an exercise, try to solve a couple of simple problems using both a recursive and an iterative approach.