Category Archives: Recursion

Print a string in reverse using recursion

In simple words, Recursion is nothing but a function calling itself. How can we solve this problem using recursion? 
Initially pass the entire string as input to the function. Basically a pointer to the first character is passed. This function examines the next character; if it is not null, it calls itself by advancing the pointer to the next character. This call sequence goes on until the next character is a null.
In the last call, it prints the last character and function call returns. When this call returns, it goes to the previous state. that means it prints the last but one character and so on…

Here the simple C++ code to do this.

#include <iostream>
#define MAXLEN 100
using namespace std;

void printRev(char *str)
{
//return if empty string
if( *str == NULL )
return;

//if the next char is not null, recurse
if( *(str+1) != NULL )
printRev(str+1);

//print char while unwinding the stack
cout<<*str;
}
int main()
{
char str[MAXLEN];
cin>>str;
printRev(str);
return 0;
}

Explaining recursion with a simple example

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;
}