Problem

The Tetranacci sequence generalizes Fibonacci and Tribonacci: each term after the first four is the sum of the previous four.

Recurrence (0-indexed):

T(0) = 0, T(1) = 1, T(2) = 1, T(3) = 2 T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4) for n ≥ 4.

First terms (n = 0..10): 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, …

Given n, compute T(n).

Examples

1
2
3
4
5
6
7
8

Input: n = 5
Output: 4

Input: n = 9
Output: 108

Input: n = 0
Output: 0
Similar Problems

Solution

We explore multiple methods, from exponential recursion to O(log n) matrix exponentiation.

Method 1 - Naive Recursion (Exponential)

Intuition

Directly apply the recurrence. Massive recomputation occurs (each call branches into 4 smaller calls) → exponential blowup.

Approach

Base return for n = 0..3. Otherwise sum of previous four recursive calls.

Code

1
2
3
4

long long tetranacciRec(int n){
  if(n==0) return 0; if(n==1||n==2) return 1; if(n==3) return 2;
  return tetranacciRec(n-1)+tetranacciRec(n-2)+tetranacciRec(n-3)+tetranacciRec(n-4);
}
1
2
3
4
5
6

func tetranacciRec(n int) int64 {
  if n == 0 { return 0 }
  if n == 1 || n == 2 { return 1 }
  if n == 3 { return 2 }
  return tetranacciRec(n-1) + tetranacciRec(n-2) + tetranacciRec(n-3) + tetranacciRec(n-4)
}
1
2
3
4
5
6

class TetraRec {
  long tetranacci(int n){
    if(n==0) return 0; if(n==1||n==2) return 1; if(n==3) return 2;
    return tetranacci(n-1)+tetranacci(n-2)+tetranacci(n-3)+tetranacci(n-4);
  }
}
1
2
3
4
5
6
7
8
9

def tetranacci_rec(n: int) -> int:
  if n == 0:
    return 0
  if n in (1,2):
    return 1
  if n == 3:
    return 2
  return (tetranacci_rec(n-1) + tetranacci_rec(n-2) +
      tetranacci_rec(n-3) + tetranacci_rec(n-4))

Complexity

  • ⏰ Time complexity: O(4^n) – 4-way branching, large overlap.
  • 🧺 Space complexity: O(n) – recursion depth.

Method 2 - Top-Down Memoization

Intuition

Cache each n after first computation; each state depends on four smaller indices → linear number of states.

Approach

  1. Allocate memo array size n+1, initialize with sentinel (e.g. -1).
  2. Base cases for first four values.
  3. Recursively compute with caching.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

