8Recursion
Recursion is a deceptively simple concept: any function that calls itself is recursive. Despite this apparent simplicity, understanding and applying recursion can be surprisingly complex. One of the major barriers to understanding recursion is that general descriptions tend to become highly theoretical, abstract, and mathematical. Although there is certainly value in that approach, this chapter instead follows a more pragmatic course, focusing on example, application, and comparison of recursive and iterative (nonrecursive) algorithms.
UNDERSTANDING RECURSION
Recursion is useful for tasks that can be defined in terms of similar subtasks. For example, sort, search, and traversal problems often have simple recursive solutions. A recursive function performs a task in part by calling itself to perform the subtasks. At some point, the function encounters a subtask that it can perform without calling itself. This case, in which the function does not recurse, is called the base case; the former, in which the function calls itself to perform a subtask, is referred to as the recursive case.
These concepts can be illustrated with a simple and commonly used example: the factorial operator. n! (pronounced “n factorial”) is the product of all integers between n and 1. For example, 4! = 4 · 3 · 2 · 1 = 24. n! can be more formally defined as follows:
n! = n (n – 1)!
0! = 1! = 1
This definition leads ...
Get Programming Interviews Exposed, 4th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.