Calculating Groot's Growth - codepath/compsci_guides GitHub Wiki

TIP102 Unit 7 Session 1 Standard (Click for link to problem statements)

Problem 4: Calculating Groot's Growth

Groot grows according to a pattern similar to the Fibonacci sequence. Given n, find the height of Groot after n months using a recursive method.

The Fibonacci numbers, commonly denoted F(n), form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 20 mins
  • 🛠️ Topics: Recursion, Fibonacci Sequence

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • Q: What is the main task in this problem?
    • A: The task is to calculate the height of Groot after n months using the Fibonacci sequence.
  • Q: Are there any special cases for small values of n?
    • A: Yes, the base cases are when n = 0 and n = 1.
HAPPY CASE
Input: 5
Output: 5
Explanation: The 5th Fibonacci number is 5.

Input: 8
Output: 21
Explanation: The 8th Fibonacci number is 21.

EDGE CASE
Input: 0
Output: 0
Explanation: The 0th Fibonacci number is 0.

Input: 1
Output: 1
Explanation: The 1st Fibonacci number is 1.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Recursive Fibonacci Problems, we want to consider the following approaches:

  • Recursive Calculation: Calculate the Fibonacci number by summing the two preceding numbers in the sequence with base cases for n = 0 and n = 1.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:

  • Use a recursive function to calculate the Fibonacci number at position n. Define the base cases for n = 0 and n = 1.

Recursive Approach:

1) Base case: If `n` is 0, return 0.
2) Base case: If `n` is 1, return 1.
3) Recursive case: Return the sum of `fibonacci_growth(n - 1)` and `fibonacci_growth(n - 2)`.

⚠️ Common Mistakes

  • Forgetting to define the base cases, which would lead to infinite recursion.
  • Misunderstanding the Fibonacci sequence and incorrectly summing the terms.

4: I-mplement

Implement the code to solve the algorithm.

def fibonacci_growth(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_growth(n - 1) + fibonacci_growth(n - 2)

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Trace through the fibonacci_growth function with the input 5. The function should return 5 after calculating fibonacci_growth(4) and fibonacci_growth(3) recursively.
  • Trace through the function with the input 8. The function should return 21 after recursively calculating fibonacci_growth(7) and fibonacci_growth(6).

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

  • Time Complexity: O(2^N) where N is the input n. The function makes two recursive calls for each non-base case, leading to exponential growth in the number of calls.
  • Space Complexity: O(N) due to the recursion stack. The depth of the recursion is proportional to n, leading to linear space usage.