#include <vector>
long long tetraMemoDfs(int n, std::vector<long long>& memo){
  if(n==0) return 0; if(n==1||n==2) return 1; if(n==3) return 2;
  if(memo[n]!=-1) return memo[n];
  memo[n]= tetraMemoDfs(n-1,memo)+tetraMemoDfs(n-2,memo)+tetraMemoDfs(n-3,memo)+tetraMemoDfs(n-4,memo);
  return memo[n];
}
long long tetranacciMemo(int n){
  std::vector<long long> memo(n+1, -1);
  return tetraMemoDfs(n,memo);
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func tetranacciMemo(n int) int64 {
  memo := make([]int64, n+1)
  for i := range memo { memo[i] = -1 }
  var dfs func(int) int64
  dfs = func(k int) int64 {
    if k == 0 { return 0 }
    if k == 1 || k == 2 { return 1 }
    if k == 3 { return 2 }
    if memo[k] != -1 { return memo[k] }
    memo[k] = dfs(k-1)+dfs(k-2)+dfs(k-3)+dfs(k-4)
    return memo[k]
  }
  return dfs(n)
}
1
2
3
4
5
6
7
8
9

class TetraMemo {
  long[] memo;
  long dfs(int n){
    if(n==0) return 0; if(n==1||n==2) return 1; if(n==3) return 2;
    if(memo[n]!=-1) return memo[n];
    memo[n]=dfs(n-1)+dfs(n-2)+dfs(n-3)+dfs(n-4); return memo[n];
  }
  long tetranacci(int n){ memo=new long[n+1]; java.util.Arrays.fill(memo,-1); return dfs(n);} 
}
1
2
3
4
5
6
7
8
9

from functools import lru_cache

@lru_cache(None)
def tetranacci_memo(n: int) -> int:
  if n == 0: return 0
  if n in (1,2): return 1
  if n == 3: return 2
  return (tetranacci_memo(n-1) + tetranacci_memo(n-2) +
      tetranacci_memo(n-3) + tetranacci_memo(n-4))

Complexity

  • ⏰ Time complexity: O(n) – each n computed once, constant combination cost.
  • 🧺 Space complexity: O(n) – memo + recursion stack.

Method 3 - Bottom-Up DP (Array)

Intuition

Iteratively build results from base up to n storing all previous terms needed.

Approach

dp[i] = dp[i-1]+dp[i-2]+dp[i-3]+dp[i-4] for i ≥ 4.

Code

1
2
3
4
5
6
7

long long tetranacciBU(int n){
  if(n==0) return 0; if(n==1||n==2) return 1; if(n==3) return 2;
  std::vector<long long> dp(n+1);
  dp[0]=0; dp[1]=dp[2]=1; dp[3]=2;
  for(int i=4;i<=n;++i) dp[i]=dp[i-1]+dp[i-2]+dp[i-3]+dp[i-4];
  return dp[n];
}
1
2
3
4
5
6
7
8
9

func tetranacciBU(n int) int64 {
  if n == 0 { return 0 }
  if n == 1 || n == 2 { return 1 }
  if n == 3 { return 2 }
  dp := make([]int64, n+1)
  dp[0]=0; dp[1],dp[2],dp[3]=1,1,2
  for i:=4; i<=n; i++ { dp[i]=dp[i-1]+dp[i-2]+dp[i-3]+dp[i-4] }
  return dp[n]
}
1
2
3
4
5
6
7
8
9

class TetraBU {
  long tetranacci(int n){
    if(n==0) return 0; if(n==1||n==2) return 1; if(n==3) return 2;
    long[] dp=new long[n+1];
    dp[0]=0; dp[1]=dp[2]=1; dp[3]=2;
    for(int i=4;i<=n;i++) dp[i]=dp[i-1]+dp[i-2]+dp[i-3]+dp[i-4];
    return dp[n];
  }
}
1
2
3
4
5
6
7
8
9

def tetranacci_bu(n: int) -> int:
  if n == 0: return 0
  if n in (1,2): return 1
  if n == 3: return 2
  dp = [0]*(n+1)
  dp[1]=dp[2]=1; dp[3]=2
  for i in range(4, n+1):
    dp[i] = dp[i-1]+dp[i-2]+dp[i-3]+dp[i-4]
  return dp[n]

Complexity

  • ⏰ Time complexity: O(n) – one loop.
  • 🧺 Space complexity: O(n) – dp array.

Method 4 - Bottom-Up Space Optimized (4 Variables)

Intuition

Only last 4 values are needed; rotate through four variables.

Approach

Maintain (a,b,c,d) representing (T(n-4), T(n-3), T(n-2), T(n-1)) and compute next.

Code

1
2
3
4
5
6

long long tetranacciSpace(int n){
  if(n==0) return 0; if(n==1||n==2) return 1; if(n==3) return 2;
  long long a=0,b=1,c=1,d=2,cur; // corresponds to T0..T3
  for(int i=4;i<=n;++i){ cur=a+b+c+d; a=b; b=c; c=d; d=cur; }
  return d;
}
1
2
3
4
5
6
7
8
9

func tetranacciSpace(n int) int64 {
  if n == 0 { return 0 }
  if n == 1 || n == 2 { return 1 }
  if n == 3 { return 2 }
  a,b,c,d := int64(0),int64(1),int64(1),int64(2)
  var cur int64
  for i:=4; i<=n; i++ { cur=a+b+c+d; a,b,c,d=b,c,d,cur }
  return d
}
1
2
3
4
5
6
7
8

class TetraSpace {
  long tetranacci(int n){
    if(n==0) return 0; if(n==1||n==2) return 1; if(n==3) return 2;
    long a=0,b=1,c=1,d=2,cur=0;
    for(int i=4;i<=n;i++){ cur=a+b+c+d; a=b; b=c; c=d; d=cur; }
    return d;
  }
}
1
2
3
4
5
6
7
8
9

def tetranacci_space(n: int) -> int:
  if n == 0: return 0
  if n in (1,2): return 1
  if n == 3: return 2
  a,b,c,d = 0,1,1,2
  for _ in range(4, n+1):
    cur = a+b+c+d
    a,b,c,d = b,c,d,cur
  return d

Complexity

  • ⏰ Time complexity: O(n) – single pass.
  • 🧺 Space complexity: O(1) – constant variables.

Method 5 - Matrix Exponentiation (Logarithmic)

Intuition

Any fixed-order linear recurrence can be represented via matrix multiplication. For order 4:

Let state vector V(n) = [T(n), T(n-1), T(n-2), T(n-3)]^T. Then V(n) = M * V(n-1) where

M = | 1 1 1 1 | | 1 0 0 0 | | 0 1 0 0 | | 0 0 1 0 |

Thus V(n) = M^{n-3} * V(3) with V(3) = [2,1,1,0]^T for n ≥ 3.

Fast exponentiation computes M^{k} in O(log n) matrix multiplications (each 4x4 constant cost).

Approach

  1. Handle base n < 4 directly.
  2. Binary exponentiation of 4x4 matrix.
  3. Multiply result by base vector to get T(n).

Code (C++, Java, Python shown)

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include <array>
using Mat4 = std::array<std::array<long long,4>,4>;

Mat4 mul(const Mat4& A, const Mat4& B){
  Mat4 C{}; for(int i=0;i<4;++i) for(int j=0;j<4;++j){ long long s=0; for(int k=0;k<4;++k) s+=A[i][k]*B[k][j]; C[i][j]=s; }
  return C;
}
Mat4 mpow(Mat4 base, long long exp){
  Mat4 R{}; for(int i=0;i<4;++i) R[i][i]=1;
  while(exp){ if(exp&1) R=mul(R,base); base=mul(base,base); exp>>=1; }
  return R;
}
long long tetranacciMatrix(long long n){
  if(n==0) return 0; if(n==1||n==2) return 1; if(n==3) return 2;
  Mat4 M = {{{1,1,1,1},{1,0,0,0},{0,1,0,0},{0,0,1,0}}};
  Mat4 P = mpow(M, n-3);
  // V(3) = [2,1,1,0]^T; T(n) = first row dot V(3)
  return P[0][0]*2 + P[0][1]*1 + P[0][2]*1 + P[0][3]*0;
}
Java
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class TetraMatrix {
  long[][] mul(long[][] A,long[][] B){
    long[][] C=new long[4][4];
    for(int i=0;i<4;i++) for(int j=0;j<4;j++){
      long s=0; for(int k=0;k<4;k++) s+=A[i][k]*B[k][j]; C[i][j]=s; }
    return C;
  }
  long[][] mpow(long[][] base,long exp){
    long[][] R=new long[4][4]; for(int i=0;i<4;i++) R[i][i]=1;
    while(exp>0){ if((exp&1)==1) R=mul(R,base); base=mul(base,base); exp >>=1; }
    return R;
  }
  long tetranacci(long n){
    if(n==0) return 0; if(n==1||n==2) return 1; if(n==3) return 2;
    long[][] M={{1,1,1,1},{1,0,0,0},{0,1,0,0},{0,0,1,0}};
    long[][] P= mpow(M, n-3);
    return P[0][0]*2 + P[0][1]*1 + P[0][2]*1 + P[0][3]*0;
  }
}
Python
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

from typing import List

def _mat_mul(A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
  return [[sum(A[i][k]*B[k][j] for k in range(4)) for j in range(4)] for i in range(4)]

def _mat_pow(M: List[List[int]], e: int) -> List[List[int]]:
  R = [[int(i==j) for j in range(4)] for i in range(4)]
  while e:
    if e & 1:
      R = _mat_mul(R, M)
    M = _mat_mul(M, M)
    e >>= 1
  return R

def tetranacci_matrix(n: int) -> int:
  if n == 0: return 0
  if n in (1,2): return 1
  if n == 3: return 2
  M = [[1,1,1,1],[1,0,0,0],[0,1,0,0],[0,0,1,0]]
  P = _mat_pow(M, n-3)
  return P[0][0]*2 + P[0][1]*1 + P[0][2]*1

Complexity

  • ⏰ Time complexity: O(log n) – binary exponentiation of constant-size matrix.
  • 🧺 Space complexity: O(1) – (ignoring recursion; iterative). Matrix storage constant.

Method Comparison

Method Time Space Notes
1 Naive Recursion O(4^n) O(n) Pedagogical only
2 Memoization O(n) O(n) Simple; top-down
3 Bottom-Up Array O(n) O(n) Straightforward tabulation
4 Space Optimized O(n) O(1) Preferred for large n (unless log method)
5 Matrix Exponentiation O(log n) O(1) Fast for large n; linear recurrence trick

Notes

  • For very large n, numbers grow exponentially; consider using big integers or applying a modulus (e.g., 1e9+7) — adjust operations accordingly.
  • The matrix exponentiation method generalizes to any k-step Fibonacci by using a k×k companion matrix.
  • If only sequential queries with increasing n arrive, maintain a rolling window (Method 4) and append new values in amortized O(1).