Like Fibonacci, but each term is the sum of the previous three. Define
T(0)=0, T(1)=1, T(2)=1, and T(n)=T(n-1)+T(n-2)+T(n-3). Return T(n)
efficiently.
tribonacci(n)
Assume n >= 0.
tribonacci(4) // → 4 (0,1,1,2,4)
tribonacci(7) // → 24
tribonacci(0) // → 0
T(n) = T(n-1) + T(n-2) + T(n-3) looks like Fibonacci but with three prior terms and three base cases. Translated directly into recursion, each call spawns three more, so the naive tree grows even faster than Fibonacci's — roughly O(3ⁿ). The same T(k) gets asked for repeatedly by different branches.
Recursive calls depend only on a single integer argument — "what is the tribonacci value at index k?" Only n+1 distinct questions exist for a given n, but the naive recursion asks the same one exponentially many times. Few distinct questions, many repeated askings — memoization applies.
T(0)=0, T(1)=1, T(2)=1.T(k), check the cache — if present, return immediately.T(k-1) + T(k-2) + T(k-3), store under key k, return it.Since every distinct k from 0 to n is computed exactly once, total work drops from exponential to O(n).
Instead of top-down recursion with a cache, build bottom-up: start from the three base values and iteratively compute T(3), T(4), ... up to T(n), storing each as you go. Same subproblems, same total work, just built forwards instead of lazily on demand. Either direction, the realization is the same: only a handful of genuinely distinct subproblems exist, and caching converts many repeated evaluations into one computation plus fast lookups.
def tribonacci(n):
memo = {0: 0, 1: 1, 2: 1}
def t(k):
if k in memo:
return memo[k]
v = t(k - 1) + t(k - 2) + t(k - 3)
memo[k] = v
return v
return t(n)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.