Learn Functional Programming with Elixir/

...

/

Conquering Recursion

Conquering Recursion

Explore the 'decrease and conquer' and 'divide and conquer' techniques for solving problems using recursion.

We'll cover the following...

Introduction to conquering recursion

For many developers, recursive functions are one of the hardest things to understand when moving to functional programming. It can be confusing to find the stop condition clause or to even make the function call itself.

Functional programmers work with recursive functions more than developers in other paradigms because recursive functions are the core of code repetition in functional programming. While recursive functions can be intimidating, functional programmers need to be comfortable using them in their programs.

There are two helpful techniques for solving problems using recursive functions: decrease and conquer and divide and conquer. We’ll explore them next.

Decrease and conquer

Decrease and conquer is a technique for reducing a problem to its simplest form and starting to solve it incrementally. By doing this, we find the most obvious solution to a tiny part of the problem. From there, we start to conquer progressively, incrementing the problem step by step. Let’s experiment with this approach using a well-known problem: the factorial.

The factorial of a number is the product of all positive integers less than or equal to it. If we want to know the factorial of 3, we use the 3 * 2 * 1 expression. Using the decrease and conquer strategy, the first step is to find the base case, the simplest factorial scenario. We’ll use the base case to help solve more complex ones. Let’s write it in a module, expecting a number from 0 to 4:

defmodule Factorial do
  def of(0), do: 1
  def of(1), do: 1
  def of(2), do: 2 * 1
  def of(3), do: 3 * 2 * 1
  def of(4), do: 4 * 3 * 2 * 1
end

The factorial for the number 4 is 4*3*2*1, for the number 3, it’s 3*2*1, and so on until we find the solution. The base scenario for the factorial is when the argument is 0 or 1. We can’t keep going because a factorial works only with positive numbers. We don’t need calculations for 0 and 1 because the result is 1. We can compile the code and try what we have done using IEx: ...