What is recursion in Programming

A function invoking itself is known as recursion. Recursion is an alternative to iteration. Recursion is very close to mathematical way of solving a given problem.

Advantages of recursion are, it is straight forward and easy. Disadvantage of recursion is, it occupies more memory on the stack when compared to iteration.

Note: Remember to write an exit condition while using recursion. If there is no exit condition, then the function will call itself infinitely.

Consider the following program which calculates the factorial of a number using recursion:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

#include using namespace std; int fact(int n) { if(n==0 || n==1) return 1; else return n*fact(n–1); } int main() { int num; cout<<“Enter a number: “; cin>>num; cout<<“Factorial of “<<num<<” is: “<<fact(num)<<endl; return 0; } Input and output for the above program is as follows: Enter a number: 5 Factorial of 5 is: 120

In the above program the exit condition is if(n==0 || n==1) return 1;

The recursive call is fact(n-1).

Note: In the above program there is no function declaration (prototype) for the function fact(). If the function definition is written before main(), there is no need of writing function declaration.

Passing an Array as a Parameter

Like we are able to pass variables, we can also pass arrays as arguments to a function. A function prototype which accepts an array and its size as parameters is as follows:

void PrintArray(int nums[ ], int size);

Consider the following program which contains a function that takes an array and its size as arguments and calculates the largest element in the array.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

#include using namespace std; int largest(int nums[], int size) { int max = nums[0]; for(int i=1; i<size; i++) { if(max<nums[i]) { max = nums[i]; } } return max; } int main() { int nums[5] = {1,2,5,3,4}; cout<<“Largest element in the array is: “<<largest(nums, 5)<<endl; return 0; } Output of the above program is as follows: Largest element in the array is: 5

Note that in the above program there is no need to write square brackets in the function call largest(nums, 5).

Parameter Passing Techniques

In C++ we have three ways for passing arguments to a function. They are: pass-by-value, pass-by-reference, and pass-by-address.

Pass-by-value

Generally used way to pass arguments is pass-by-value. In this method, the arguments passed in the function call are copied to formal parameters in the function definition. So, any changes made to the formal parameters are not reflected on the actual parameters. Consider the following swap function which demonstrates pass-by-value:

1 2 3 4 5 6

void swap(int x, int y) { int temp = x; x = y; y = temp; }

Let’s assume that in the main() function we are writing the following code:

int a = 10, b = 20;

swap(a, b);

Although the values of x and y are being interchanged, since they are copies of a and b, the values of a and b remains the same i.e., 10 and 20 respectively.