Recursion

Introduction

So far we've mostly used functions to make them do something for us: sometimes print a certain number and sometimes perform calculations and return the result to us. Sometimes we might pass the return value of one function to another one, and sometimes functions might use other functions to achieve the result.

However, there is one more significant use case when it comes to functions.

Recursion

Apart from doing all the above, we could make a function call itself, and sometimes such a move makes the solution easier. When a function calls itself, the process is known as recursion.
Here’s a code snippet that demonstrates a function that prints the star symbol n times:

fun printStars(n: Int) {
    if (n < 1) return
    print("*")
    printStars(n - 1)
}

Basically, the workflow of this function can be described as follows: “if there are still some stars left (n > 0), print a star and then call myself with the number of remaining stars to be printed (n-1).”

Let's look at a more complex example of the factorial function. You already know what the factorial is – apparently, this mathematical concept might be considered a classical use case for recursion.

To get the factorial f(n), we need to multiply all positive numbers less than or equal to n, i.e., 1 * 2 * 3 * 4 * ... * n . This process can be viewed as taking 4, multiplying it by 3, taking the result (12), multiplying it by 2, and so on. So for a given positive number n, we need to multiply n by the factorial of n-1. Therefore, if we know how to get f(n-1), we can easily get f(n). Let’s use this idea to make a recursive factorial function:

fun factorialRecursive(n: Int): Int {
    if (n == 0 || n == 1) return 1
    return n * factorialRecursive(n - 1)
}

Terminal condition

Consider the following example:

fun printStars(n: Int) {
    print("*")
    printStars(n - 1)
}

At the first glance, it might seem the same as the function we saw earlier (the one that prints stars), but it has one significant difference. It never stops. It just keeps calling itself with changing parameters until the machine executing this code runs out of memory (or some other unpleasant thing happens).

Recursion should always be used very carefully. If there are no conditions to stop a recursive function from another recursive call, it gets stuck in a never-ending loop of invoking itself, which would break the program eventually. Therefore, to use recursion properly and not make our PC run out of RAM, we need to limit it and always make sure we have a terminal condition – with the factorial, it’s when the function gets n equal or less than 0.

Recursion Tracing

Recursion is quite a difficult topic to grasp at first, so we need some way to be able to trace it and see what final result the function is giving us.

Sure you can copy-paste a code snippet and run it in the IDE, but what happens when you get a StackOverflow error or a result that you are not expecting? You don't really know what went wrong.

This is where we can apply manual tracing (tracing by hand) and see what exactly is going on at each step of the recursive function.

Consider the next code snippet:

fun m(x: Int, y: Int): Int {
  return if (x < y) {
    x
  } else {
    m(x - y, y)
  }
}

Imagine you were asked what output the m(50, 7) function invocation would return. You would probably start doing the tracing in your head, and after 4-5 calls, you would lose track of the calls. So here is an example of how you can trace such a function easily:

m(50, 7) -> m(43, 7)
  m(43, 7) -> m(36, 7)
    m(36, 7) -> m(29, 7)
      m(29, 7) -> m(22, 7)
        m(22, 7) -> m(15, 7)
          m(15, 7) -> m(8, 7)
            m(8, 7) -> m(1, 7)
              m(1, 7) -> 1 // we hit the base case, time to go back
          m(8, 7) -> 1
         m(15, 7) -> 1
        m(22, 7) -> 1
      m(29, 7) -> 1
    m(36, 7) -> 1
  m(43, 7) -> 1
m(50, 7) -> 1 // 1 is the answer

This way, we can visualize the function operation with ease and tell what is happening at each step. Trying a different invocation e,.g., m(37, 10), we will see a pattern and will be able to conclude that this recursive function is calculating x % y.

This small technique can help you solve more complex recursion problems and, most importantly, visualize a recursive function.

Replacing recursion by a loop

Each recursive function can be represented with a corresponding loop. In the recursive factorial function, the call of f(n) is always followed by the call of f(n-1), so in any consecutive pair of calls, n differs exactly by 1. So, if functions are always called with "n, n-1, n-2, n-3...", why don't we just make a loop to make everything easier? Let’s use this idea to implement a non-recursive solution:

fun factorial(n: Int): Int {
    var f = 1
    for (i in 1..n)
        f *= i
    return f
}

Types of recursion

There are several types of recursion:

