In this post we will see a simple example which explains the concept of recursion.
Recursion is nothing but defining a problem in terms of itself. For example let us consider the problem of finding the sum of all the elements in an array. We can define the problem as follows.
Let sum(array,n) denotes the sum of the elements of an array of size n.
We can define sum(array,n) = sum(array,n-1) + array[n]
sum(array,n-1) is sum of the elements of array of size n-1 which actually is the same problem but with a smaller input size – the smaller sub-problem. If we write a function to solve the original problem, we can use the same function to solve this sub-problem also. There should be one base-case where we no longer need recursion to solve the smallest problem possible. In this case, the smallest sub-problem would be an array with just one element. What is the sum of elements in such an array? That single element itself. Then we work backwards to solve increasingly bigger sub-problem.
The following program illustrates the above concept.
#include <iostream>
using namespace std;
//This is a recursive function to find the sum of
//the elements in an array
int findSumRecursive(int *array,int n)
{
//Base cases
//if the array is empty return 0
if( n <= 0)
return 0;
//If the array has only one element, return that
//It is first as well as last element
else if( n == 1)
return array[n-1];
//recursive case
else
return array[n-1] + findSumRecursive(array,n-1);
}
int main()
{
int n;
cin>>n; //read array size
int i;
//dynamically allocate memory for the array
int *array = new int[n];
//read array elements
for( i = 0 ; i < n ; i++)
{
cin>>array[i];
}
cout<<findSumRecursive(array,n)<<endl;
//free the memory if it is no loner needed
delete[] array;
return 0;
}