USTHB - Faculty of Computer Science - Department of Computer Science – A.

LAACHEMI (1)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Chapter 6 :
Recursion

A Russian doll is a doll with a Russian doll inside.

 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (2)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Recursion:

1) Definitions.
2) How to write a recursive algorithm.
3) General scheme of recursive actions.
4) Direct and indirect recursion.
5) How it works ?
6) Types of recursion.
7) Recursion and complexity.
8) How to eliminate recursion ?
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (3)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Definition:

👉 Recursion is a fundamental concept in computer science

and mathematics that replaces loops by action calls. An
action calls itself directly or indirectly to solve a problem.

👉 This technique is used to break down complex problems

into simpler sub-problems, each of which can be solved in
the same way.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (4)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Definition:

👉 Recursion is a simple and elegant way to solve certain

problems.

👉 Definition: A function or procedure that calls itself is

called recursive.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (5)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Definition:

👉 A parametrized action P is recursive if its execution

implies one or more calls to P. these calls are considered
recursive.

👉 An algorithm that contains at least one recursive

parametrized action is recursive.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (6)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Concept of recursion:
👉 Recursive programming consists of having one or more
recursive functions in a program.

What is a recursive function?

👉 A recursive function is a function that defines itself in

terms of itself; that is to say, in a recursive function, there
will be a call to the same function.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (7)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

What is a recursive function?

Definition of function A:

A(...) {
...
...
A(...); //Call to A
}

👉 The recursive function contains in its body one or more

calls to itself, possibly with definable arguments.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (8)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

What is a recursive function?

Example:
Basically, a function that calls itself directly or indirectly.
Let’s take a look at this example :
Equation:

f(x) = f(x-1) + 1

f(0)=1
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (9)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

What is a recursive function?

Example:
Consider the factorial function; if we write the factorial
code of X, we have a choice between two definitions.

👉 Repetitive definition: Fact(X)=1*2*3*...*(X-1)*X, we use

a loop.

👉 Recursive definition: Fact(X)=X*Fact(X-1), we use a

recursive function.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (10)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

What is a recursive function?

Recursive programming is not always interesting, but it
allows me to program in a more elegant and often simpler
way.

In pseudocode (algorithmic):
Function Factorial(x : integer) : integer
Begin
If x = 0 then
return 1
Else
return x * Factorial(x - 1)
EndIf
End
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (11)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Advantages of recursion (1):

👉 Simplicity and readability of code : with recursive

programming, the code is simpler and more readable,
particularly for problems that may be solved by naturally
de composing them into similar problems.

👉 Ease of implementation for certain tasks: some

algorithms, such as quicksort or tree traversal, can be more
easily implemented recursively.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (12)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Advantages of recursion (2):

👉Natural handling of recursive data structures: Recursive

programming can be well suited to handling recursive data
structures, such as trees or linked lists.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (13)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Principle of constructing a recursive function:

👉 The number of recursive calls must be finite; that is,
there must be a stopping condition. If this condition is met,
the function must compute itself directly without making
another call.

𝑋 ∗ 𝐹𝑎𝑐𝑡 𝑋 − 1 𝑖𝑓 𝑋 ≥ 1
Fact(X) = ቊ
1 𝑖𝑓 𝑋 = 0 (𝑇ℎ𝑒 𝑠𝑡𝑜𝑝𝑝𝑖𝑛𝑔 𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛)

In pseudocode (algorithmic):
Function Factorial(x : integer) : integer //long
Begin
If x = 0 then return 1
Else return x * Factorial(x - 1)
EndIf
End
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (14)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Principle of constructing a recursive function:

Stopping Condition:
👉 Since a recursive function calls itself, it is imperative to
include a stopping condition for the recursion; otherwise,
the program will never terminate!

👉 The stopping condition must always be tested first, and

then, if the condition is not met, initiate a recursive call.

𝑋 ∗ 𝑋 − 1 ! 𝑖𝑓 𝑿 ≥ 𝟏
Fact(X) = ቊ
1 𝑖𝑓 𝑿 = 𝟎 (𝑇ℎ𝑒 𝑠𝑡𝑜𝑝𝑝𝑖𝑛𝑔 𝑐𝑜𝑛𝑑𝑖𝑡𝑖𝑜𝑛)
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (15)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Principle of constructing a recursive function:

