Recursion & Backtracking
Visualize recursive algorithms and understand how the call stack works. See how complex problems can be solved by breaking them down into smaller subproblems.
Fibonacci Sequence
The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1.
Time: O(2ⁿ)
Space: O(n)
Speed50%
Select an algorithm and click Start to visualize recursion
How the Fibonacci Sequence Works: The Fibonacci sequence is defined recursively where each number is the sum of the two preceding ones.
- The sequence starts with 0 and 1 (or sometimes 1 and 1)
- Each subsequent number is the sum of the two preceding numbers
- The recursive definition is:
- F(0) = 0 (base case)
- F(1) = 1 (base case)
- F(n) = F(n - 1) + F(n - 2) for n > 1 (recursive case)
The recursive implementation of Fibonacci demonstrates how a problem can be broken down into smaller subproblems. However, it's inefficient due to repeated calculations, making it a classic example for teaching dynamic programming.