Multiple recursion

As explained in Modern C, Third Edition

Multiple recursion is recursion in which one invocation makes more than one recursive call.

Multiple recursion occurs when one invocation makes more than one recursive call. The Fibonacci implementation below branches into two calls for every n greater than two, creating a recursive call tree with repeated subproblems. section 7.3

Naive recursive Fibonacci

size_t fib(size_t n) { if (n < 3) return 1; return fib(n-1) + fib(n-2); } The repeated calls make execution time exponential in n. For example, computing fib(4) recomputes fib(2). section 7.3

Use these rules when evaluating multiple recursion:

• Expect exponential computation times when recursive branches repeatedly solve the same subproblems. section 7.3
• Trade storage for computation time with a cache; cached Fibonacci recursion reduces execution time to linear in n. section 7.3

Figure 7.2 Recursive call fib(4)

Trace the recursive call tree for fib(4) and locate repeated subcalls. section 7.3

How Modern C, Third Edition covers it

How deep it goes

Derives exponential and linear execution-time behavior, then stops short of concrete timing measurements.

Examples

Uses fib(n), the fib(4) call tree, and cached Fibonacci implementations as concrete examples.

What you can do after

Evaluate recursive algorithm costs and apply caching to reduce repeated Fibonacci computation.

How it connects

Connects recursion with Fibonacci sequences, caching, repeated subproblems, and algorithmic performance.

liveBookmanning.com

Read Modern C, Third Edition on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Modern CMultiple recursion is recursion in which one invocation makes more than one recursive call.

Compare how 2 books explain multiple recursion →

Related concepts

• exponential time complexityproduces · Exponential time complexity is a computational growth rate in which an algorithm’s running time increases exponentially with input size.

This explainer was generated by Manning's knowledge graph from the text of Modern C, Third Edition. The section links point to the parts of the book it draws on.