1. Direct recursion

It’s the case when a function simply calls itself only once. Our recursive factorial makes a good example:

fun factorialRecursive(n: Int): Int = if (n == 0 || n == 1) 1 else n * factorialRecursive(n - 1)

2. Indirect recursion

This is the case when a function uses some other function, which, in turn, calls the former function. There’s no necessity to do it like that, but a modified version of the factorial function can be an example:

fun weirdFactorialRecursive(n: Int): Int = if (n == 0 || n == 1) 1 else factorialCompute(n)

fun factorialCompute(n: Int): Int = n * weirdFactorialRecursive(n - 1)

3. Tail recursion

A function utilizes tail recursion if a recursive call is the last thing the function does.

See, for example, a factorial function with the final call being recursive. This version is a bit different, since usually, we do multiplication last, while here we do it before passing the result to the recursive call.

fun tailFactorialRecursive(n: Int, cur: Int = 1): Int {
    if (n == 0) return cur
    return tailFactorialRecursive(n - 1, cur * n)
}

Why does tail recursion stand out as a separate type? Because modern compilers can more efficiently work with it. To compute another call of a recursion function, the compiler usually pushes the stack frame onto the stack of operations to be performed, therefore, creating a new set of local variables, which costs time and space. In the case of tail recursion, the compiler can just return to the beginning of the function to continue working with the same variables it already has in the current stack frame.

4. Multiple recursion

This is the case when a function makes several calls to itself. As an example, there is a well-known sequence of numbers called the Fibonacci numbers. In this sequence, each next number is the sum of the two preceding ones, starting at $F_0 = 0$, $F_1 = 1$. Then, each new Fibonacci number is calculated as follows: $F_n = F_{n-1} + F_{n-2}$.

A program for calculating this sequence utilizes multiple recursion: in order to compute the current Fibonacci number, we need to compute the two preceding ones, therefore making 2 recursive calls:

fun fibonacci(n: Int): Int {
    if (n <= 0) return 0
    if (n == 1) return 1
    return fibonacci(n - 1) + fibonacci(n - 2)
}

However, this solution is extremely inefficient, as recursion branches each time we need another number; therefore, the number of calls and calculations grows exponentially.

Optimizations

As we've already noted, multiple recursion in the case of the Fibonacci sequence is extremely inefficient due to computing numerous values for a great number of recursion branches. Apart from turning recursion into a loop, there is yet another method of optimizing it, which is called memoization.

Calling f(6), for example, would call f(5) and f(4), and f(5), in its turn, would also call f(4). The basic version would compute f(4) two times, and it gets worse for the numbers which are used more often.

How could we make our function compute the required number only once? Let’s save it to an array once we compute it and make all other recursion branches first check if the value has already been computed. If not, they will do it, but if the value is already there, it can be used right away. Here’s a version of the same algorithm with memoization:

val fibList = MutableList(1000){0}

fun coolerFibonacci(n: Int): Int {
    if (n <= 0) return 0
    if (n == 1) return 1
    return if (fibList[n] != 0) fibList[n]
    else {
        fibList[n] = coolerFibonacci(n - 1) + coolerFibonacci(n - 2)
        fibList[n]
    }
}

One more possible optimization method involves replacing recursion with a loop, which may be used, for example, in the case of calculating the Fibonacci sequence. Why calculate a needed number if we can basically iterate through all required numbers:

fun fibonacciLoop(n: Int): Int {
    var n0 = 0
    var n1 = 1
    for (i in 1 until n) {
        val cur = n0 + n1
        n0 = n1
        n1 = cur
    }
    return n1
}

Memoization is very helpful if you often need to calculate a value of a recursion function. However, if you need to calculate the result only once, you may try optimizing the function with a loop. You don't need to optimize every single recursion function – just try not to calculate the same numbers twice or more.

Conclusion

Despite the fact that recursion should be used very carefully, it is a very convenient tool when it comes to certain types of problems. To solve a problem via recursion, we only need to define the base case (such as returning 1 if asked for the factorial of 0 or 1) and the recursive case (such as the factorial of n being dependent on the factorial of n-1), and then recursion does the rest. So the main point of using recursion is the simplicity of implementation for some complex ideas, as you can see in various graph algorithms.

Therefore, recursion is most useful when we can divide a certain problem into sub-problems, each of which being a smaller version of the original one.