The tetranacci numbers are a generalization of the Fibonacci numbers defined by the recurrence relation
T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4)
with T(0)=0, T(1)=1, T(2)=1, T(3)=2,
For n>=4. They represent the n=4 case of the Fibonacci n-step numbers. The first few terms for n=0, 1, … are 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, …
Given a number N. The task is to find the N-th tetranacci number.
Examples:
Input: 5 Output: 4 Input: 9 Output: 108
Recommended: Please try your approach on {IDE} first, before moving on to the solution.
A naive approach is to follow the recurrence for finding the number and use recursion to solve it.
Below is the implementation of the above approach.
C++
// A simple recursive CPP program to print// the nth tetranacci numbers.#include <iostream>using namespace std;// Function to return the// N-th tetranacci numberint printTetraRec(int n){ // base cases if (n == 0) return 0; // base cases if (n == 1 || n == 2) return 1; // base cases if (n == 3) return 2; else return printTetraRec(n - 1) + printTetraRec(n - 2) + printTetraRec(n - 3) + printTetraRec(n - 4);}// function to print the nth tetranacci numbervoid printTetra(int n){ cout << printTetraRec(n) << " ";}// Driver codeint main(){ int n = 10; printTetra(n); return 0;} |
Java
// A simple recursive Java // program to print the nth// tetranacci numbers.class GFG{// Function to return the// N-th tetranacci numberstatic int printTetraRec(int n){ // base cases if (n == 0) return 0; // base cases if (n == 1 || n == 2) return 1; // base cases if (n == 3) return 2; else return printTetraRec(n - 1) + printTetraRec(n - 2) + printTetraRec(n - 3) + printTetraRec(n - 4);}// function to print the // Nth tetranacci numberstatic void printTetra(int n){ System.out.println(printTetraRec(n) + " ");}// Driver codepublic static void main(String[] args){ int n = 10; printTetra(n);}}// This code is contributed by mits |
Python3
# A simple recursive Python3 program # to print the nth tetranacci numbers.# Function to return the# N-th tetranacci numberdef printTetraRec(n): # base cases if (n == 0): return 0; # base cases if (n == 1 or n == 2): return 1; # base cases if (n == 3): return 2; else: return (printTetraRec(n - 1) + printTetraRec(n - 2) + printTetraRec(n - 3) + printTetraRec(n - 4));# function to print the # nth tetranacci numberdef printTetra(n): print(printTetraRec(n), end = " ");# Driver coden = 10;printTetra(n);# This code is contributed # by mits |
C#
// A simple recursive C# // program to print the nth// tetranacci numbers.class GFG{ // Function to return the// N-th tetranacci numberstatic int printTetraRec(int n){ // base cases if (n == 0) return 0; // base cases if (n == 1 || n == 2) return 1; // base cases if (n == 3) return 2; else return printTetraRec(n - 1) + printTetraRec(n - 2) + printTetraRec(n - 3) + printTetraRec(n - 4);}// function to print the // Nth tetranacci numberstatic void printTetra(int n){ System.Console.WriteLine( printTetraRec(n) + " ");}// Driver codestatic void Main(){ int n = 10; printTetra(n);}}// This code is contributed by mits |
PHP
<?php// A simple recursive PHP program // to print the nth tetranacci numbers.// Function to return the// N-th tetranacci numberfunction printTetraRec($n){ // base cases if ($n == 0) return 0; // base cases if ($n == 1 || $n == 2) return 1; // base cases if ($n == 3) return 2; else return printTetraRec($n - 1) + printTetraRec($n - 2) + printTetraRec($n - 3) + printTetraRec($n - 4);}// function to print the // nth tetranacci numberfunction printTetra($n){ echo printTetraRec($n) . " ";}// Driver code$n = 10;printTetra($n);// This code is contributed // by Abby_akku?> |
Javascript
<script> // A simple recursive Javascript // program to print the nth // tetranacci numbers. // Function to return the // N-th tetranacci number function printTetraRec(n) { // base cases if (n == 0) return 0; // base cases if (n == 1 || n == 2) return 1; // base cases if (n == 3) return 2; else return printTetraRec(n - 1) + printTetraRec(n - 2) + printTetraRec(n - 3) + printTetraRec(n - 4); } // function to print the // Nth tetranacci number function printTetra(n) { document.write(printTetraRec(n) + " " + "</br>"); } let n = 10; printTetra(n); </script> |
Output:
208
Time Complexity: O(4N)
Auxiliary Space: O(4N), The extra space is used due to the recursion call stack.
A better solution is to use Dynamic Programming (memoization) as there are multiple overlaps.
Given below is the recursive tree for N=10.
rec(10)
/ / \ \
rec(9) rec(8) rec(7) rec(6)
/ / \ \
rec(8) rec(7) rec(6) rec(5)
In the above partial recursion tree, rec(8), rec(7), rec(6) have been solved twice. In drawing the complete recursion tree, it has been observed that there are many subproblems that are solved again and again. So this problem has overlapping Substructure property and recomputation of same subproblems can be avoided by either using Memoization or Tabulation.
Below is the implementation of the above approach.
C++
// A DP based CPP// program to print// the nth tetranacci number#include <iostream>using namespace std;// Function to print the// N-th tetranacci numberint printTetra(int n){ int dp[n + 5]; // base cases 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]; cout << dp[n];}// Driver codeint main(){ int n = 10; printTetra(n); return 0;} |
Java
// A DP based Java// program to print// the nth tetranacci numberclass GFG{// Function to print the// N-th tetranacci numberstatic void printTetra(int n){ int[] dp=new int[n + 5]; // base cases 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]; System.out.print(dp[n]);}// Driver codepublic static void main(String[] args){ int n = 10; printTetra(n);}}// This code is contributed by mits |
Python3
# A DP based Python3 program to print# the nth tetranacci number# Function to print the# N-th tetranacci numberdef printTetra(n): dp = [0] * (n + 5); # base cases dp[0] = 0; dp[1] = 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]); print(dp[n]);# Driver coden = 10;printTetra(n);# This code is contributed by mits |
C#
// A DP based C#// program to print// the nth tetranacci numberclass GFG{// Function to print the// N-th tetranacci numberstatic void printTetra(int n){ int[] dp=new int[n + 5]; // base cases 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]; System.Console.WriteLine(dp[n]);}// Driver codestatic void Main(){ int n = 10; printTetra(n);}}// This code is contributed by mits |
PHP
<?php// A DP based PHP// program to print// the nth tetranacci number// Function to print the// N-th tetranacci numberfunction printTetra($n){ $dp = array_fill(0, $n + 5, 0); // base cases $dp[0] = 0; $dp[1] = $dp[2] = 1; $dp[3] = 2; for ($i = 4; $i <= $n; $i++) $dp[$i] = $dp[$i - 1] + $dp[$i - 2] + $dp[$i - 3] + $dp[$i - 4]; echo $dp[$n];}// Driver code$n = 10;printTetra($n);// This code is contributed by mits?> |
Javascript
<script> // A DP based Javascript // program to print // the nth tetranacci number // Function to print the // N-th tetranacci number function printTetra(n) { let dp=new Array(n + 5); // base cases dp[0] = 0; dp[1] = dp[2] = 1; dp[3] = 2; for (let i = 4; i <= n; i++) dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] + dp[i - 4]; document.write(dp[n]); } let n = 10; printTetra(n);</script> |
Output:
208
Time Complexity: O(N)
Auxiliary Space: O(N)
The time complexity above is linear, but it requires extra space. Space used can be optimized in the above solution by using four variables to keep track of the previous four numbers.
Below is the implementation of the above approach.
C++
// A space optimized// based CPP program to// print the nth tetranacci number#include <iostream>using namespace std;// Function to print the// N-th tetranacci numbervoid printTetra(int n){ if (n < 0) return; // Initialize first // four numbers to base cases int first = 0, second = 1; int third = 1, fourth = 2; // declare a current variable int curr; if (n == 0) cout << first; else if (n == 1 || n == 2) cout << second; else if (n == 3) cout << fourth; else { // Loop to add previous // four numbers for // each number starting // from 4 and then assign // first, second, third // to second, third, fourth and // curr to fourth respectively for (int i = 4; i <= n; i++) { curr = first + second + third + fourth; first = second; second = third; third = fourth; fourth = curr; } cout << curr; }}// Driver codeint main(){ int n = 10; printTetra(n); return 0;} |
Java
// A space optimized// based Java program to// print the nth tetranacci numberimport java.io.*;import java.util.*;import java.lang.*;class GFG{// Function to print the// N-th tetranacci numberstatic void printTetra(int n){ if (n < 0) return; // Initialize first // four numbers to base cases int first = 0, second = 1; int third = 1, fourth = 2; // declare a current variable int curr = 0; if (n == 0) System.out.print(first); else if (n == 1 || n == 2) System.out.print(second); else if (n == 3) System.out.print(fourth); else { // Loop to add previous // four numbers for // each number starting // from 4 and then assign // first, second, third // to second, third, fourth and // curr to fourth respectively for (int i = 4; i <= n; i++) { curr = first + second + third + fourth; first = second; second = third; third = fourth; fourth = curr; } System.out.print(curr); }}// Driver codepublic static void main(String[] args){ int n = 10; printTetra(n);}}// This code is contributed// by Akanksha Rai(Abby_akku) |
Python3
# A space optimized based Python3 program # to print the nth tetranacci number # Function to print the N-th # tetranacci number def printTetra(n): if (n < 0): return; # Initialize first four # numbers to base cases first = 0; second = 1; third = 1; fourth = 2; # declare a current variable curr = 0; if (n == 0): print(first); elif (n == 1 or n == 2): print(second); elif (n == 3): print(fourth); else: # Loop to add previous four numbers # for each number starting from 4 # and then assign first, second, # third to second, third, fourth # and curr to fourth respectively for i in range(4, n + 1): curr = first + second + third + fourth; first = second; second = third; third = fourth; fourth = curr; print(curr); # Driver code n = 10; printTetra(n); # This code is contributed by mits |
C#
// A space optimized based C# program to // print the nth tetranacci number using System;class GFG{ // Function to print the // N-th tetranacci number static void printTetra(int n) { if (n < 0) return; // Initialize first // four numbers to base cases int first = 0, second = 1; int third = 1, fourth = 2; // declare a current variable int curr = 0; if (n == 0) Console.Write(first); else if (n == 1 || n == 2) Console.Write(second); else if (n == 3) Console.Write(fourth); else { // Loop to add previous // four numbers for // each number starting // from 4 and then assign // first, second, third // to second, third, fourth and // curr to fourth respectively for (int i = 4; i <= n; i++) { curr = first + second + third + fourth; first = second; second = third; third = fourth; fourth = curr; } Console.Write(curr); } } // Driver code static public void Main () { int n = 10; printTetra(n); } } // This code is contributed ajit |
PHP
<?php// A space optimized based PHP program // to print the nth tetranacci number // Function to print the N-th // tetranacci number function printTetra($n) { if ($n < 0) return; // Initialize first four // numbers to base cases $first = 0; $second = 1; $third = 1; $fourth = 2; // declare a current variable $curr; if ($n == 0) echo $first; else if ($n == 1 || $n == 2) echo $second; else if ($n == 3) echo $fourth; else { // Loop to add previous four // numbers for each number // starting from 4 and then // assign first, second, third // to second, third, fourth and // curr to fourth respectively for ($i = 4; $i <= $n; $i++) { $curr = $first + $second + $third + $fourth; $first = $second; $second = $third; $third = $fourth; $fourth = $curr; } echo $curr; } } // Driver code $n = 10; printTetra($n); // This code is contributed by ajit?> |
Javascript
<script>// A space optimized// based Javascript program to// print the nth tetranacci number// Function to print the// N-th tetranacci numberfunction printTetra(n){ if (n < 0) return; // Initialize first // four numbers to base cases var first = 0, second = 1; var third = 1, fourth = 2; // declare a current variable var curr; if (n == 0) cout << first; else if (n == 1 || n == 2) cout << second; else if (n == 3) cout << fourth; else { // Loop to add previous // four numbers for // each number starting // from 4 and then assign // first, second, third // to second, third, fourth and // curr to fourth respectively for (var i = 4; i <= n; i++) { curr = first + second + third + fourth; first = second; second = third; third = fourth; fourth = curr; } document.write( curr); }}// Driver codevar n = 10;printTetra(n);</script> |
Output:
208
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
