Skip to Main Content
Programming Interviews Exposed, 4th Edition
book

Programming Interviews Exposed, 4th Edition

by John Mongan, Noah Suojanen Kindler, Eric Giguere
April 2018
Beginner content levelBeginner
384 pages
11h 3m
English
Wrox
Content preview from Programming Interviews Exposed, 4th Edition

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

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Beyond Vibe Coding

Beyond Vibe Coding

Addy Osmani
The Programmer's Brain

The Programmer's Brain

Felienne Hermans
Programming Rust, 2nd Edition

Programming Rust, 2nd Edition

Jim Blandy, Jason Orendorff, Leonora F. S. Tindall

Publisher Resources

ISBN: 9781119418474Purchase book