Posted on by Kalkicode
Code Recursion

# 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:

1. Base Case: If the size `n` becomes less than 1, it means we have reached the last row of the sum triangle, and we stop the recursion.

2. Recursive Case: Otherwise, we perform the following steps: a. Create an auxiliary array `auxiliary[]` of size `n-1`. b. Traverse the original array `arr[]` up to the second last element. c. Calculate the sum of each pair of consecutive elements and store them in the `auxiliary[]` array. d. Call the `sumTriangle(auxiliary, n - 1)` recursively with the `auxiliary[]` and the reduced size `n-1`.

3. 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)
{
// 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
}
}``````

#### 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()
{
// 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
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)
{
// 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
}
}``````

#### 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()
{
// 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
}
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()
{
// 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
}
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() :
arr = [1, 4, 3, 1, 6, 5]
n = len(arr)
#  Test

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()
#  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
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()
{
// 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
}
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
}
}``````

#### input

``````  96
45  51
23  22  29
12  11  11  18
5  7  4  7  11
1  4  3  1  6  5``````

## Time 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.

## Comment

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.

Categories
Relative Post