Hi everyone !

In this article, we will se how to go from a simple recursive solution for a problem, to its iterative version.

Definitions

Recursion is basically when an element call itself. Solving a problem using recursion aims to break that problem into smaller versions of it, easier to solve.

There are plenty of recursion types (tail, generative, etc.) and all of them are more or less easier to understand and/or implement; however, pretty much every algorithm can use either recursion or iteration to find the same result. The problem is that sometimes switching from one way to another may be hard.

Practice

Let's have a look on a simple example.

Given `l` an array of integers and `i` an integer, return the number of occurences of `i` in `l`.

Recursive solution

This problem is no big deal and can easily be solved with recursion.

We will need:
- a base case: a condition that will stop our recursion to avoid infinite looping;
- Treatment: how will we handle and process the given arguments;
- Recursive call: change our parameters to handle the next part of the problem.

Here those parts seems quite obvious:
- base case: if there is no more element in the list, we can stop;
- treatment: if the first element is the number we are looking for, we will increment the counter of occurences;
- recursive call: we will continue to loop through the tail of the list.

Nb:

If you are not familiar with head and tail in a list, here is a representation:

[   1,   2, 3, 4, 5, 6 ]
| head |     tail      |

Implementation

    def rec_occurrence(l: List[Int], i: Int): Int = {
        // base case
        if (l == Nil) {
            0
        }
        // recursion
        else if (l.head == i) {
            1 + rec_occurrence(l.tail, i)
        }
        else {
            rec_occurrence(l.tail, i)
        }
    }

Recursive solution (bis)

Our previous solution is working perfectly fine but won't lead us anywhere as it is: we must first change it to tail recursion. Tail recursion is when the last call of your recursive algorithm is the recursion itself.

In this example, we have something like:

    1 + rec_occurrence(l.tail, i)

Instead of just the function call.

Implementation

In order to solve this, we will use an accumulator, a counter that we will keep as a parameter.

We have to build a nested function, working as the first one, bus using this parameter. The main function will then just call our nested one.

All of these results in:

    def rec_acc_occurrences(l: List[Int], i: Int): Int = {

        def lambda_occurrence(l:List[Int], i:Int, acc:Int): Int = {
            // base case
            if (l == Nil) {
                acc
            }
            // recursion
            else {
                if (l.head == i) {
                    lambda_occurrence(l.tail, i, acc + 1)
                } else {
                    lambda_occurrence(l.tail, i, acc)
                }
            }
        }

        rec_acc_occurrences(l, i, 0)
    }

Here, our last call is only the function in either way:

lambda_occurrence(l.tail, i, acc + 1)
// or
lambda_occurrence(l.tail, i, acc)

Problem solved !

Iterative solution (finally)

From the last function we made, rec_acc_occurrences, we can build our recursive implementation.

In Scala, we will first need to copy the given parameters, in order to use and modify them later.

Then, we will use a while loop in which we will put our logic. The breaking condition of this while will be what avoided us an infinity loop: the base case condition. Then, at the end of this loop, we will update our parameters as we did in the recursive call, to cover all elements of our list. Finally, all we have to do is returning the final result.

Implementation

    def iter_occurrence(l: List[Int], i: Int): Int = {
        // parameters copy
        var m = l
        var j = i
        var acc = 0

        // base case condition        
        while (m != Nil) {
            // logic
            if (m.head == j) acc += 1
            // parameters update
            m = m.tail
        }
        // base case return
        acc
    }

And we're all good ! We went from a recursive solution to an iterative one, with some extra steps. In this example, going through this process might seems to be a bit too much, but it will work no matter what is your recursive algorithm and doesn't need to "feel" the iterative way of solving your problem.

Thanks for reading, I hope this may help !