Recursion in Functional Programming

One of the guidelines for functional programming is that procedures should have no side effects, which means that we are not allowed to change a variable or modify the value of a parameter that has been passed. Functional programming prefers immutable objects which, once defined, cannot be modified later. In this topic, we will see why recursion is preferred in functional programming and see a scenario where recursion is suitable and another scenario where it is not suitable

Recursion in terms of functional programming

numbers = [1, 2, 3, 4]
for i in range(0, 4):
    print(numbers[i])

When we loop by incrementing a variable, our loop depends on mutation because the variable changes in each iteration as we are reassigning the variable i.

If we iterate the elements in a list by using the in keyword, we are getting somewhat closer to functional programming. However, there is still repeated rebinding of the variable i and therefore a change in the program state.

numbers = [1, 2, 3, 4]
for i in numbers:
    print(i)

Can we do better? Yes, the following code can be written as:

list(map(print, numbers))

The map function is a higher-order function that applies another function to each list element. Utilizing a map can transform a list into a new data stream without resorting to explicit loops or mutable state changes. It leads to a more declarative and concise code style, simplifying the implementation, enhancing readability, and reducing the likelihood of introducing errors.

The Tower of Hanoi problem

Tower of Hanoi is a mathematical game that is commonly used as a recursion and optimization problem. There are three towers in the game, and one of the towers contains a stack of disks in decreasing order of size from bottom to top. We must move the disks from the Source tower to the Destination. During the game, a larger disk cannot be put over a smaller disk.

There are three towers as follows:

• Source

• Auxiliary (the tower which is neither source nor destination, but is used for staging the disks)

• Destination

For $n = 1$, this is a trivial task: we move the only disk to the destination tower.

For $n = 2$, we can move the small disk to the empty auxiliary rods; by that, we free the large disk and can move it to the destination rod.

For $n = 3$, this task is complex: for this, we need to figure out when we need to move the largest disk.

First, the largest disk should be the only disk in the source tower to be able to move it. Second, we need an empty tower to stage the largest disk, this is the destination tower. Therefore, the two small disks should be placed on the auxiliary tower in the correct order.

To achieve this, first, we need to move the two smaller disks from the source tower to the auxiliary one. Do you see where we are going? We did this exactly for $n = 2$ (this is a recursive statement), when we move two smaller disks, the largest one is not an obstacle as any disk can be placed on top of it.

After these preparations, we move the largest disk to the destination tower. Hence, we need to achieve the following configuration.

Let's consider the general case now.

• To move the largest disk, we need to leave it as the only disk in the rod.

• We are only allowed to move the largest disk only if the destination is an empty rod.

From these two observations we can infer that $n -1$ towers should be on the auxiliary tower, the position before moving the largest disk should be as follows:

The dotted arrow shows the preparation moves. All the disks except the largest one should be moved to the auxiliary tower. Then we move the largest disk to the destination tower, then we bring the other disks to the Destination tower as shown below.

The dotted arrow shows the moving of the smaller disks on top of the largest disk.

Now, these three steps are very important for devising a recursive procedure for the Tower of Hanoi problem. We can now use recursion to recursively call the solution for $n - 1$ disks. You can try out the game on Math is Fun.

The algorithm goes like this:

def move(disk, source, destination, auxiliary):

    if disk == 1:  # if you have one disk, move it directly to the destination tower
        print(f"Move disk from {source} to {destination}") 
        
    else:  # for multiple disks
        move(disk-1, source, auxiliary, destination)  # move all except largest disk to the auxiliary tower
        print(f"Move disk from {source} to {destination}")  # move the largest disk to the destination tower
        move(disk-1, auxiliary, destination, source)  # move the disks from the auxiliary tower to the destination tower

move(3, "a", "c", "b")

By using the same function to move one and several disks, we can reduce the process of moving $n$ disk to moving $1$ disk and $n -1$ disks. We can directly move one disk, so that's easy. However, using the same trick, we can keep breaking down $n - 1$ to $n - 2$, then $n - 3$, etc, until we're only left with a sequence of moves of a single disk, which is trivial to execute.

That's generally how recursion works: keep breaking the problem down, until you're only left with instances of the base case (in this case, moving a single disk) and instructions on how to assemble multiple instances of the base case to solve more complex ones.

We need to follow the tracing from left to right of the tree and move the disks accordingly.

Notation in the diagram:

• Source → (a)

• Auxiliary → (b)

• Destination → (c)

Recursion is not always suitable, now we will see a bad usage of recursion.

Bad usage of recursion

Immutable objects and recursion are very handy concepts, but they can be extremely inefficient in some cases, as recursions are inefficient for large problems which are non-linear. One such problem is the recursive implementation of the Fibonacci series.

A Fibonacci series is a series of numbers where the next element is found by summing up the previous two elements, the first few values are: 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on

def fib(number):
    if number == 0:
        value = 0
    elif number == 2 or number == 1:
        value = 1
    else:
        value = fib(number-1) + fib(number-2)
    return value

print(fib(5))  # 5

Look at the following Fibonacci tree diagram for calculating $5th$ Fibonacci number. Initially for fib(5)call we go down the tree till we hit a base case. After reaching the base case, we backtrack and calculate the values for each node in the tree. For example, for calculating fib(2) from the tree, we simply add fib(1) and fib(0) to get 1, we already know the value of fib(1) and fib(0) which are set as the base case.

Calculating fib(5) requires us to calculate fib(4) and fib(3). This is where the inefficiencies arise, calculating fib(4) also requires us to calculate fib(3). It means that fib(3) will be calculated twice, because these calculations happen in separate branches of the recursion tree. This particular algorithm grows exponentially instead of linearly, because each call of fib() branches off into two more calls and continues on this track. Thus, increasing the size of number heavily increases the time required to complete the calculations. A more efficient implementation using dynamic programming and memoization can be done to improve the time complexity

def fib_efficient(n, memo={}):
    if n <= 0:
        return 0
    elif n == 1:
        return 1
    elif n not in memo:
        memo[n] = fib_efficient(n-1, memo) + fib_efficient(n-2, memo)
    return memo[n]

print(fib_efficient(10)) # 55

This is a more efficient solution, as it uses memoization to store the results of previously calculated Fibonacci numbers and reuses them instead of recalculating them. This significantly reduces the time complexity.

Conclusion

In this topic, we have seen recursion is preferred in functional programming because we don't need a mutable state while solving a problem as they can produce side effects. Moreover, recursion makes it possible to specify a semantic in simpler terms. We have seen how recursion can be used by avoiding loops and in a more functional way for certain algorithms. Recursion works best for cases when a problem can be divided into sub-problems calculated separately and how the problem is solved is the same as the smaller sub-problems. Recursion is preferred for Tower of Hanoi because it is concise and elegant, whereas it is not preferred for naive Fibonacci series recursion because it recomputes the same value repeatedly, we can improve the naive version with memoization so that the same values are not computed repeatedly.