Home > Articles

This chapter is from the book

This chapter is from the book

5.13 Recursion

Python supports recursive functions. For example:

def sumn(n):
    if n == 0:
        return 0
    else:
        return n + sumn(n-1)

However, there is a limit on the depth of recursive function calls. The function sys.getrecursionlimit() returns the current maximum recursion depth, and the function sys.setrecursionlimit() can be used to change the value. The default value is 1000. Although it is possible to increase the value, programs are still limited by the stack size enforced by the host operating system. When the recursion depth limit is exceeded, a RuntimeError exception is raised. If the limit is increased too much, Python might crash with a segmentation fault or another operating system error.

In practice, issues with the recursion limit only arise when you work with deeply nested recursive data structures such as trees and graphs. Many algorithms involving trees naturally lend themselves to recursive solutions—and, if your data structure is too large, you might blow the stack limit. However, there are some clever workarounds; see Chapter 6 on generators for an example.

InformIT Promotional Mailings & Special Offers

I would like to receive exclusive offers and hear about products from InformIT and its family of brands. I can unsubscribe at any time.