Recursive Algorithms Explained
Translated by
ScribdTranslationsRecursive Algorithms Explained
Translated by
ScribdTranslationsChapter 6: Recursive algorithms
1. Introduction
An algorithm or a process is said to be recurrent if it uses an iterative or recursive method to
give a result that can derive from other previous results.
We then speak of a recurring algorithm (or process) of order is an algorithm
giving a result that depends on previous results.
2. Examples
2.1. Sum calculation
Activity:
Give the algorithm of a function that calculates the sum of the elements of a square matrix M.
of dimension (knowing that the matrix is already filled).
Solution :
FunctionSum (n : integer, M : type) : real
Start
S 0
For i from 0 to n-1 do
For j from 0 to n-1 do
S S+M[i,j]
End for
Return(S)
End
T.D.O.L
Subject T/N
i, j Whole
S Real
Observation:
In the expressionS S+M[i,j], we note that the calculation of S always refers to
the previous element, so it is a first-order recurrent process.
DZIRI Jalel
2. Recurrent algorithm on strings
Activity: Case of the Thue-Morse sequence
It is a binary sequence defined by: U0 = "0" (or "1") and by the following recurrence:
To go from Unat Un+1 we replace each "0" with Un by replacing "01" with "1" and each "1" with "10".
Example:
U0 = « 1 »
U1 = « 10 »
U2 = "1001"
U3 = « 10010110 »
…..
Propose an algorithm for a function to calculate Nthterm of the Thue sequence
Morse from a given character A ("0" or "1").
Thue_MorseFunction (n : integer, A : character) : string
Beginning
CH A
For i from 1 to n do
j←0
Repeat
If CH[j] = "0" Then
Insert ("1", CH, j+1)
Otherwise
Insert ("0", CH, j+1)
End If
L ← Long (CH)
j←j+2
Until j >= L
End For
Return (CH)
End
T.D.O.L
Object T/N
i, j, L Whole
CH chain
DZIRI Jalel
Observation:
The first result depends on the first value of the character ('0' or '1'), a second
result is obtained from the previous one found, and so on. We conclude that it is a
recurring sequence of order 1.
2. 3. Pascal's Triangle
Activity:
The Pascal's triangle is the matrix of coefficients used to expand
expressions like (a+b)0(a+b)1(a+b)n
Example:
(a+b)0=1
(a+b)1=1*a + 1*b
(a+b)2=1*a2+2*a*b +1*b2
(a+b)3=1*a3+3*a2*b+3*a*b2+1*b3
(a+b)4=1*a4+4*a3*b + 6*a2*b2+4*a*b3+1*b4
1
11
121
13 31
1 464 1
……
It is observed that Pascal's triangle is the lower part of a square matrix of dimension
n. The calculation of the elements of the matrix is done as follows:
MAT [4,2] refers to two previous results: MAT [3,1] and MAT [3,2].
In general: Pascal's triangle is obtained as follows:
. The cell [0,0] must contain the value 1.
. The first element and the last element (of each line) are equal to 1.
. The other elements are determined by applying the following formula: MAT[i,j] =
MAT[i-1,j] + MAT[i-1,j-1].
So it is a recurrent treatment of order 2.
We propose to write a procedure that allows us to create Pascal's triangle in a
matrix M.
DZIRI Jalel
Solution 1 :
Procedure Fill_Pascal_Triangle (N: Integer; @ M: ta)
Start
M [0,0] ← 1
M [1,0] ← 1
M [1,1] ← 1
For i from 2 to N Do
M [i, 0] ← 1
M[i, i] ← 1
For j from 1 to i-1 Do
M [i, j] ← M [i-1, j] + M [i-1, j-1]
End For
End For
End
T.D.O.L
Subject T/N
i, j Whole
Solution 2: recursive version
Procedure Fill_Pascal_Triangle (N: Integer; @ M: table)
Beginning
For i from 0 to N-1 Do
For j from 0 to i Do
M [i, j] ← val_triangle (i, j)
End For
End For
End
DZIRI Jalel
FunctionVal_triangle (x, y : Integer) : Integer
Start
If (x = 0) OR (y = x) Then
Val_triangle ← 1
Otherwise
Val_Triangle ← Val_Triangle (x-1, y) + Val_Triangle (x - 1, y - 1)
Finsi
End
2. 4. Fibonacci Sequence
Leonardo of Pisa, known as Fibonacci, studied the reproduction of rabbits (from the point
from a digital perspective). He noticed that a couple of young rabbits take a season to become
Adult, waits for another season then gives birth to a pair of young rabbits each season.
next. He concluded that the reproduction of rabbits can be represented by the following sequence:
U0 1
U1= 1
Un= Un-1 + Un-2
For a given natural integer N, provide the algorithm of the function that calculates [Link] of
the Fibonacci sequence:
. Through an iterative process using an array.
. By an iterative process not using an array.
. Using a recursive process.
Derive the recurrence relation of the Fibonacci sequence.
DZIRI Jalel
Solution 1: Iterative solution without using an array
FunctionFIBO_IT1 (N : Integer) : Integer
Beginning
u1 ← 1, u2 ← 1
If sin ≤ 2 Then
F← 1
Otherwise
For i from 3 to N Do
F ← u1 + u2
u1 ← u2
u2 ← F
End For
End Yes
Return (F)
End
T.D.O.L
Subject T/N
i, u1, u2, F Whole
2. 5. The golden number
The golden ratio is the positive solution of the equation: x2 - x - 1 = 0. That is to say, the number
1 +√5
This number is denoted by λ.
2
By calculating the elements of the sequence Vn = Fib(n+1) / Fib(n), we can observe that
this sequence converges to the golden number whose approximate value is 1.618.
Let two sequences U and V be defined from:
U1equals 1
U2= 2
Un = Un-1 + Un-2 for n≥ 3
Vn = Un / Un-1 for n ≥ 2
DZIRI Jalel
The V suitentends towards a limit called the golden ratio. It is assumed that the nth term of the sequence
V is Vn, therefore an approximate number of the golden ratio with a precision e as soon as |Vn- Vn-1|<
e.
Write an algorithm named Number_Gold, which looks for Vnto 10-4near and its rank.
Iterative solution with table:
Algorithm display number gold
Start
Init (U)
Calculation (U, V, i)
Show (V, i)
End
T.D.N.T
Types
array of 1000 integers
tb = table of 1000 real
T.D.O.G
Object T/N
U ta
V tb
i Whole
Init Procedure
Calculate Procedure
Poster Procedure
InitProcedure(@U : ta)
Start
U[0] 1
U[1] 1
i 1
End
DZIRI Jalel
Procedure Calculation (@U : ta, @V : tb, @i : integer)
Start
Repeat
i i+1
U[i] U[i-1]+U[i-2]
V[i] U[i]/U[i-1]
Until abs(V[i]-V[i-1]) <0.0001
End
Display Procedure (V: tb; i: integer)
Beginning
Write ('the golden number is: ', V[i])
Write(" the rank is:", i)
End
DZIRI Jalel