pythonadvanced15 minutes

Build a High-Performance Memoized Recursive Function for Multivariate Fibonacci Sequence

Create a Python function that computes terms of a custom multivariate Fibonacci sequence with dynamic step parameters and optimized with memoization for high performance.

Challenge prompt

Design and implement a Python function `multi_fib(n, k)` that returns the nth term of a generalized Fibonacci sequence where each term is the sum of the previous k terms. For example, if k=2, it's the classic Fibonacci sequence; if k=3, each term is the sum of the previous three terms, and so forth. The base cases for indices less than or equal to zero should be 0, and for indices 1 through k, the terms should each be 1. Ensure your function uses memoization to optimize performance for large n and k values.

Guidance

• Implement base cases clearly to handle indices less than or equal to zero, and initial terms up to k.
• Use memoization (caching) to avoid recomputing previously calculated terms and achieve optimal time complexity.
• Ensure your function can handle large values of n and k efficiently without exceeding recursion limits.

Hints

• Use a dictionary or functools.lru_cache for memoizing recursive calls.
• Think carefully about the recursive relation: multi_fib(n, k) = sum of multi_fib(n-1, k) + multi_fib(n-2, k) + ... + multi_fib(n-k, k).
• Consider iteration instead of pure recursion if recursion depth is a concern.

Starter code

def multi_fib(n, k):
    # Your implementation here
    pass

Expected output

multi_fib(6, 3) -> 13 multi_fib(10, 2) -> 55 multi_fib(5, 5) -> 16

Core concepts

recursionmemoizationdynamic programmingmathematical sequences

Challenge a Friend

Send this duel to someone else and see if they can solve it.