java - Don't understand recursive backtracking

Question

I understand that this is a "vague" question, but I completed a data structures class at my college and still do not understand how recursive backtracking works. I don't understand the "magic" of recursion and struggle to write recursive backtracking algorithms. Like say I give an example here that is a a template for recursive backtracking:

void findSolutions(n, other params) {
    if (found a solution) {
       solutionsFound++;
       displaySolution();
    if (solutionsFound >= solutionTarget) {
       System.exit(0);
       return;
      }
   }
    for (val = first to last) {
       if (isValid(val, n)) {
           applyValue(val, n);
           findSolutions(n + 1, other params);
           removeValue(val, n);
        }
    }
} 

I don't understand how this actually works. And I'm kind of tired of having someone tell me that I just have to believe it does. I'd really like an in depth explanation of how recursion actually works and how to write it. I believe that recursion is an important concept to understand for technical interviews and such and I really want to be able to write code when I need to solve problems like these. Any tips would be greatly appreciated for explaining this as well as good resources to look at and study as well.

Answer 1

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.