Build a Memoized Recursive Function to Calculate the nth Generalized Fibonacci Number
Create a function that efficiently computes the nth term of a generalized Fibonacci sequence, where the first k terms are given and each subsequent term is the sum of the previous k terms. Implement memoization to optimize the recursive calculations.
Challenge prompt
Write a Python function named `generalized_fibonacci(n, k, initial_terms)` that returns the nth term of a generalized Fibonacci sequence. The sequence is defined by the first k terms provided in the list `initial_terms` (length k), and each term after these is the sum of the previous k terms. Your function must use recursion combined with memoization to handle large values of n efficiently. For example, for n=6, k=3, and initial_terms=[0, 0, 1], the sequence starts as 0, 0, 1, and then each next term is sum of previous 3 terms: 1, 2, 4, ... The function should return the exact nth term (1-indexed).
Guidance
- • Use a recursive helper function with a memo dictionary to store computed results and avoid redundant calculations.
- • Handle base cases by returning the initial terms directly when n ≤ k.
- • Carefully implement the sum of the previous k terms for terms beyond the initial sequence.
Hints
- • Think about the role of base cases in recursion and how they directly return values without further recursive calls.
- • Memoization can be implemented via a cache dictionary or the functools.lru_cache decorator.
Starter code
def generalized_fibonacci(n, k, initial_terms):
memo = {}
def helper(x):
# Your code here
pass
return helper(n)Expected output
For example: print(generalized_fibonacci(6, 3, [0, 0, 1])) # Output: 4 print(generalized_fibonacci(10, 2, [0, 1])) # Output: 34
Core concepts
Challenge a Friend
Send this duel to someone else and see if they can solve it.