The 3 Rules For Writing A Recursive Function

Recursion is a computational tool that involves an element calling upon itself. While recursion is often an unnecessarily taxing approach in terms of CPU demand, it can offer an elegant, efficient, and clean solution to some CS tasks. You're not alone if you've struggled to solve recursive algorithms, as recursion can be difficult to conceptualize. In this tutorial, I will define recursive functions, demonstrate some common algorithmic applications, and highlight some important aspects to keep in mind when writing recursive functions. Example code will be written in JavaScript and Ruby.

Recursive Functions

A recursive function is one that is invoked within its own definition. For example, let's consider a program which prints integers between its input and 1 to the console. You've likely seen this done through looping:

JavaScript:

const printRange = n => {
    for (let i = n; i > 0; i--) {
        console.log(i);
    }
}

printRange(4)
// => 4
// => 3
// => 2
// => 1

Ruby:

def print_range n
    n.downto(1) { |x| puts x }
end

print_range 4
# => 4
# => 3
# => 2
# => 1

With recursion, we could write the program like this:

JavaScript:

const printRange = n => {
  if (n < 1) return;
  console.log(n);
  printRange(n - 1);
}

printRange(4)
// => 4
// => 3
// => 2
// => 1

Ruby:

def print_range n
  return nil if n < 1
  puts n
  print_range n - 1
end

print_range 4
# => 4
# => 3
# => 2
# => 1

As you can see above, the recursive solution begins by checking if n is less than one, returning nothing if it is. In the case that n 1 or greater, the program prints n, then invokes itself, passing in n - 1. Following the above example of print_ range 4, the first pass through the function skips the ending condition, prints 4, then calls itself passing in 3, skipping the ending condition, printing 3, and so on, until the ending condition is met. This is a simple program, but it highlights all the important things to keep in mind when writing a recursive function:

1. Recursive functions must contain a base case (an ending condition) so the recursive call doesn't create an infinite loop. In our print function example above, checking if n < 1 gives our program a way to stop calling itself after it prints 1.

2. The base case must be evaluated before the recursive case so the function has an opportunity to end the loop. If we called our printing function before checking if n < 1, we would create an infinite loop.

3. The recursive call must increase or decrease its input such that the input is closer to the ending condition. By decrementing n with each call of our printing function, we are closer to n < 1 with every recursive call.

Elegant Recursion

There are some situations in which recursive logic can help us save lines in our code. Take for example an algorithm that calculates the Nth number in the Fibonacci sequence. An iterative approach might look like this:

JavaScript:

const fib = n => {
  const arr = [0, 1];
  if (n <= 2) return 1;
  for (let i = 2; i <= n; i++) {
    arr[i] = arr[i - 1] + arr[i - 2];
  }
  return arr[n];
}

console.log(fib(10));
// => 55

Ruby:

def fib n
  return 1 if n <= 2
  first = 1
  second = 1
  until n < 3
    result = first + second
    first = second
    second = result
    n -= 1
  end
  result
end

puts fib 10
# => 55

With recursion, we can clean up our solution to this:

JavaScript:

const fib = n => n < 2 ? n : fib(n - 1) + fib(n - 2);

console.log(fib(10));
// => 55

Ruby:

def fib n
  return 1 if n <= 2
  fib(n - 1) + fib(n - 2)
end

puts fib 10
# => 55

Dangers of Recursion

On top of being difficult to grasp and unintuitive to read, recursion is also often more taxing on our CPU than other alternatives by being less efficient and requiring our machines to perform more tasks. This is the case for our first example, where the non-recursive program's only task was printing, and not checking conditions and invoking within itself. This is why you don't often see recursive solutions for basic looping tasks.

Back to our Fibonacci algorithm example, we can see that recursion can do a lot to make code shorter, but is it as efficient as the iterative approach? The answer is no. Our the first solution has a linear time complexity of 0(n), while the recursive solution increases that time complexity to 0(2^n). So while more concise, it is much less efficient.

When Recursion Is Used

There are situations where recursion is the best approach to an algorithmic problem. A common use of recursion is in binary searches. Consider writing an algorithm to search for a number in a long, sorted list of numbers. An iterative approach would likely include looping over all the numbers in the list to check if one is equal to the target number. That solution would look something like this:

JavaScript:

const searchNumber = (arr, target) => {
  for (const item of arr) {
    if (item === target) return true;
  }
  return false;
}

