# 🚀Day 13/180 509. Fibonacci Number (Leetcode)

[**509\. Fibonacci Number**](https://leetcode.com/problems/fibonacci-number/description/)

[#180DaysOfDSA#](https://leetcode.com/problems/single-number/)[Da](https://leetcode.com/problems/hamming-distance/)[ilyCodingChallenge](https://leetcode.com/problems/single-number/) #LeetCodeJourney #GeeksforGeeks #CodingNinjas #Codechef #CodeForces #ContinuousLearning #TechCommunity

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1720632832488/7ac834f8-5a67-4df8-b714-757336d007f3.png align="center")

Sure, let's do a dry run of the provided recursive function for `n = 4`.

Here is the code again for reference:

```java
class Solution {
    public int fib(int n) {
        if (n == 1 || n == 0) {
            return n;
        }
        int first = fib(n - 1);
        int second = fib(n - 2);
        return first + second;
    }
}
```

### Dry Run for `n = 4`:

1. **Call** `fib(4)`
    
    * `n` is neither 0 nor 1, so we proceed to calculate `fib(3)` and `fib(2)`.
        
2. **Call** `fib(3)`
    
    * `n` is neither 0 nor 1, so we proceed to calculate `fib(2)` and `fib(1)`.
        
3. **Call** `fib(2)`
    
    * `n` is neither 0 nor 1, so we proceed to calculate `fib(1)` and `fib(0)`.
        
4. **Call** `fib(1)`
    
    * `n` is 1, so we return 1.
        
5. **Call** `fib(0)`
    
    * `n` is 0, so we return 0.
        
6. **Return to** `fib(2)`
    
    * We have `fib(1) = 1` and `fib(0) = 0`.
        
    * `fib(2)` returns `1 + 0 = 1`.
        
7. **Return to** `fib(3)`
    
    * We have `fib(2) = 1` (from step 6) and need to calculate `fib(1)` again.
        
8. **Call** `fib(1)`
    
    * `n` is 1, so we return 1.
        
9. **Return to** `fib(3)`
    
    * We have `fib(2) = 1` and `fib(1) = 1`.
        
    * `fib(3)` returns `1 + 1 = 2`.
        
10. **Return to** `fib(4)`
    
    * We have `fib(3) = 2` (from step 9) and need to calculate `fib(2)` again.
        
11. **Call** `fib(2)`
    
    * `n` is neither 0 nor 1, so we proceed to calculate `fib(1)` and `fib(0)`.
        
12. **Call** `fib(1)`
    
    * `n` is 1, so we return 1.
        
13. **Call** `fib(0)`
    
    * `n` is 0, so we return 0.
        
14. **Return to** `fib(2)`
    
    * We have `fib(1) = 1` and `fib(0) = 0`.
        
    * `fib(2)` returns `1 + 0 = 1`.
        
15. **Return to** `fib(4)`
    
    * We have `fib(3) = 2` and `fib(2) = 1`.
        
    * `fib(4)` returns `2 + 1 = 3`.
        

### Final Result:

The call `fib(4)` returns 3, which is the 4th Fibonacci number.

The recursive calls create a tree-like structure where many subproblems are solved multiple times, indicating the inefficiency of this approach.