Tracing the Fibonacci function (Tree)

COSC 2306: Data Programming - Recursive Branching Call Stack Visualizer

Execution Tree

Tree is currently empty.
Click "Step" or "Run Trace" to trace the slide example.

Controls (Parameters)

Default values match the exact execution tree shown on Slide 9.

# Fibonacci branching visualizer ready.

Understanding Recursive Branching & Inefficiency

Unlike the Factorial function, which makes a single linear line of recursive calls, this Fibonacci implementation makes two recursive calls inside its general case: rFibNum(n-1) + rFibNum(n-2).

  • Execution Order: The computer evaluates depth-first. It fully travels down the left branch (n-1) until a base case is hit, before ever attempting the right branch (n-2).
  • The Redundancy Problem: Observe the tree closely as it completes. Notice how functions like rFibNum(2,3,2) are evaluated multiple times! This redundancy leads to an exponential \(O(2^n)\) time complexity.
  • The Solution (Memoization): As shown on Slide 11, saving results in a cache dictionary prevents recalculating a node that has already been split and solved.
Python Implementation (Slide 8) 
def rFibNum(a, b, n):
    if n == 1:
        return a
    elif n == 2:
        return b
    else:
        return rFibNum(a, b, n-1) + rFibNum(a, b, n-2)