const arr1 = [1,2,4,5,6,7,8,9,10,11,12,14,15,16,17,18]

console.log(searchNumber(arr1, 13));
// => false

console.log(searchNumber(arr1, 6));
// => true

Ruby:

def search_number (arr, target)
  arr.each do |item|
    return true if item == target
  end
  false
end

arr1 = [1,2,4,5,6,7,8,9,10,11,12,14,15,16,17,18]

puts search_number(arr1, 13)
# => false

puts search_number(arr1, 6)
# => true

With an array input is this small, the iterative approach doesn't seem too costly. Imagine, however, if our input array included thousands of numbers, or more. Then we would want to think about ways to make our search more efficient.

Binary Searches

Binary searches offer an efficient approach to this problem. With binary searches, each "checking task" is able to dismiss half of the remaining input. Let's say we are checking for the number 78 in a sorted list of numbers between 1 and 100. If we check the number(s) in the middle of the array, let's say 46, we can dismiss half of the array by checking if our target is smaller or bigger than the mid-value. If our target is 78, we can dismiss all the numbers less than our mid-value of 46. The next check would then be applied to the mid-value of the top-half of the input array (46 - 100), and so on. This improvement reduces the iterative search time complexity from O(n) to O(log n), a massive improvement. Recursion can help us with binary searches:

JavaScript:

const searchNumber = (arr, target) => {
  let mid = Math.floor(arr.length / 2);
  if (arr.length === 1 && arr[0] != target) return false;
  if (target === arr[mid]) return true;
  if (target < arr[mid]) return searchNumber( arr.slice(0, mid), target);
  return searchNumber(arr.slice(mid + 1), target);
}

const arr1 = [1,2,4,5,6,7,8,9,10,11,12,14,15,16,17,18]

console.log(searchNumber(arr1, 13));
// => false

console.log(searchNumber(arr1, 6));
// => true

Ruby:

def search_number (arr, target)
  mid = (arr.size / 2).floor
  return false if (arr.size == 1 && arr[0] != target)
  if target == arr[mid]
    true
  elsif target < arr[mid]
    search_number(arr[0, mid], target)
  else target > arr[mid]
    search_number(arr[-mid, mid], target)
  end
end

arr1 = [1,2,4,5,6,7,8,9,10,11,12,14,15,16,17,18];

puts search_number(arr1, 13)
# => false

puts search_number(arr1, 6)
# => true

As you can see, the recursive solution is longer than the iterative solution. It is, however, much more efficient, despite being recursive. While you can conduct a binary search without recursion, you'll commonly see them carried out recursively. This is due to binary searches being efficient enough to handle the burden of recursive calls.

To put it in perspective, imagine searching for an item in a list of a million. This is not a far fetched scenario considering the size of modern databases. With iteration, your maximum number of checks is a million, no getting around that. With the binary search, it will take you at most 20 checks. Now you can see why this is one of few areas where we can afford to use recursion.

Interactive Fractal Tree

To see recursion in action in an interactive fractal tree I made using p5.js, click here. The recursive function doing the heavy lifting is below (Note: I am using the p5.js library, which where functions like line(), pop(), push(), translate(), strokeWeight(), and rotate() are coming from). Can you spot the base case?

function branch(len) {
  weight = Math.log(len) / 2
  strokeWeight(weight);
  line(0, 0, 0, -len);
  translate(0, -len);
  if (len > 4) {
    push();
    rotate(angle);
    branch(len * 0.67);
    pop();
    push();
    rotate(-angle);
    branch(len * 0.67)
    pop();
  }
}

Conclusion

In this post we learned a lot about recursion. We learned what it is, and the three most important things to keep in mind when writing a recursive funciton:

1. Always include a base case (ending condition)
2. The base case is evaluated before the recursive case
3. The recursive call is given an input that's closer to the ending condition

We also saw that using recursive logic can help us save a lot of lines in our code, but that we must use it sparingly to avoid over-taxing our CPUs and slowing down our programs.

Finally, we looked at how recursion and binary searches can help us vastly improve the efficiency of certain search algorithms, and discussed how time complexity can be increased or decreased with recursion, depending on the situation.

You are now equipped to go out and write your own recursive functions. You could make an interactive recursive fractal tree, like the one I made. Just make sure not to get lost down that recursive rabbit hole!