Tribonacci, three-way recursion but still linear

Question

The Tribonacci sequence sums the previous three terms: so it runs 0, 1, 1, 2, 4, 7, 13, 24, 44, \dots Why is the naive recursion even worse than Fibonacci here, and how do you get it to O(n)?

Accepted Answer

Every call now spawns three recursive calls instead of two, so the recursion tree fans out faster: the call count grows like 	au^n where 	au \approx 1.839 (the tribonacci constant), a steeper exponential than Fibonacci's 1.618^n. The reason is the same though: massive recomputation of a tiny set of distinct subproblems. There are only n+1 of them. Keep three rolling values and sweep upward, O(n) time and O(1) space: Trace trib(6): starting (0,1,1), the loop steps to (1,1,2), (1,2,4), (2,4,7), (4,7,13), returning 13, which matches T(6). Takeaway. More branches per call means a steeper expone…

Tribonacci, three-way recursion but still linear

Your answer

More Coding questions