Recursion
Recursion is a computational technique in which a definition or procedure refers to or invokes itself, directly or indirectly.
Fabulous Adventures in Data Structures and Algorithms
A recursive algorithm solves a problem by invoking itself on smaller or simpler instances together with terminating cases.
- How it is used
- Solves graph coloring, permutation generation, quadtree stepping, and term anti-unification by reducing each problem to smaller instances.
- How deep it goes
- Develops base cases, recursive calls, result assembly, and failure paths in C#; also examines lazy evaluation and stack-depth costs.
- Examples
- Uses a four-color map of South America, numbered change-ringing permutations, Life quads, and binary arithmetic terms.
- What you can do after
- Build it from scratch using explicit base cases, smaller calls, and result assembly; evaluate stack depth and deferred enumeration costs.
Read how Fabulous Adventures in Data Structures and Algorithms explains recursion →
Functional Programming in JavaScript
A problem-solving technique in which a process is defined in terms of smaller instances of itself until a base case is reached.
- How it is used
- Solves self-similar problems and parses recursively defined data structures in functional JavaScript.
- How deep it goes
- Defines base and recursive cases, traces array summation and tree traversal, then examines stack use and tail-call optimization.
- Examples
- Uses array summation, deep freezing, XML or HTML parsing, graph traversal, tree mapping, and factorial.
- What you can do after
- Apply it by writing terminating recursive functions and recognizing when tail-recursive state passing can reduce stack growth.
Read how Functional Programming in JavaScript explains recursion →
Software Design for Python Programmers
Recursion is a problem-solving technique that repeatedly applies the same procedure to progressively smaller instances of a problem until a terminating condition is reached.
- How it is used
- Uses repeated self-calls to reduce problems and explore solution paths in algorithms, trees, sorting, puzzles, and search.
- How deep it goes
- Explains reduction, base cases, unwinding, backtracking, implementations, and performance risks, but defers formal complexity analysis.
- Examples
- Demonstrates list algorithms, Towers of Hanoi, binary search trees, quicksort, Fibonacci computation, eight queens, and Sudoku.
- What you can do after
- Build it from scratch for shrinking subproblems, recursive data structures, sorting, and path-search programs with explicit termination.
Read how Software Design for Python Programmers explains recursion →
Object-Oriented Software Design in C++
A recursive algorithm is an algorithm whose definition or execution invokes the same algorithm on smaller instances of a problem.
- How it is used
- Explains recursive problem solving through progressively smaller subproblems, data structures, sorting, and path exploration.
- How deep it goes
- Develops base cases, unwinding, recursive data structures, backtracking, and performance risks through worked C++ examples.
- Examples
- Uses vector maximum and reversal, Towers of Hanoi, binary search trees, quicksort, Fibonacci, eight queens, and Sudoku.
- What you can do after
- Build recursive functions with base cases, trace unwinding, implement recursive structures and sorting, and diagnose repeated-call costs.
Read how Object-Oriented Software Design in C++ explains recursion →
Algorithms Every Programmer Should Know
Recursion is a technique in which a function directly or indirectly invokes itself to solve progressively smaller or simpler instances of a problem.
- How it is used
- Uses recursive backtracking to grow compatible vertex groups and enumerate maximal cliques without generating every graph subset.
- How deep it goes
- Traces recursive state, branching, stopping, and backtracking through a graph, then provides pseudocode and Python implementations.
- Examples
- Traces a small network to maximal cliques {1, 2, 4} and {2, 3, 5}, including a branch rejected through X.
- What you can do after
- Build it from scratch: implement recursive Bron–Kerbosch clique enumeration in Python, with an optional pivot variation.
Read how Algorithms Every Programmer Should Know explains recursion →
Type-Driven Development with Idris
A technique in which a definition refers to itself to solve a problem through smaller instances of that problem.
- How it is used
- Uses recursion to process structured data, construct interactive loops, and define functions with input-dependent types.
- How deep it goes
- Works through base cases, smaller recursive calls, REPL tests, and totality checks, while deferring fuller treatment of totality.
- Examples
- Demonstrates an evenness test, word-length lists, countdown loops, a variable-argument adder, and natural-number equality.
- What you can do after
- Build recursive Idris functions and check examples and totality in the REPL.
Read how Type-Driven Development with Idris explains recursion →
Modern C
Recursion is a technique in which a computation is defined or performed through calls or applications that refer to the same computation.
- How it is used
- Uses recursion to compute numerical results and process nested text.
- How deep it goes
- Traces recursive calls and local instances, then examines repeated computation and shared state.
- Examples
- Uses Euclid’s greatest common divisor algorithm, Fibonacci calculations, and a brace-indenting parser.
- What you can do after
- Evaluate and understand recursive call sequences, stopping cases, repeated work, and shared state.
Learn Haskell by Example
Recursion is a technique in which a computation is defined in terms of applications of itself to smaller or simpler inputs.
- How it is used
- Replaces loops and mutable counters when traversing lists or repeatedly performing IO actions.
- How deep it goes
- Works through base cases, list patterns, recursive steps, partial-function failures, and a parameterized IO loop.
- Examples
- Uses listLength, indexOf, an exercise to implement (!!), and an interactive line-numbering action.
- What you can do after
- Build it from scratch for list traversal and apply it to simulate a counter-driven IO loop.
Modern C, Third Edition
Recursion is a technique in which a computation is defined or performed by calls to the same computation on smaller or simpler inputs.
- How it is used
- Uses recursive functions to expose the C function-call model and implement computations over smaller inputs or nested structures.
- How deep it goes
- Explains per-call variables, stopping conditions, recursive reduction, repeated work, and cached running time; also discusses unbounded recursion and compiler transformation.
- Examples
- Traces a greatest-common-divisor calculation, compares recursive Fibonacci implementations, and applies recursive descent to brace indentation.
- What you can do after
- Evaluate/understand recursive C functions by tracing calls, checking progress toward a base case, and recognizing repeated computation.
Classic Computer Science Problems in Swift: Essential techniques for practicing programmers
An algorithm that solves a problem by invoking itself on smaller instances of the same problem.
- How it is used
- Uses self-calls to express algorithms whose smaller subproblems resemble the original problem.
- How deep it goes
- Develops base cases, recursive cases, repeated-work memoization, and iterative alternatives through Swift examples rather than formal proofs.
- Examples
- Demonstrates Fibonacci computation and Towers of Hanoi using recursive Swift functions and stack-backed towers.
- What you can do after
- Build recursive Swift functions with explicit stopping conditions, recognize repeated work, and substitute memoized or iterative implementations.
Grokking Algorithms, Second Edition
Recursion is a problem-solving technique in which a procedure solves a problem by invoking itself on smaller or simpler instances of that problem.
- How it is used
- Uses self-calling functions to express repeated searches and to build divide-and-conquer solutions.
- How deep it goes
- Works through stopping cases and call-stack behavior, while deferring tail recursion and a proof of the land-tiling reduction.
- Examples
- Illustrates self-calls with nested-box searches, countdown, factorial, and square tiling of a rectangular plot.
- What you can do after
- Build it from scratch with a stopping case and self-call, then assess its stack-memory cost against a loop.
Read how Grokking Algorithms, Second Edition explains recursion →
Grokking Simplicity
A programming technique in which a computation is defined in terms of one or more calls to the same computation.
- How it is used
- Operates on arbitrarily deep nested data when ordinary array iteration is insufficient.
- How deep it goes
- Explains base cases, recursive cases, progress toward termination, call-stack behavior, and loops-versus-recursion tradeoffs.
- Examples
- Uses nestedUpdate() and incrementSizeByName() to modify values at known paths inside nested cart data.
- What you can do after
- Apply it via nestedUpdate() to modify values at known paths in deeply nested data.
Elixir in Action, Third Edition
Recursion is a technique in which a computation invokes itself on a smaller, simpler, or continuing input until reaching a terminating or deliberately nonterminating case.
- How it is used
- Implements looping and long-running server behavior where higher-level iteration abstractions or process abstractions do not hide the mechanism.
- How deep it goes
- Explains base cases, recursive clauses, list decomposition, tail-call optimization, accumulators, and stack-space behavior.
- Examples
- Demonstrates factorial, natural-number printing, direct list summation, and accumulator-based tail-recursive summation.
- What you can do after
- Build it from scratch: write recursive loops with terminating clauses, process lists, and convert suitable functions to tail-recursive form.
Read how Elixir in Action, Third Edition explains recursion →
The Joy of JavaScript
A technique in which a function calls itself directly or indirectly to solve a problem by reducing it to smaller instances.
- How it is used
- Uses recursion to eliminate iterative state in functional code and traverse nested blockchain objects for validation.
- How deep it goes
- Explains base cases, carried state, self-calls, and recursive tree traversal, while deferring detailed symbol and iteration treatment.
- Examples
- Demonstrates recursive hashing over string data and recursive validation across blockchains, blocks, and transactions.
- What you can do after
- Build it from scratch by converting stateful loops into recursive functions and composing recursive validation across nested objects.
Grokking AI Algorithms, Second Edition
A programming technique in which a function or algorithm calls itself until an exit condition is reached.
- How it is used
- Uses self-calls to explore future game states during Minimax search.
- How deep it goes
- Traces copied states, terminal checks, depth reduction, and returned scores; stops short of general recursion patterns.
- Examples
- Demonstrates recursion by exploring Connect Four moves until wins, draws, full boards, or depth limits.
- What you can do after
- Apply recursion in Minimax search to explore candidate moves and return a best move.
Read how Grokking AI Algorithms, Second Edition explains recursion →
Building User-Friendly DSLs
A computation technique in which a procedure solves a problem by invoking itself on smaller or nested instances of that problem.
- How it is used
- Uses self-calls to implement generic depth-first traversal and compute properties of abstract syntax trees.
- How deep it goes
- Explains recursive dispatch, subtree aggregation, and backtracking through returns, without detailing JavaScript engine internals.
- Examples
- Demonstrates generic AST traversal and counts leaves in a rental AST with numberOfLeaves.
- What you can do after
- Build it from scratch by writing recursive JavaScript functions that traverse AST objects, references, arrays, and nested values.
100 Java Mistakes and How to Avoid Them
Recursion is a programming technique in which a method or algorithm invokes itself to solve a problem through smaller subproblems.
- How it is used
- Uses self-calls to express algorithms over smaller subproblems, especially cleanly for tree traversal.
- How deep it goes
- Explains stack consumption, JVM-dependent limits, tail-call optimization, iterative rewrites, and cycle risks.
- Examples
- Uses recursive summation, string index search, and named-node tree search with recursive and iterative implementations.
- What you can do after
- Diagnose stack-overflow risks, rewrite tail recursion as iteration, and choose heap-based traversal for deeper searches.
Read how 100 Java Mistakes and How to Avoid Them explains recursion →
Julia as a Second Language
Recursion is a programming technique in which a computation invokes itself on smaller or simpler inputs until a terminating condition is reached.
- How it is used
- Introduces recursion as a control-flow alternative to loops for repeated computation.
- How deep it goes
- Explains base cases and stack overflow through factorial and Fibonacci, then compares recursive and iterative implementations.
- Examples
- Uses a nonterminating factorial function and recursive Fibonacci calculation motivated by rabbit population growth.
- What you can do after
- Evaluate recursion against iteration for simplicity and performance, and identify a missing base case.
Practical Automation with PowerShell: Effective scripting from the console to the cloud
Recursion is the repeated traversal or invocation of nested structures through a self-referential operation.
- How it is used
- Optimizes watcher scripts by limiting searches to relevant nested locations.
- How deep it goes
- Compares recursive and scoped traversal with runtime evidence, but stops short of implementing recursion itself.
- Examples
- Uses nested folders and Active Directory site OUs to contrast broad recursive searches with targeted queries.
- What you can do after
- Apply it via PowerShell by replacing broad recursive searches with targeted commands or separate watchers.
C++ Concurrency in Action, Second Edition
Recursion is a technique in which a function or process calls itself to solve smaller instances of a problem.
- How it is used
- Uses recursive task division when data chunks become clear only through processing, as in Quicksort.
- How deep it goes
- Explains recursive Quicksort calls and concurrency choices, including thread-count risks and alternatives.
- Examples
- Uses Quicksort partitioning and recursive accumulate reduction to illustrate recursive work division.
- What you can do after
- Evaluate recursive tasks for concurrent execution by checking data independence and controlling thread creation.
Read how C++ Concurrency in Action, Second Edition explains recursion →
Functional Programming in Scala, Second Edition
Recursion is a technique in which a computation solves a problem by calling itself on smaller or simpler inputs.
- How it is used
- Expresses loops functionally without mutating a loop variable.
- How deep it goes
- Explains helper state, base cases, execution traces, tail position, and tail call elimination through factorial.
- Examples
- Uses factorial, a recursive helper named go, and indented or flat execution traces for factorial(5).
- What you can do after
- Build recursive Scala loops, trace their evaluation, and recognize when tail recursion prevents stack growth.
Read how Functional Programming in Scala, Second Edition explains recursion →
Clojure: The Essential Reference
Recursion is a computation technique in which a function invokes itself, directly or through other functions, on a successive subproblem or state.
- How it is used
- Replaces mutation-driven loops with functional iteration that passes successive state through arguments.
- How deep it goes
- Defines targets, exit conditions, and tail calls, then works through a loop-recur collection example.
- Examples
- Uses square collection and counter accumulation examples, alongside Java for and do-while contrasts.
- What you can do after
- Apply it via Clojure loop and recur to build iteration without mutating loop variables.
Read how Clojure: The Essential Reference explains recursion →
Natural Language Processing in Action, Second Edition
Recursion is a computational process in which an operation invokes itself or reuses its output as input until a termination condition is reached.
- How it is used
- Explains repeated input-output recycling in recursive algorithms, RNNs, and autoregressive transformer generation.
- How deep it goes
- Defines recursion, distinguishes it from recurrence, and emphasizes termination but stops short of implementing a recursive function.
- Examples
- Uses recursive token generation, RNN memory, transcription, translation, algorithmic trading, and code generation as examples.
- What you can do after
- Evaluate recursive NLP architectures and recognize why termination and decreasing work matter for safe repeated computation.
Read how Natural Language Processing in Action, Second Edition explains recursion →
The Well-Grounded Python Developer: How the pros use Python and Flask
Recursion is a technique in which an operation is repeatedly applied to progressively nested or related instances of the same kind of structure.
- How it is used
- Traverses self-referential comment hierarchies so web applications can display nested content in meaningful order.
- How deep it goes
- Explains recursive tree traversal and its stopping and return behavior, then connects it to recursive SQL CTEs without detailing the full query.
- Examples
- Uses a MyBlog content post with nested comment posts represented as a tree.
- What you can do after
- Apply recursion via SQLAlchemy and recursive CTEs to retrieve hierarchies from self-referential database tables.
Read how The Well-Grounded Python Developer: How the pros use Python and Flask explains recursion →
The Well-Grounded Rubyist, Fourth Edition
Recursion is a programming technique in which a routine invokes itself, directly or indirectly, to solve a problem through progressively smaller or simpler subproblems.
- How it is used
- Uses self-calling functions to express iteration without side effects, especially in functional programming.
- How deep it goes
- Explains terminal clauses, argument reduction, and per-call local scope, while deferring a full treatment of recursion.
- Examples
- Demonstrates recursive method scope, Fibonacci evaluation, pattern-matching Fibonacci, and recursively computed sums of squares.
- What you can do after
- Apply via Ruby by writing recursive Fibonacci and sum-of-squares functions with explicit terminal clauses.
Read how The Well-Grounded Rubyist, Fourth Edition explains recursion →
Also covered in
- Latency
- Quantum Programming in Depth
- 100 C++ Mistakes and How to Avoid Them
- .NET in Action, Second Edition
- Functional Programming in C#, Second Edition
- Elliptic Curve Cryptography for Developers
- Functional Design and Architecture: Examples in Haskell
- Build a Frontend Web Framework (From Scratch)
What to know first
- loopA loop is a programming-language control-flow construct that repeatedly executes a block of instructions according to an iteration rule or continuation condition.
- arrayAn array is an ordered collection of elements organized in one or more dimensions and accessible by position or index.
- factorialThe factorial of a nonnegative integer n, written n!, is the product of all positive integers from 1 through n, with 0! equal to 1.
- functionA function is a callable unit of program code that performs a computation or operation, can accept inputs, and may produce a result or side effect.
Related concepts
- stopping criterionhas part · A stopping criterion is a condition or rule that determines when a process, computation, or sequence of actions should end.
- tail recursionincludes · Tail recursion is recursion in which the recursive call is the final operation of the current function invocation.
- quicksortused by · Quicksort is a comparison-based sorting algorithm that partitions elements around a pivot and recursively sorts the resulting partitions.
- depth-first searchimplements · Depth-first search is a traversal strategy that follows a branch as far as possible before backtracking to explore alternatives.
- minimax algorithmused by · A game-search algorithm that alternates maximizing an agent's score and minimizing the opponent's score while exploring possible future moves.
- Towers of Hanoi puzzleused by · The Towers of Hanoi is a puzzle requiring a stack of differently sized disks to move among three pegs, one disk at a time, without placing a larger disk on a smaller one.
Questions about recursion
What is recursion?
Recursion is a computational technique in which a definition or procedure refers to or invokes itself, directly or indirectly.
Which Manning books explain recursion?
Fabulous Adventures in Data Structures and Algorithms, Functional Programming in JavaScript, Software Design for Python Programmers, Object-Oriented Software Design in C++, Algorithms Every Programmer Should Know, Type-Driven Development with Idris, Modern C, Learn Haskell by Example and 17 more.
What should I know before learning recursion?
Manning books that teach recursion usually introduce loop, array, factorial and function first.
What kinds of recursion are there?
Kinds of recursion include tail recursion.
What are the parts of recursion?
Recursion includes stopping criterion.
What is recursion also called?
Recursion is also called recursive.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.
























