Recursive Programming is similar to iterative programing (for loop..) since we are executing a specific code block several times until an exit condition is met. Recursion is an alternative solution to iterative and it calls itself repeatedly until the condition we set inside the code block is met.
Syntax
function(parameters) {
//exit condition
function(slightly different parameters)
}
Example:
Let us recursively calculate the sum of all numbers in a given array.
int Sum(int[] a, int i) {
if (i == a.Length)
return 0;
return a[i] + Sum(a, i + 1);
}
Testing:
int answer= Sum(new int[] { 1, 1, 2, 2, 3,1 }, 0); //output 10
Explanation:
- We have set up our recursive Sum function by passing the array of integers and 0 which is the start index of an array.
- Basically we can think of recursion as a way of chopping the whole task in to a smaller unit of work as follows.
- Sum(ai ) = a[0] + (a[1] + a[2] + a[3] … a[n]) In other words, Sum(ai) = a[0] + Sum(a[1]…a[n])
- But we can also use the same strategy to calculate Sum(a[1]…a[n]). Sum(a[1]…a[n]) = a[1] + Sum(a[2]…a[n])
- We can repeat the same process until we met an exit condition .
- Exit condition is to pass the current index we are on to the sum function and check if we reach the end of the array, in which case we return 0.