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)
	{
		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  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.

New Comment