Simple examples of recursion.
Let's say you want a method sum(n)
that sums the numbers from 0
to n
.
Using a simple for
loop, that easy enough to understand:
private static int sum(int n) {
int sum = 0;
for (int i = 0; i <= n; i++)
sum += i;
return sum;
}
System.out.println(sum(5)); // prints: 15
Now, if you were to do this using recursion, there would be two ways.
One way would be to add a second parameter with the sum calculated so far, initially set to 0
, and then make a recursive call like this:
private static int sum(int n, int sum) {
if (n == 0)
return sum;
return sum(n - 1, sum + n);
}
System.out.println(sum(5, 0)); // prints: 15
This is known as tail-recursion, because the recursive call is the very last thing done in the method. It is a common pattern in functional programming.
The other way is using recursive backtracking, and is what you asked about.
Here you make a recursive call to calculate sum(n-1)
, until you get to sum(0)
, which of course is 0
. You then add n
to that sum and return it.
private static int sum(int n) {
if (n == 0)
return 0;
return sum(n - 1) + n;
}
System.out.println(sum(5)); // prints: 15
This is using backtracking, because it make the recursive call first, to calculate the "lower" value, then add to that value on the return from the lower call, i.e. when backtracking.