How Recursion Works with Examples
Using a Loops
We could simply right this function like:
public static int summationThroughLoops(int k){
int sum = 0;
for(int i = 0; i < k; i++){
sum += (i + 1);
}
return sum;
}
This function will take k (the max iteration) and will iterate through as a summation.
So if k is 5, the function will do 1 + 2 + 3 + 4 + 5 = 15
Using Recursion
Now lets solve the exact same problem with Recursion:
public static int sum(int k) {
if (k > 0) {
return k + sum(k - 1);
} else {
return 0;
}
}
In this function, instead of a loop, the function calls itself while k declines in that call. the intial call to the function will return k + sum(k – 1). In order for this function to actually return, it will need to run the call sum(k – 1). So what happens next?
Say k = 5 again. so the initial call would:
return 5 + sum(5 – 1)
it calls itself and sum(5 – 1) returns 4 + sum(4 – 1)
sum(4 – 1) returns 3 + sum(3 – 1)
sum(3 – 1) returns 2 + sum(2 – 1)
sum(2 – 1) returns 1 + sum(1 – 1)
sum(1 – 1) returns 0
If you then return all the way back:
sum(1 – 1) returns 0
sum(2 – 1) returns 1 + 0 = 1
sum(3 – 1) returns 2 + 1 = 3
sum(4 – 1) returns 3 + 3 = 6
sum(5 – 1) returns 4 + 6 = 10
sum(5) returns 5 + 10 = 15