Recursion

In this section we will talk about recursion, and in the next one we will cover a closely related concept of backtracking, and see how it applies to solving interview problems.

Recursion

Recursion is a very well known concept in programming. In short, recursion is a method when a function call relies on the results of the same function on some other input.

Recursive functions almost always have the following components:

void f(/* State */) {
    /* Base or terminating case */

    /* Operations on state, and possible calls to f() function again */
}

When writing recursive functions, you should always think about what these components should look like. What are you trying to achieve? What is the state? What is the base case?

We can express pretty much anything using recursion. Let's write a recursive function to calculate the sum of the array:

int a[] = {5, 7, 10, -3, 18};

int f(int position /* State. Our state here is the current position in the array */) {
    /* Base or terminating case */
    /* If we are beyond the end of the array, we can stop and just return 0 */
    if (position == a.length)
        return 0;

    /* Operations on state, and possible calls to f() function again */
    /* Add current number and sum of the rest of the array */
    return a[position] + f(position + 1);
}

int arraySum = f(0); // f(0) returns 37 - the sum of our array

Note that this recursive code is equivalent to the following code:

int a[] = {5, 7, 10, -3, 18};

int arraySum = 0;
for (int i = 0; i < a.length; i++)
    arraySum += a[i];

In general, any code can be expressed as a recursive function.

But why do we need recusion? Often, recursive implementation is much easier, and sometimes non-recursive implementation is very hard, or seems almost impossible.

As an example, let's write a function to print all strings of length N that consist only of characters 'A', 'B' and 'C':

/* f() prints all string of length N consisting only of characters 'A', 'B', and 'C'. 
Our state will be the length N, and the current string that we have built so far */
void f(final int N, String currentString /* State */) {
    /* Base or terminating case */
    /* If we already built the string of length N, just print it. */
    if (currentString.length() == N) {
        System.out.println(currentString);
        return;
    }
    
    /* Operations on state, and possible calls to f() function again */
    /* We are still building the string, so let's try adding 'A', 'B', and 'C' to it. */
    f(N, currentString + "A");
    f(N, currentString + "B");
    f(N, currentString + "C");
}

// prints all strings of length 5 consisting of 'A's, 'B's, and 'C's. 
// Note how we start with an empty string
f(5, "");

While it's possible to achieve the same result non-recursively, the recursive implementation is arguably much simpler and more straightforward.

Try to understand how the codes above work. It may be helpful to run them on your own, try some small modifications, and see what the output is.

Backtracking

Backtracking is a general method of recursively trying all possible solutions for the problem. See the next section to learn more about it:

void f(final int N, String currentString) {
  if (currentString.length() == N) {
    System.out.println(currentString);
    return;
  }

  f(N, currentString + "0");
  f(N, currentString + "1");
}

f(3, "");