Stopping Condition: Fact(X) = X*(X-1)!

Without the stopping

condition in the recursion,
the program never stops!
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (16)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Principle of constructing a recursive function:

Example:

Calculate the factorial of a number n (n≥0) :

0!=1 ; 1!=1 ; 2!=1*2 ; 3!=1*2*3 ; 4!=1*2*3*4 ; 5!=1*2*3*4*5
0!=1 ; 1!= 0!*1 ; 2!=1!*2 ; 3!= 2!*3 ; 4!=3!*4 ; 5!=4!*5
When n>0 we obtain : n! = (n-1)!*n

The calculation of the factorial value of a number is defined

by :

If n=0 then n! = 1
If n>0 then n! = n*(n-1)!
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (17)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Principle of constructing a recursive function:

Remark !

👉 The variable n is tested each time to determine whether

recursive calls should be stopped or not.

n is called the control variable.

👉 When n=0, the value of n ! is given directly.

0 is called the base value.

 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (18)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Principle of constructing a recursive function:

Example in C language: Factorial(X).

unsigned int fact(unsigned int X) {

if (X == 0)
return 1;
else
return X*fact(X-1);
}
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (19)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Principle of constructing a recursive function:

Example in C language: Factorial(X).
Appel à fact(4)
. 4*fact(3) = ?
. Appel à fact(3)
. . 3*fact(2) = ?
. . Appel à fact(2)
. . . 2*fact(1) = ?
. . . Appel à fact(1)
. . . . 1*fact(0) = ?
. . . . Appel à fact(0)
. . . . Retour de la valeur 1
. . . . 1*1
. . . Retour de la valeur 1
. . . 2*1
. . Retour de la valeur 2
. . 3*2
. Retour de la valeur 6
. 4*6
Retour de la valeur 24
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (20)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Principle of constructing a recursive function:

Concept of an execution stack:
Definition (Call Stack):
👉 The call stack of the current program is a memory
location used to store parameters, local variables, and the
return address of each function being executed.

👉 The call chain must terminate, meaning it must lead to

the base case.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (21)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Principle of constructing a recursive function:

Concept of an execution stack:
Definition (Call Stack):

👉 The call stack operates according to the LIFO principle:

Last-In-First-Out.

👉 Remark ! The stack has a fixed size; improper use of

recursion can lead to a stack overflow.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (22)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Principle of constructing a recursive function (1):

Concept of an execution stack:
Remark:
👉 In order to ensure the execution of nested function calls,
including recursive calls, the system uses a stack.

👉 Each time a new function is called, memory space is

pushed onto the stack.
All local objects within the function—parameters and
variables of the calling function, plus parameters and
variables of a function that must be used to populate the
return address, that is, the address of the instruction from
which execution of the interrupted function should resume.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (23)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Principle of constructing a recursive function (2):

Concept of an execution stack:
👉 A recursive function can be called a large number of
times; the essential point is that at a given call the
recursion stops (there are no more calls to the function) by a
stopping condition or the function is calculated directly.

👉 The function parameters are always passed by value, so

with each call to a recursive function, memory areas are
again allocated for these parameters.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (24)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Principle of constructing a recursive function (2):

Concept of an execution stack:
👉 With each new function call, the machine pushes the
following onto a system stack:

→ The parameters of the calling function.

→ Its local objects.
→ The return address, that is, the address of the
instruction that must be executed upon returning to
the calling function.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (25)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Principle of constructing a recursive function (2):

Remark:
👉 Recursion is useful because it allows for simpler
programming, but it is costly in terms of memory space and
execution time.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (26)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Direct and indirect recursion:

Direct recursion:
👉 When a subroutine calls itself, as in the case of the
factorial, this is called direct recursion.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (27)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Direct and indirect recursion:

Indirect recursion (1):
👉 We speak of indirect recursion when a function f() calls
another function A() and the latter calls the function f().

👉 Sometimes, it's possible for a subroutine A to call a

subroutine B, which itself calls subroutine A.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (28)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Direct and indirect recursion:

Indirect recursion (2):
👉 So the call originating from A returns to A after passing
through B. This is called indirect recursion (in fact, the
sequence of calls starting from A can pass through several
other subroutines before returning to A!).
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (29)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Direct and indirect recursion:

Indirect recursion (3):
Example:
👉 A simple example of indirect recursion is the recursive
definition of even and odd numbers. A positive number n is
even if n-1 is odd; a positive number n is odd if n-1 is even.
The stopping conditions are given by the values n=0, which
is even, and n=1, which is odd.

Principle:
even(n) returns true if n is even.
odd(n) returns true if n is odd.
Each function calls the other with n-1.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (30)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Direct and indirect recursion:

Indirect recursion (4):
Example:
Function even(n : Integer) : Boolean Function odd(n : Integer) : Boolean
If n = 0 Then If n = 0 Then
Return true Return false
End If End If
Return odd(n - 1) Return even(n - 1)
End Function End Function

even(4) → odd(3) → even(2) → odd(1) → even(0) → True

odd(5) → even(4) → … → True
Indirect recursion is produced by the even and odd
functions: even calls odd and odd in turn calls even.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (31)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Direct and indirect recursion:

Indirect recursion:
Example 2:
Another example, which combines both types of recursion,
is presented below:
Calculate the sequences of values given by the following
relationships:
x0 = 1; xn = 2*yn-1 + xn-1
y0 = -1 ; yn = 2*xn-1 + yn-1
The recursive functions that calculate the values of the
sequences x and y are shown below. Each function contains both
direct recursion (x calls x and y calls y) and indirect recursion (x
calls y, which calls x, and so on). The example does not handle
situations involving incorrect parameter values (i.e., n < 0).
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (32)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Direct and indirect recursion:

Indirect recursion:
Example 2:

x0 = 1; xn = 2*yn-1 + xn-1
y0 = -1; yn = 2*xn-1 + yn-1
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (33)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Evaluating a Recursive Call:

How is it possible to call a subroutine while it is already
executing?
How is it that the data handled by these different calls to
the same subroutine doesn't get mixed up?

To answer these questions, we must first understand the

memory model in Java subroutine execution.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (34)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Evaluating a Recursive Call:

1) Memory model:
Each Java subroutine (including the main program "main")
uses a memory area to store its parameters and local
variables.

Additionally, a function also reserves space in its memory

area for its returned result.
Consider the following function as an example:
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (35)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Evaluating a Recursive Call:

1) Memory model:

FIGURE – Memory area occupied by the example function.

 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (36)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Evaluating a Recursive Call:

1) Memory model:
The allocation of this memory area occurs when the
subroutine is called, in a special memory area of the
program called the stack.

Subroutine memory areas are pushed onto the stack in the

order they are called and popped from the stack as soon as
the subroutine finishes.

Therefore, a subroutine's memory area only physically

exists while the subroutine is running.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (37)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Evaluating a Recursive Call:

1) Memory model:
Suppose that the main program that calls the example
function has the following form:

FIGURE – The stack during the function call example.

 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (38)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Evaluating a Recursive Call:

1) Memory model:
👉 Before the call, as well as after the execution of the
example function, the stack contains only the memory
space of ’main’.

👉 The space freed up by ‘example’ will be occupied by a

possible subsequent call to another subroutine (perhaps
even ‘example’, if it is called multiple times by ‘main’!).
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (39)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Evaluating a Recursive Call:

1) Memory model:
Note:
👉 There is a clear separation between the local variables
of the different subroutines, as they occupy distinct memory
areas (e.g., the variables x, y, and c).

Conclusion:
👉 The stack contains, at any given time, the memory
areas of the chain of subroutines currently being executed,
starting from the main program.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (40)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Evaluating a Recursive Call:

2) Recursive Call Flow:
👉 In recursive programs, the call stack is filled by calls to
the same subroutine (which calls itself).

👉 Consider the calculation of factorial(2): the main

program calls factorial(2), which calls factorial(1), which
calls factorial(0), which can calculate its return value
without any further recursive calls.

👉 The value returned by factorial(0) allows factorial(1) to

calculate its result, which in turn allows factorial(2) to
calculate its own and return it to the main program.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (41)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Evaluating a Recursive Call:

2) Recursive Call Flow:
👉 FIGURE – The sequence of calls and calculations is
illustrated in the following figure:

FIGURE – Chain of recursive calls for factorial(2).

Each instance of factorial retrieves the result of the next
recursive call into the variable sub_result, allowing it to
calculate result and return it to its caller.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (42)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

How to design a recursive subroutine?

Writing recursive programs generally involves the following
steps:
1. Find a recursive decomposition of the problem
→ (a) Find the element of recursion that defines the simpler
cases (e.g., a decreasing numerical value, a decreasing
data size).
→ (b) Express the solution in the general case in terms of
the solution for the simpler case.
2. Find the stopping condition for the recursion and the
solution in this case:
→ Verify that the stopping condition is reached after a finite
number of recursive calls in all cases.
3. Combine the two previous steps into a single program.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (43)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Different Types of Recursion:

1) Multiple Recursion:
An action can execute multiple recursive calls. Typically
two, and sometimes more.
Example:
Procedure DisplayRec(I/n: integer, I/i: integer); //1st call i=1 Begin
if (i<=n) then
write(i); DisplayRec(n, i+1);
write(" ;"); DisplayRec(n, i+1);
write(i);
endif;
End;

After executing AfficheRec(3,1), the result will be:

123;3;3;32;23;3;3;321
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (44)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Different Types of Recursion:

2) Tail Recursion:
If the execution of a recursive call is never followed by the
execution of another instruction, this call is said to be right-
recursive, also known as tail recursion. In tail recursion,
recursive calls do not need to be pushed onto the execution
stack because the next call simply replaces the previous call
in the execution context.
Example:
Procedure DisplayRecT(I/n: integer, I/i: integer); // First call i=1
Begin
if (i<=n) then write(i); DisplayRecT(n, i+1);
endif;
End; // DisplayRecT is a tail-recursive function.
After executing displayRecT(3, 1) the result will be 1 2 3.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (45)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Different Types of Recursion:

3) Non-Terminal Recursion:
A recursive action is said to be non-terminal if the result of
the recursive call is used to perform some processing (in
addition to returning a value). A non-terminal recursive
action requires a stack.
Example:
Procedure DisplayRecNT(I/n: integer, I/i: integer); // 1st call i=1
Begin
if (i<=n) then
DisplayRecNT(n, i+1);
write(i);
endif;
End; // displayRecNT is a non-terminal recursive function
After executing afficheRecNT(3, 1) the result will be 3 2 1.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (46)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Different Types of Recursion:

4) Nested Recursion:
This involves making a recursive call inside another
recursive call.

Example:
The Ackermann sequence:
→ is a sequence defined by the Ackermann function,
→ serves as an example of extreme growth,
→ It grows faster than any of the classical functions used in
algorithms.
→ is fundamental in computability theory and algorithmic
analysis.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (47)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Different Types of Recursion:

4) Nested Recursion:
Example: The Ackermann sequence:
The Ackermann function 𝐴(𝑚,𝑛) is defined as follows:

→ It is a doubly recursive function, which explains its

explosive growth.
Examples : A(1,3)=5, A(2,4)=11, A(3,3)=26−3=61
A(4,1)=65533.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (48)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Principle of constructing a recursive function:

To write a recursive function, you must:

👉 Find a recursive definition.

👉 Never forget to find the trivial case (that is, the stopping
condition).
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (49)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Principle of constructing a recursive function:

In summary, a recursive function must include:

👉 A general case in which one or more further calls to the

function itself are made.

👉 With each recursive call, the value of at least one of the

function's parameters must change.

👉 A stopping condition or base case in which no further

calls are made, and which triggers the upward flow of
results to higher levels of the recursion.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (50)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Principle of constructing a recursive function:

👉 This case corresponds to the function's result when it is

simple to calculate: the value returned by the function is
then directly defined.

👉 The call chain must terminate, meaning it must lead to

the base case.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (51)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Terminal recursion:
In other words:
👉 A function is tail recursive if nothing is executed after
the recursive call.
Example: multiple38 (k*38) : 38×1=38 38×2=76 38×3=114
38×4=152 38×5=190
Function multiple38(n : integer) : boolean
If n = 38 then return True
EndIf
If n < 38 then return False
EndIf
// Appel récursif
return (multiple38(n - 38)
EndFunction
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (52)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

How to write a recursive algorithm :

👉 First, Determine the particular case or cases (base cases
or trivial cases) which are executed directly without
recursive calls. In these cases, the command variables are
equal to the base values.

👉 Then, depending on the type of operation done,

construct your parametrized action as follows :
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (53)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

How to write a recursive algorithm :

Example: A sum (+)
Function Fct (…) : typeElement
.
.
.
Begin
if (a command variable = a base value) then
return a constant; // often 0
else
return a constant + Fct(command variable and
others)
endIf;
End;
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (54)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

How to write a recursive algorithm :

Example: A product (*)
Function Fct (…) : typeElement
.
.
.
Begin
if (a command variable = a base value) then
return a constant; // often 1
else
return a constant * Fct(command variable and
others)
endIf;
End;
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (55)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

How to write a recursive algorithm :

Example: A Boolean
Function Fct (…) : typeElement
. . .
Begin
if(a command variable = a base value) then
return True;
else
if(a command variable = a base value) then
return False;
else
return Fct(command variable and others)
endIf;
endIf;
End;
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (56)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

How to write a recursive algorithm :

Example: Displaying in sequence (from the first to the last)
Procedure Proc (…) .
.
.
Begin
Display(…);
Proc(a command variable);

End;
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (57)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

How to write a recursive algorithm :

Example: Displaying in reverse (from the last to the first).
Procedure Proc (…) .
.
.
Begin
Proc(a command variable);
Display(…);

End;
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (58)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

How recursion works ?

👉 A program can only be executed if it is loaded into main

memory. Each instruction in the program is located at a
given address in memory.

👉 When a program calls a function, the system saves the

return address (address of the instruction that follows the
call), as well as the values of local variables.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (59)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

How recursion works ?

👉 When a function f calls a function g, the return address

of f (parameters and local variables) must be saved before g
is called, and this context must be recovered after g returns.

👉 If there are several nested calls, the system manages a

stack to save the different contexts of the different
recursive calls.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (60)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

How recursion works ?

👉 The parameters of the recursive call change. At each

call, the local variables are stored in a stack. The
parameters and local variables are then popped as we move
up the levels.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (61)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

How recursion works ?

On the 𝑖 𝑡ℎ call, the system pushes in a stack:

1. Parameter values at level i.

2. The values of local variables at level i.
3. The return address at level i.

At the end of the recursive calls, level i+1 returns to level i :

1. Return to main program if stack is empty.

2. Pop return address.
3. Pop the level i context (the values of level i variables).
4. Execute the instruction following the last call.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (62)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Recursion and complexity Function Fib (I/ n :integer) :

👉 Fibonnaci example : integer
𝐹0 = 0, Begin
if (n=0) then return 0 ;
𝐹1 = 1 else
𝐹𝑛 = 𝐹 𝑛−1 + 𝐹 𝑛−2 𝑛 ≥ 2. if (n=1) then return 1 ;
else
return (Fib(n-1)+Fib(n-2));
The corresponding endIf;
Recursive function is : endIf;
end;
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (63)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Recursion and complexity

Fibonnaci example : Executing this recursive function for n=4
gives us the following tree:

𝑛
O(2 )
For n=5; Fib(5)=5 (15 calls to arrive at the result). The successive
values of this sequence : 0, 1, 1, 2, 3, 5, 8, 12, 21, 34, 55,…
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (64)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Recursion and complexity Fibonnaci example

Function Fib (I/ n : integer) x←0 ;
: integer ; y ← 1 ;
Var z ← 1 ;
x, y, z, i : integer ; /* x=Fib(0) and y=
Begin Fib(1) */
If (n=0) then for i ← 2 to n Do
return 0 ; z ← x+y ;
endIf; x ← y ;
If (n=1) then y ← z ;
return 1 ; endFor;
endIf; return z ;
end;

When n=4 : x=0 y=1 i=2 : z=1 x=1 y=1 i=3 : z=2 x=1 y=2 i=4 : z=3
x=2 y=3 Result z=3 with 3 iterations.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (65)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Recursion and complexity

Fibonnaci example

👉 The problem lies in the number of calls to the function.

We can see that for the recursive solution, the number of
calls is exponential (a bad solution that is very costly in
terms of complexity), whereas the iterative solution only
costs n calls.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (66)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Eliminating Terminal Recursion

👉 In order to eliminate terminal recursion, the recursive
call must be replaced by a while loop.

First case:
f(x) /* Recursive*/ f(x) /* Itrerative*/
Begin Begin
if (condition(x)) then While (condition(x)) do
A; A;
f(g(x)); x ← g(x);
endIf ; endWhile ;
End ; End;
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (67)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Eliminating Terminal Recursion

Second case:
f(x) /* Recursive*/ f(x) /* Itrerative*/
Begin Begin
if(condition(x)) While (condition(x))
then Do
A ; A ;
f(g(x)); x←g(x) ;
else endWhile;
B; B;
endIf ; End;
End ;
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (68)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Example : Palindrome Function

Function Palindrome_R (I/word: Function Palindrome_I (I/word: String,
String, I/beg :integer, I/end : I/beg :integer, I/end : integer) :
integer) : boolean boolean
Begin Begin
if((beg<end) and (word[beg]=
While((beg<end)and(word[beg]=
word[end]))
word[end])) do
then
return Palindrome_R(word, beg ← beg+1:
beg+1,end-1); end ← end-1;
else endWhile;
if (beg>=end)then if (beg>=end)then
return TRUE; return TRUE;
else else
return FALSE; return FALSE;
endIf; endIf;
endIf;
End;
End;
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (69)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Eliminating Non Terminal Recursion

A single recursive call:

👉 To eliminate recursion, you need to save the context of
the recursive call.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (70)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Eliminating Non Terminal Recursion

First case f(x) /* Itrerative */

f(x) /* Recursive */ Begin
Begin Stack s←initStack();
if (condition(x)) then while (condition(x)) do
A ; A ;
f(g(x)); push (p, x);
endIf ; //a stack is x←g(x) ;
necessary endWhile;
B ; B;
end; While (non emptyStack(p)) do
pop (p, x) ;
B ;
endWhile;
end;
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (71)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Eliminating Non Terminal Recursion

Second case f(x) /* Itrerative */
f(x) /* recursive */ Begin
begin Stack s←initStack();
if (condition(x)) then while (condition(x)) do
A1; A1 ;
f(g(x)); push(p, x);
A2; x ← g(x) ;
else endWhile;
B; B;
endIf; while (non emptyStack(p)) do
end; pop (p, x);
A2;
endWhile;
end;
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (72)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Example : display a number digit by digit Recursively

Procedure DisplayNumber_Recursive (I/ n : integer)

Begin
if (n>0) then
DisplayNumber_Recursive (n/10) ;
endIf;
write(n%10) ;
End;
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (73)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Example : display a number digit by digit Iteratively

Procedure DisplayNumber_It (I/ n : integer)
variable
s : Stack ;
Begin
s ← initStack() ;
while (n>0) do
push(p,n) ;
n ← n/10 ;
endWhile;
while (non emptyStack(p))Do
pop(p,n)
write(n%10) ;
endWhile;
End;
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (74)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Eliminating Non Terminal Recursion:

Two recursive calls:
The second call is terminal (we’ll just replace it with a loop)
f(x) /* recursive*/
Begin Begin
If (condition(x)) then While (condition(x)) do
A ; A ;
f(g(x)); f(g(x)) ;
f(h(x)) ; x←h(x) ;
endIf; endWhile ;
End; End;

We first apply the

rule of terminal
recursion for the
second call :
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (75)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Eliminating Non Terminal Recursion:

f(x) /* iterative */
Begin
Stack s←initStack();
While (condition(x) or non emptyStack(p)) Do
While (condition(x)) Do
A ;
push (p, x);
x←g(x) ;
endWhile ;
pop(p, x) ;
x←h(x) ;
endWhile;
End;
Then, we apply
what we’ve seen
for the first call.
 USTHB - Faculty of Computer Science - Department of Computer Science – [Link] (76)
Module: Algorithms and Data Structures 3, 2nd Year ING INFO, Section: A, 2025/2026.

Chapter 6 Recursion

Conclusion:

👉 As you can see, eliminating recursion is sometimes very

easy—it's as simple as writing a loop, as long as you're
careful about how you run it. But sometimes it's extremely
difficult.