Recursion is a process by which a function calls itself repeatedly till it falls under the base condition and our motive is achieved.
To solve any problem using recursion, we should simply follow the below steps:
- Assume/Identify the smaller problem from the problem which is similar to the bigger/original problem.
- Decide the answer to the smallest valid input or smallest invalid input which would act as our base condition.
- Approach the solution and link the answer to the smaller problem given by the recursive function to find the answer to the bigger/original problem using it.
Here, we are illustrating the total Sum using recursion can be done using storing numbers in an array, and taking the summation of all the numbers using recursion.
Example
Input: N = 5, arr[] = {70, 60, 90, 40, 80}
Output: Total Sum = 340
Input: N = 8, arr[] = {8, 7, 6, 5, 4, 3, 2, 1}
Output: Total Sum = 36
Approach:
Now, we will apply the approach discussed above in this question to calculate the sum of all elements recursively.
- Smaller problem will be the array from index 1 to last index.
- Base condition will be when the index will reach the length of the array.ie out of the array that means that no element exist so the sum returned should be 0.
- Now, our task is to solve the bigger/ original problem using the result calculated by smaller problem. So, to do that as we know smaller problem is from index1 to last index , so if we get the sum of this problem then after that for the whole sum of array we just need to add the first element / ith element to that answer and return our final answer.
Below is the implementation of the above approach.
Example:
Java
// Java program to calculate the sum of// the elements of the array recursivelyimport java.io.*;class GFG { // recursive function public static int calculate_sum_using_recursion(int arr[], int i, int length) { // base condition - when reached end of the array // return 0 if (i == length) { return 0; } // recursive condition - current element + sum of // (n-1) elements return arr[i] + calculate_sum_using_recursion(arr, i + 1,length); } public static void main(String[] args) { int N = 5, total_sum = 0; // create 1-D array to store numbers int arr[] = { 89, 75, 82, 60, 95 }; // call function to calculate sum total_sum = calculate_sum_using_recursion(arr, 0, N); // print total sum System.out.println("The total of N numbers is : " + total_sum); }} |
The total of N numbers is : 401
Time complexity: O(N)
Auxiliary Space: O(N)
Approach 2:
We can apply recursion by not just one way but there can be one or more than one ways to solve a single problem using recursion.
In the above approach, we started recursion from forward direction and reached and hit the base condition at the end/last position.
In this approach, we will consider the length variable in the function as the changing parameter, where length variable will start from the last position and the base case will hit reaching to the front out of bound index which is -1.
Example:
Java
// Java program to calculate the sum of// the elements of array using recursionimport java.io.*;class GFG { // recursive function public static int calculate_sum_using_recursion(int arr[], int length) { // base condition - when reached -1 index // return 0 if (length == -1) { return 0; } // recursive condition - current element + sum of // (n-1) elements return arr[length] + calculate_sum_using_recursion(arr,length - 1); } public static void main(String[] args) { int N = 8, total_sum = 0; // create 1-D array to store numbers int arr[] = { 8, 7, 6, 5, 4, 3, 2, 1 }; // call function to calculate sum total_sum = calculate_sum_using_recursion(arr, N - 1); // print total sum System.out.println("The total of N numbers is : " + total_sum); }} |
The total of N numbers is : 36
Time complexity: O(N)
Auxiliary Space: O(N)
