Sum triangle of array using recursion
The "Sum triangle of array" problem involves generating a special kind of triangle where each row contains the elements of the given array, and each element in a row is the sum of the adjacent elements from the row above it. This process is repeated until a single row is left with the sum of all elements of the original array.
Problem Statement and Example
Given an array of integers, let's say arr[] = {1, 4, 3, 1, 6, 5}. We need to create a sum triangle
as follows:
96
45 51
23 22 29
12 11 11 18
5 7 4 7 11
1 4 3 1 6 5 In the first row, we have the elements of the given array. In each subsequent row, each element is the sum of the two elements directly above it. The process continues until we have a single row containing the sum of all elements of the original array.
Approach
To achieve this using recursion, we'll create a function sumTriangle(arr, n) that takes the array
arr[] and its size n as inputs. The function will follow these steps:
-
Base Case: If the size
nbecomes less than 1, it means we have reached the last row of the sum triangle, and we stop the recursion. -
Recursive Case: Otherwise, we perform the following steps: a. Create an auxiliary array
auxiliary[]of sizen-1. b. Traverse the original arrayarr[]up to the second last element. c. Calculate the sum of each pair of consecutive elements and store them in theauxiliary[]array. d. Call thesumTriangle(auxiliary, n - 1)recursively with theauxiliary[]and the reduced sizen-1. -
After the recursion, we print the original array
arr[]to display each row of the sum triangle.
Pseudocode
function sumTriangle(arr[], n):
if n < 1:
return
else:
Create an auxiliary array auxiliary[n - 1]
for i from 0 to n-2:
sum = arr[i] + arr[i + 1]
auxiliary[i] = sum
sumTriangle(auxiliary, n - 1)
for i from 0 to n-1:
print arr[i]
print new line
// Call the function with the given array and its size
sumTriangle(arr, n)
Algorithm Explanation
The given pseudocode outlines the recursive approach to create the sum triangle of the array. It checks for the
base case where the size n is less than 1, indicating that there's only one row left in the sum
triangle, which means the recursion should stop. If the base case is not met, the algorithm proceeds with the
recursive case.
In the recursive case, it creates the auxiliary array of size n-1 and fills it with the sums of
consecutive elements from the arr[]. Then, it calls the sumTriangle function
recursively with the auxiliary[] and a reduced size of n-1. This continues until the
base case is met, and the recursion starts to unwind.
Finally, after the recursion is completed, the algorithm prints the elements of the original array
arr[]. Each row of the sum triangle is printed one after the other.
Code Solution
Here given code implementation process.
// C program for
// Sum triangle of array using recursion
#include <stdio.h>
// Print the sum triangle by recursion
void sumTriangle(int arr[], int n)
{
if (n < 1)
{
// Stop recursion
return;
}
else
{
// Define auxiliary array
int auxiliary[n - 1];
int sum = 0;
// Execute the loop through by n
for (int i = 0; i < n - 1; i++)
{
// Calculate sum the elements of two consecutive elements
sum = arr[i] + arr[i + 1];
// Put sum
auxiliary[i] = sum;
}
// Reduce size and pass new auxiliary array to
sumTriangle(auxiliary, n - 1);
// Display calculated result
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
}
int main(int argc, char
const *argv[])
{
// Given array elements
int arr[] = {
1 , 4 , 3 , 1 , 6 , 5
};
/*
---------------------------------
96
45 51
23 22 29
12 11 11 18
5 7 4 7 11
1 4 3 1 6 5
---------------------------------
*/
// Get the size
int n = sizeof(arr) / sizeof(arr[0]);
// Test
sumTriangle(arr, n);
return 0;
}input
96
45 51
23 22 29
12 11 11 18
5 7 4 7 11
1 4 3 1 6 5/*
Java Program for
Sum triangle of array using recursion
*/
public class Triangle
{
// Print the sum triangle by recursion
public void sumTriangle(int[] arr, int n)
{
if (n < 1)
{
// Stop recursion
return;
}
else
{
// Define auxiliary array
int[] auxiliary = new int[n - 1];
int sum = 0;
// Execute the loop through by n
for (int i = 0; i < n - 1; i++)
{
// Calculate sum the elements of two consecutive elements
sum = arr[i] + arr[i + 1];
// Put sum
auxiliary[i] = sum;
}
// Reduce size and pass new auxiliary array to
sumTriangle(auxiliary, n - 1);
// Display calculated result
for (int i = 0; i < n; i++)
{
System.out.print(" " + arr[i]);
}
System.out.print("\n");
}
}
public static void main(String[] args)
{
Triangle task = new Triangle();
// Given array elements
int[] arr = {
1 , 4 , 3 , 1 , 6 , 5
};
/*
---------------------------------
96
45 51
23 22 29
12 11 11 18
5 7 4 7 11
1 4 3 1 6 5
---------------------------------
*/
// Get the size
int n = arr.length;
// Test
task.sumTriangle(arr, n);
}
}input
96
45 51
23 22 29
12 11 11 18
5 7 4 7 11
1 4 3 1 6 5// Include header file
#include <iostream>
using namespace std;
/*
C++ Program for
Sum triangle of array using recursion
*/
class Triangle
{
public:
// Print the sum triangle by recursion
void sumTriangle(int arr[], int n)
{
if (n < 1)
{
// Stop recursion
return;
}
else
{
// Define auxiliary array
int auxiliary[n - 1];
int sum = 0;
// Execute the loop through by n
for (int i = 0; i < n - 1; i++)
{
// Calculate sum the elements of two consecutive elements
sum = arr[i] + arr[i + 1];
// Put sum
auxiliary[i] = sum;
}
// Reduce size and pass new auxiliary array to
this->sumTriangle(auxiliary, n - 1);
// Display calculated result
for (int i = 0; i < n; i++)
{
cout << " " << arr[i];
}
cout << "\n";
}
}
};
int main()
{
Triangle *task = new Triangle();
// Given array elements
int arr[] = {
1 , 4 , 3 , 1 , 6 , 5
};
/*
---------------------------------
96
45 51
23 22 29
12 11 11 18
5 7 4 7 11
1 4 3 1 6 5
---------------------------------
*/
// Get the size
int n = sizeof(arr) / sizeof(arr[0]);
// Test
task->sumTriangle(arr, n);
return 0;
}input
96
45 51
23 22 29
12 11 11 18
5 7 4 7 11
1 4 3 1 6 5// Include namespace system
using System;
/*
Csharp Program for
Sum triangle of array using recursion
*/
public class Triangle
{
// Print the sum triangle by recursion
public void sumTriangle(int[] arr, int n)
{
if (n < 1)
{
// Stop recursion
return;
}
else
{
// Define auxiliary array
int[] auxiliary = new int[n - 1];
int sum = 0;
// Execute the loop through by n
for (int i = 0; i < n - 1; i++)
{
// Calculate sum the elements of two consecutive elements
sum = arr[i] + arr[i + 1];
// Put sum
auxiliary[i] = sum;
}
// Reduce size and pass new auxiliary array to
this.sumTriangle(auxiliary, n - 1);
// Display calculated result
for (int i = 0; i < n; i++)
{
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
}
public static void Main(String[] args)
{
Triangle task = new Triangle();
// Given array elements
int[] arr = {
1 , 4 , 3 , 1 , 6 , 5
};
/*
---------------------------------
96
45 51
23 22 29
12 11 11 18
5 7 4 7 11
1 4 3 1 6 5
---------------------------------
*/
// Get the size
int n = arr.Length;
// Test
task.sumTriangle(arr, n);
}
}input
96
45 51
23 22 29
12 11 11 18
5 7 4 7 11
1 4 3 1 6 5<?php
/*
Php Program for
Sum triangle of array using recursion
*/
class Triangle
{
// Print the sum triangle by recursion
public function sumTriangle($arr, $n)
{
if ($n < 1)
{
// Stop recursion
return;
}
else
{
// Define auxiliary array
$auxiliary = array_fill(0, $n - 1, 0);
$sum = 0;
// Execute the loop through by n
for ($i = 0; $i < $n - 1; $i++)
{
// Calculate sum the elements of two consecutive elements
$sum = $arr[$i] + $arr[$i + 1];
// Put sum
$auxiliary[$i] = $sum;
}
// Reduce size and pass new auxiliary array to
$this->sumTriangle($auxiliary, $n - 1);
// Display calculated result
for ($i = 0; $i < $n; $i++)
{
echo " ".$arr[$i];
}
echo "\n";
}
}
}
function main()
{
$task = new Triangle();
// Given array elements
$arr = array(1, 4, 3, 1, 6, 5);
/*
---------------------------------
96
45 51
23 22 29
12 11 11 18
5 7 4 7 11
1 4 3 1 6 5
---------------------------------
*/
// Get the size
$n = count($arr);
// Test
$task->sumTriangle($arr, $n);
}
main();input
96
45 51
23 22 29
12 11 11 18
5 7 4 7 11
1 4 3 1 6 5/*
Node JS Program for
Sum triangle of array using recursion
*/
class Triangle
{
// Print the sum triangle by recursion
sumTriangle(arr, n)
{
if (n < 1)
{
// Stop recursion
return;
}
else
{
// Define auxiliary array
var auxiliary = Array(n - 1).fill(0);
var sum = 0;
// Execute the loop through by n
for (var i = 0; i < n - 1; i++)
{
// Calculate sum the elements of two consecutive elements
sum = arr[i] + arr[i + 1];
// Put sum
auxiliary[i] = sum;
}
// Reduce size and pass new auxiliary array to
this.sumTriangle(auxiliary, n - 1);
// Display calculated result
for (var i = 0; i < n; i++)
{
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
}
}
function main()
{
var task = new Triangle();
// Given array elements
var arr = [1, 4, 3, 1, 6, 5];
/*
---------------------------------
96
45 51
23 22 29
12 11 11 18
5 7 4 7 11
1 4 3 1 6 5
---------------------------------
*/
// Get the size
var n = arr.length;
// Test
task.sumTriangle(arr, n);
}
main();input
96
45 51
23 22 29
12 11 11 18
5 7 4 7 11
1 4 3 1 6 5# Python 3 Program for
# Sum triangle of array using recursion
class Triangle :
# Print the sum triangle by recursion
def sumTriangle(self, arr, n) :
if (n < 1) :
# Stop recursion
return
else :
auxiliary = [0] * (n - 1)
sum = 0
i = 0
# Execute the loop through by n
while (i < n - 1) :
# Calculate sum the elements of two consecutive elements
sum = arr[i] + arr[i + 1]
# Put sum
auxiliary[i] = sum
i += 1
# Reduce size and pass new auxiliary list to
self.sumTriangle(auxiliary, n - 1)
i = 0
# Display calculated result
while (i < n) :
print(" ", arr[i], end = "")
i += 1
print(end = "\n")
def main() :
task = Triangle()
arr = [1, 4, 3, 1, 6, 5]
n = len(arr)
# Test
task.sumTriangle(arr, n)
if __name__ == "__main__": main()input
96
45 51
23 22 29
12 11 11 18
5 7 4 7 11
1 4 3 1 6 5# Ruby Program for
# Sum triangle of array using recursion
class Triangle
# Print the sum triangle by recursion
def sumTriangle(arr, n)
if (n < 1)
# Stop recursion
return
else
# Define auxiliary array
auxiliary = Array.new(n - 1) {0}
sum = 0
i = 0
# Execute the loop through by n
while (i < n - 1)
# Calculate sum the elements of two consecutive elements
sum = arr[i] + arr[i + 1]
# Put sum
auxiliary[i] = sum
i += 1
end
# Reduce size and pass new auxiliary array to
self.sumTriangle(auxiliary, n - 1)
i = 0
# Display calculated result
while (i < n)
print(" ", arr[i])
i += 1
end
print("\n")
end
end
end
def main()
task = Triangle.new()
# Given array elements
arr = [1, 4, 3, 1, 6, 5]
# ---------------------------------
# 96
# 45 51
# 23 22 29
# 12 11 11 18
# 5 7 4 7 11
# 1 4 3 1 6 5
# ---------------------------------
# Get the size
n = arr.length
# Test
task.sumTriangle(arr, n)
end
main()input
96
45 51
23 22 29
12 11 11 18
5 7 4 7 11
1 4 3 1 6 5
/*
Swift 4 Program for
Sum triangle of array using recursion
*/
class Triangle
{
// Print the sum triangle by recursion
func sumTriangle(_ arr: inout[Int], _ n: Int)
{
if (n < 1)
{
// Stop recursion
return;
}
else
{
// Define auxiliary array
var auxiliary: [Int] = Array(repeating: 0, count: n - 1);
var sum: Int = 0;
var i: Int = 0;
// Execute the loop through by n
while (i < n - 1)
{
// Calculate sum the elements of two consecutive elements
sum = arr[i] + arr[i + 1];
// Put sum
auxiliary[i] = sum;
i += 1;
}
// Reduce size and pass new auxiliary array to
self.sumTriangle(&auxiliary, n - 1);
i = 0;
// Display calculated result
while (i < n)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
}
}
func main()
{
let task: Triangle = Triangle();
// Given array elements
var arr: [Int] = [1, 4, 3, 1, 6, 5];
/*
---------------------------------
96
45 51
23 22 29
12 11 11 18
5 7 4 7 11
1 4 3 1 6 5
---------------------------------
*/
// Get the size
let n: Int = arr.count;
// Test
task.sumTriangle(&arr, n);
}
main();input
96
45 51
23 22 29
12 11 11 18
5 7 4 7 11
1 4 3 1 6 5/*
Scala Program for
Sum triangle of array using recursion
*/
class Triangle()
{
// Print the sum triangle by recursion
def sumTriangle(arr: Array[Int], n: Int): Unit = {
if (n < 1)
{
// Stop recursion
return;
}
else
{
// Define auxiliary array
var auxiliary: Array[Int] = Array.fill[Int](n - 1)(0);
var sum: Int = 0;
var i: Int = 0;
// Execute the loop through by n
while (i < n - 1)
{
// Calculate sum the elements of two consecutive elements
sum = arr(i) + arr(i + 1);
// Put sum
auxiliary(i) = sum;
i += 1;
}
// Reduce size and pass new auxiliary array to
sumTriangle(auxiliary, n - 1);
i = 0;
// Display calculated result
while (i < n)
{
print(" " + arr(i));
i += 1;
}
print("\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Triangle = new Triangle();
// Given array elements
var arr: Array[Int] = Array(1, 4, 3, 1, 6, 5);
/*
---------------------------------
96
45 51
23 22 29
12 11 11 18
5 7 4 7 11
1 4 3 1 6 5
---------------------------------
*/
// Get the size
var n: Int = arr.length;
// Test
task.sumTriangle(arr, n);
}
}input
96
45 51
23 22 29
12 11 11 18
5 7 4 7 11
1 4 3 1 6 5Time Complexity
The time complexity of this recursive approach is a bit tricky to analyze due to the nested nature of the
recursion. For each level of recursion, we perform a loop over n-1 elements to calculate the sums
in the auxiliary array. Since the recursion has n levels, and the number of elements to process
reduces by one in each level, the total time complexity can be approximated as O(n^2), where n is
the size of the input array.
Resultant Output Explanation
The given code uses the recursive function sumTriangle to create the sum triangle for the input
array arr[] = {1, 4, 3, 1, 6, 5}. The output is displayed row by row, representing each row of the
sum triangle.
96 45 51 23 22 29 12 11 11 18 5 7 4 7 11 1 4 3 1 6 5
Each row contains the elements of the original array, and each element in a row (except the last row) is the sum of the two elements directly above it. The last row contains the sum of all elements of the original array.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment