Branching Recursion and Multiple Work

Branching recursion generates multiple calls per frame, such as naive Fibonacci: fib(n) = fib(n-1) + fib(n-2). The number of calls grows exponentially, and many subproblems are repeated.

Countermeasures: Memoization, dynamic programming, or closed formulas.

Be able to distinguish the complexity of the naive variant from the linear DP variant.

$$T(n)=T(n-1)+T(n-2)+\Theta(1)$$

The same split, linear work: Fibonacci Number [1].

Where used

Unmemoized search trees, naive recursive layouts, exponential parser variants. The same structure is found in Divide-and-Conquer (Merge Sort) and in Backtracking; the difference is whether subproblems overlap and whether results are stored.

Depth

In branching recursion, multiple subproblems arise from a single problem. The runtime depends not only on the depth but also on the number of nodes in the resulting call tree.

Naive Fibonacci computation repeatedly solves the same arguments. Memoization stores results by argument and reduces the call tree to the number of different subproblems. Dynamic programming calculates the same dependencies in an ordered manner without recursion.

Not every branching means duplicate work. In Divide-and-Conquer methods, disjoint subproblems can occur; then the work for splitting and combining additionally determines the recurrence.

Difficulty levels

1. Draw a small call tree.
2. Distinguish between repeated and disjoint subproblems.
3. Analyze a recurrence with memoization or divide-and-conquer structure.

Pitfalls

The recursion depth alone does not describe the runtime. Memoization helps only when states are unambiguous and can be stored as keys with reasonable effort.