Recursion

Learn how to create recursive functions in Kotlin.

What is Recursion?

Recursion is the process in which a function calls itself until a condition is met. This concept is similar to a while loop in which a body of code will be executed repeatedly until a condition is met.

Recursion is an advanced topic when it comes to functions and programming; it often takes time and practice until a programmer is comfortable with creating and using recursive functions so don’t feel discouraged if it doesn’t all stick right away.

Breaking Down a Recursive Function

In a recursive function, a base case (usually an if expression) is created to check for a condition. If the condition is true, then the function will return a value. If the condition is false, the function will return a function call to itself with a new set of argument values; this is known as a recursive call. The function will continue to call upon itself until the base case is reached.

Let’s use a recursive function to get the sum of a group of numbers from num until 0:

fun recursiveSum(num: Int): Int { // base case if (num == 0) { return num } else { // recursive call return num + recursiveSum(num - 1) } }

If we were to call this function with an argument of 4, we would get a return value of 10. Let’s try and break down how that worked. Until the parameter num has a value of 0, the code in the else block, return num + recursiveSum(num - 1), will be executed like so:

  • recursiveSum(4) returns 4 + recursiveSum(3).
  • recursiveSum(3) returns 3 + recursiveSum(2).
  • recursiveSum(2) returns 2 + recursiveSum(1).
  • recursiveSum(1) returns 1 + recursiveSum(0).

Once we call recursiveSum(0), the base case is reached because num is 0. Now, we need to return the value from each call starting from the last call made.

  • recursiveSum(0) returns 0.
  • recursiveSum(1) returns 1 + 0 which equals 1.
  • recursiveSum(2) returns 2 + 1 which equals 3.
  • recursiveSum(3) returns 3 + 3 which equals 6.
  • recursiveSum(4) returns 4 + 6 which equals 10.

Note: Like a while loop, a recursive function can run infinitely if we do not create a base case that eventually stops the recursive calls.

Let’s practice creating our own recursive function: