SICP series (part2) : recursive process vs iterative process
Introduction
In this article we will dive into iterative and recursive process using the substitution model that we explored in the previous article of the SICP series.
Iterative process
In C like languages like Javascript , Java (languages not built specifically for FP) and so on iteration is usually achieved with a for or while loop.
Let's take a simple program that compute the factorial of number n written in an iterative way in javascript:
1
2
3
4
5
6
7
function factorial(n) {
let product = 1; // we assume that we won't pass a number less than 1
for (let i = 2; i <= n; i++) {
product *= i;
}
return product;
}
this JS version use assignment ( which is not really FP friendly) and Scheme does not have a for key word to achieve iteration.
Let's write the iterative version in Scheme:
1
2
3
4
5
6
7
8
9
(define (factorial n)
(fact-iter 1 1 n))
(define (fact-iter product i max-count)
(if (> i max-count)
product
(fact-iter (* i product)
(+ i 1)
max-count)))
“We have a base case to return the result when i is superior to max-count and a function fact-iter that call itself so it is a recursive function thus a recursive process right not an iterative one ?”
Well yes it is a recursive function but it is still an iterative process, an iterative process maintain some kind of state through each step of the process,
in the iterative version of the factorial function the states are the product and i (which is a counter) with the for loop each variables are reassigned at each step of the for loop and with the recursive function the variables are just passed between function calls but the two implementation are an iterative process.
Let's use the substitution model to see the evolutions of the product and i states:
1
2
3
4
5
6
7
8
(factorial 6)
(fact-iter 1 1 6)
(fact-iter 1 2 6)
(fact-iter 2 3 6)
(fact-iter 6 4 6)
(fact-iter 24 5 6)
(fact-iter 120 6 6)
(fact-iter 720 7 6)
The time complexity is O(n) for the JS version and the Scheme version and the space complexity is O(1) for the Scheme version thanks to the tail call optimization (tail call recursion is when the last line is a call to the function itself and nothing else which is not the case in recursive process) and same thing for the for loop version in Javascript.
Recursive function in Javascript and Java for exemple don't benefit from tail call optimization (except in Safari for Javascript) so the space complexity for recursive functions in these languages is O(n).
Recursive process
Let's write the factorial function with a recursive process to see the difference with the iterative process.
1
2
3
4
(define (factorial n)
(if (= n 1)
1
(* n (factorial ( - n 1)))))
What is really striking is how short the solution is compared to the iterative version and how close the recursive process is from the mathematical representation of a factorial which is n! = n * (n-1) * (n-2) … 3 * 2 * 1.
The function also looks kind of magical because it does not explicitly maintain the product state neither a count state let's unveil this magic by applying some substitution to see how this function works under the hood:
1
2
3
4
5
6
7
8
9
10
11
12
(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720
We can see that the computation is differed untill the process reach the condition (= n 1) and that the interpreter is maintaining some hidden informations which is (* n (factorial (- n 1)) we can't really know the value of the product at each steps of the process unlike the iterative process because the computation is differed.
We also see that the shape of a recursive process is different of the shape of an iterative one.
The iterative process is like a line it does not grow and the iterative one grow significantly on the right and retract itself to the left which make it looks like a triangle turned on the right.
We can see now the the advantages and the drawbacks of the two processes.
The recursive process is shorter and more readable than the iterative one because it is closer from its mathematical representation but the drawback of the recursive process is that it is less performant because it rely on the interpreter to maintain some informations, it has a space complexity of O(n) because it is not tail recursive (the last line of the function is not just a call to itself).
Conculsion
I expect that now you understand the difference between iterative process and recursive process better.
Another important point of this article is that recursive function ≠ recursive process.
I hope that you found this article interesting, stay tuned for the next article of the SICP series.