Nth Tribonacci Number
Problem
The Tribonacci sequence starts with T(0) = 0, T(1) = 1 and T(2) = 1, and every later term is the sum of the three before it: T(n) = T(n - 1) + T(n - 2) + T(n - 3). Given n with 0 ≤ n ≤ 37, return T(n).
Examples
Input: n = 4
Output: 4
Why: the sequence runs 0, 1, 1, 2, 4Input: n = 25
Output: 1389537Input: n = 0
Output: 0
Why: edge case, the first seed valueHints
0 / 3
The definition is already a recursive function. Draw its call tree for n = 6 and count how often T(3) is computed.
Every call branches three ways, so the plain recursion does about 1.84 to the power n calls. Each value only ever depends on the three values just before it.
Keep the last three terms in three variables and slide them forward n times: the new triple is the old second, the old third and the sum of all three.
Solution
The recursive definition is correct but recomputes the same terms again and again, exactly like the naive Fibonacci in the lesson, only worse, since each call spawns three more instead of two. Memoization would fix that, but the dependency is so short that there is nothing to cache beyond three numbers. The loop keeps T(i), T(i + 1) and T(i + 2) and shifts the window one step per iteration, so after n steps the first slot holds T(n). Time is O(n) and space is O(1), and n up to 37 keeps the answer within a 32-bit integer.
def tribonacci(n):
a, b, c = 0, 1, 1 # T(0), T(1), T(2)
for _ in range(n):
a, b, c = b, c, a + b + c # slide the window one term forward
return a
print(tribonacci(4)) # -> 4
print(tribonacci(25)) # -> 1389537
print(tribonacci(0)) # -> 0Stuck on the idea rather than the code? Factorial and Fibonacci covers it.