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

509. Fibonacci Number

#180DaysOfDSA#DailyCodingChallenge #LeetCodeJourney #GeeksforGeeks #CodingNinjas #Codechef #CodeForces #ContinuousLearning #TechCommunity

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

Here is the code again for reference:

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.