Recursion visualizer

Fibonacci Recursion

Build each Fibonacci number from the two preceding recursive results.

Best O(1)Average O(2^n)Worst O(2^n)Space O(n)
Example Call
fibonacci(6)

Recursion Tree

Ready
Ready to evaluate fibonacci(6).fibonacci(6)
fib(6)waitingfib(5)waitingfib(4)waitingfib(3)waitingfib(2)waitingfib(1)waitingfib(0)waitingfib(1)waitingfib(2)waitingfib(1)waitingfib(0)waitingfib(3)waitingfib(2)waitingfib(1)waitingfib(0)waitingfib(1)waitingfib(4)waitingfib(3)waitingfib(2)waitingfib(1)waitingfib(0)waitingfib(1)waitingfib(2)waitingfib(1)waitingfib(0)waiting
Call stackEmpty
ActiveWaiting returnResolved

Metrics

Calls0
Returns0
Max depth0
Time taken0.0s

Pseudocode

  1. fibonacci(n)
  2. if n <= 1
  3. return n
  4. left = fibonacci(n - 1)
  5. right = fibonacci(n - 2)
  6. return left + right