National Higher School of Technology and Engineering Annaba
Department of preparatory classes Computer Science 2 Course
First Year 2025/2026
Chapter 4: Recursive Algorithm Concept
In the previous chapter, we saw that recursion is a general concept that can be illustrated in (almost) all
advanced programming languages, enabling the expression of concise, easy-to-write, and easy-to-understand
algorithms. A recursive algorithm allows, among other things, to solve a problem by computing solutions of
smaller instances of the same problem.
Indeed, any recursive algorithm can be written in an iterative form (An algorithm is said to be iterative when
it uses loops). In general, it is necessary to become accustomed to both styles of programming, in order to
make the most objective choice later on. However, the choice between a recursive or iterative version of an
algorithm must be made based on several criteria, but primarily on simplicity: which version is easier to
understand? Which one best reflects the nature of the problem? Which one is more flexible and will allow you
to add modifications/improvements to the algorithm later on?
In this chapter, we will see how to convert a recursive algorithm into an iterative one.
1. Converting a Recursive Algorithm to an Iterative Algorithm
In theory, it's always possible to convert a recursive algorithm into an iterative one, but in practice, it's not
always easy! This transformation is easier for a tail-recursive algorithm.
1.1. Converting a Tail-Recursive Function
The characteristic property of tail recursion is that in the sequence of calls made, there's no need to
remember what needs to be done after the function returns. A tail-recursive function has the general form:
return_type function_name(parameters)
{
// Instruction block 0
if(Condition)
{
// Instruction block 1
}
else
{
// Instruction block 2
return function_name(f(parameters));
}
}
Where:
parameters is the list of parameters.
Condition is the termination condition.
Instruction block 0: the block of instructions executed in all cases.
Instruction block 1: the block of instructions executed if Condition is true.
Instruction block 2: the block of instructions executed if Condition is false.
f is the parameter transformation function.
Note that instruction blocks 0, 1, and 2 can be empty.
The corresponding iterative function is:
return_type function_name(parameters)
{
// Instruction block 0
Dr N. lachtar 1
National Higher School of Technology and Engineering Annaba
Department of preparatory classes Computer Science 2 Course
First Year 2023/2024
while(!Condition)
{
// Instruction block 2
parameters = f(parameters);
// Instruction block 0
}
// Instruction block 1
}
Example:
The tail-recursive version of the factorial function is:
int factorial(int n, int a)
if(n == 0) return a;
else return factorial(n-1, n*a);
}
List of parameters P: n and a.
Condition: n==0.
Instruction block 0: doesn't exist.
Instruction block 1: return a.
Instruction block 2: doesn't exist.
Parameter transfer function f(n, a): (n=n-1, a=n*a).
The corresponding iterative function is:
int factorial(int n, int a)
{
while(n != 0)
{
a = n*a;
n = n-1;
}
return a;
}
2. Examples of Recursive and Iterative Algorithms
Below, we present some classical examples of recursive and iterative functions.
2.1. Example 1: Calculation of the PGCD(a,b) by successive subtractions
If a = b, the PGCD is a. Otherwise, we calculate the PGCD of the pair formed by the difference between a
and b, and the smaller of the two.
PGCD(a,b) = PGCD(a-b,b) if a > b
PGCD(a,b) = PGCD(a,b-a) if b > a
PGCD(a,b) = a if a=b
Provide a recursive function and another iterative function to calculate the PGCD between 2 integers passed
as parameters.
Dr N. lachtar 2
National Higher School of Technology and Engineering Annaba
Department of preparatory classes Computer Science 2 Course
First Year 2023/2024
Recursive Function
int pgcd(int a, int b){
if(a == b) return a;
else if(a > b) return pgcd(a-b, b);
else return pgcd(a, b-a);
}
Iterative Function
int pgcd(int a, int b){
while(a != b){
if(a > b) a = a - b;
else b = b - a;
}
return a;
}
2.2. Example 2: Fibonacci Sequence
The Fibonacci sequence (Fn) is defined recursively as follows:
F0 = 0;
F1 = 1
Fn = Fn-1 + Fn-2 for n ≥ 2;
Provide a recursive function and another iterative function to calculate Fn.
Recursive Function
int fibonacci(int n){
if(n == 0) return 0;
else if(n == 1) return 1;
else return fibonacci(n-1) + fibonacci(n-2);
}
Iterative Function
int fibonacci(int n){
int fn1 = 0, fn2 = 1, fn, i;
for(i = 2; i <= n; i++){
fn = fn1 + fn2;
fn1 = fn2;
fn2 = fn;
}
return fn;
}
p
2.3. Example 3: calculaion of combinaisons Cn
𝑝
We want to calculate the combinations of p elements among n, denoted as 𝐶𝑛 . A recursive definition is as follows:
Dr N. lachtar 3
National Higher School of Technology and Engineering Annaba
Department of preparatory classes Computer Science 2 Course
First Year 2023/2024
𝑝 1 𝑖𝑓 𝑝 = 0 𝑜𝑟 𝑝 = 𝑛
𝐶𝑛 = { 𝑝 𝑝−1
𝐶𝑛−1 + 𝐶𝑛−1 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒
p
Provide a recursive function and another iterative one to calculate Cn .
Recursive Function Iterative Function
Recursive Function Iterative Function
int combinaison (int n,int p){ int combinaison (int n,int p, int
C[][]){
if(p==0 || p==n)return 1 ;
int i,j;
else return combinaison(n-1,p)
+combinaison(n-1,p-1); for(i=0;i<=n;i++){
} C[i][0]=1;
C[i][i]=1;
}
for(i=2;i<=n;i++)
for (j=1;j<i;j++)
C[i][j]=C[i-1][j-1]+C[i-1][j];
return C[n][p];
}
In the iterative function, we used a matrix of n rows and n columns to store the calculated temporary values.
For n=5 and p=3, the matrix will be filled as follows:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
Dr N. lachtar 4