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 !
Top comments (3)
What I am missing here is an explanation of why someone would want to convert a recursive solution to an iterative one.
Often a recursive solution is easier to understand and to maintain which can be a huge benefit. On the other hand, if performance (both time and memory) really matters, iterative solutions are practically always superior.
Some compilers have tail recursion optimization, which basically means that they perform this conversion internally and automatically, offering you the best of both worlds.
Since your last paragraph can be a little confusing, for anyone that's wondering:
Tail Call Optimization optimizes the iterative function explained in this article, while it's unable to optimize the function in the first example.
Each time a function is called, the program has to allocate memory for all of the parameters used in the functions. These cannot be unallocated until the compiler/interpreter is certain they won't ever be used again.
Normally this means whenever the function is exited, which in the first example first happens after adding "+1" to the return value of the called function.
In the iterative function the returned value won't be modified, so it can deallocate the original function immediately, and only concentrate on the new function call. (I'm paraphrasing a little, optimization might not work exactly like this, and it might do additional optimization, but this is the general gist of the idea behind it)
Well, it may not be needed but I thought it was interesting to know and to share. It may also help someone to understand how some compilers convert some recursive algorithms into iterative ones.