Chapter VII RECURSION.pdf algor and data structure

CHAPITER VII: RECURSION Saad Dahlab University - Blida1 Faculty of Sciences Department of Computer Science Computer Science Engineering Semester 2 (1st year) Algorithmic and Data Structures 2 Mrs AROUSSI (s_aroussi@esi.dz) 2024-2025 Available at https://sites.google.com/a/esi.dz/informatiqueblida/algorithmique-et-structure- de-donn%C3%A9es

Definition Evolution of a recursive call Types of recursion divide and rule Design of a recursive algorithm 2 CONTENT

3 An algorithm is said to be recursive when it is self-referring: it refers to itself in its definition. In other words, an algorithm is said to be recursive if it is defined according to itself, directly or indirectly. DEFINITION

4 Example: the factorial n! Itératif n! = 1 * 2 * ... * n Récursif n! = n * (n-1)! Function Facto (n: integer): integer Begin F 1; For i 2 to n do F F*i; return F; End Function Facto (n: integer): integer Begin return n*Facto (n-1); End EXAMPLE

5 The execution of a recursive call passes through two phases, the descent phase and the ascent phase: In the descent phase, each recursive call in turn makes a recursive call. EVOLUTION OF A RECURSIVE CALL Facto(4) 4 * Facto(3) Facto(3) 3 * Facto(2) Facto(2) 2 * Facto(1) Facto(1) 1 * Facto(0) Facto(0) 0 * Facto(-1) Function Facto (n: integer): integer Begin return n*Facto (n-1); End

6 Since a recursive algorithm calls itself, it is imperative that a recursion stop condition is provided, otherwise the program never stops! Example 1: Factorial n! EVOLUTION OF A RECURSIVE CALL STOP CONDITION Previous version Correct version Function Facto (n: integer): integer Begin return n*Facto (n-1); End Function Facto (n: integer): integer Begin if (n<=1) then return 1 else return n*Facto (n-1); End

7 Upon reaching the terminal condition, the ascent phase is started which continues until the initial call is completed, which completes the recursive process. EVOLUTION OF A RECURSIVE CALL 24 1 2 6 Ascent phase Function Facto (n: integer): integer Begin if (n<=1) then return 1 else return n*Facto (n-1); End Facto(4) → 4 * Facto(3) Facto(3) → 3 * Facto(2) Facto(2) → 2 * Facto(1)

8 EXERCISE 1 For each module (below), write the corresponding recursive algorithm: 1. Som (n) calculates the sum of the n natural number. 2. Somme (a, b) calculates the sum of the integers a and b. 3. Prod (a, b) calculates the product of integers a and b. 4. Puiss (a, b) calculates a power b 5. Quotient (a, b) calculates the quotient of a by b. 6. Remainder (a, b) calculates the remainder of division of a by b. 7. PGCD (a, b) calculates the Greatest Common Divisor between a and b 8. Fib (n) calculates the Fibonacci sequence (Un = Un-1 + Un-2 if n > 1, otherwise U0 = U1 = 1)

9 1. The sum of the n natural number. Iterative Som (n) = 0+ 1 + 2 + ... + n Recursive Som (n) = n + Som (n-1) Function Som (n: integer): integer Begin S 0; For i 1 to n do S S+i; return S; End Function Som (n: integer): integer Begin if n = 0 then return (0) else return (Som(n-1) +n) End EXERCISE 1

10 2. The sum of the two integers a and b. 1st solution a+b = a+(b-1)+1 2nd solution a+b = (a-1)+b+1 Function Somme (a, b: integer): integer Begin if b = 0 then return (a) else return (Somme (a, b-1) +1) End Function Somme (a, b: integer): integer Begin if a = 0 then return (b) else return (Somme (a-1, b) +1) End EXERCISE 1

11 3. The product of the two integers a and b. 1st solution a*b = a*(b-1)+a 2st solution a*b = (a-1)*b+b Function Prod (a, b: integer): integer Begin if a = 0 or b = 0 then return (0) else return (Prod(a, b-1) +a) End Function Prod (a, b: integer): integer Begin if a = 0 or b = 0 then return (0) else return (Prod(a-1, b) +b) End EXERCISE 1

12 4. The power ab (a and b two positive integers) iterative ab = a*a*a*......*a, b fois recursive ab = ab-1 * a Function Puiss (a, b: integer): integer Begin P 1; for i 1 to b do P P*a; return P; End Function Puiss (a, b: integer): integer Begin if b = 0 then return (1) else return (Puiss(a, b-1) *a) End EXERCISE 1

13 5. The quotient and the remainder of the division of a by b (a and b two positive integers) Quotient a div b = (a-b) div b+ 1 Remainder a mod b = (a-b) mod b Function Quotient (a, b: integer): integer Begin if a<b then return (0) else return (Quotient(a-b, b) +1) End Function Reste (a, b: integer): integer Begin if a<b then return (a) else return (Reste(a-b, b)) End EXERCISE 1

14 7. Le Greatest Common Divider between a and b (a and b two positive integers) Function PGCD (a, b: integer): integer Begin if a=b then return (a) else if a <b then return (PGCD(a, b-a)) else return (PGCD(a-b, b)) End EXERCISE 1

15 8. Fibonacci sequence. EXERCISE 1 Function Fib (n: integer): integer Begin if n = 0 or n = 1 then return (n) else return (Fib (n-1)+Fib(n-2)) End

16 1. Terminal recursion: a recursive module is said to be terminal if no processing is carried out when a recursive call is raised (except for the return of the module). Remainder of the division a mod b = (a-b) mod b Function Reste (a, b: integer): integer Begin if a<b then return (a) else return (Reste(a-b, b)) End Reste(13,4) Reste(9, 4) Reste (5, 4) Reste (1, 4) 1 TYPES OF RECURSION

17 2. Non-terminal recursion: a recursive module is said to be non-terminal if the result of the recursive call is used to perform processing (in addition to module feedback). Factorial n! = n * (n-1)! Function Facto (n: integer): integer Begin if (n<=1) then return 1 else return n*Facto (n-1); End Fact(4) 4 * Fact(3) 3 * Fact (2) 2 * Fact(1) 1 TYPES OF RECURSION

18 Exercise 1 Algorithm Type Som (n) if n = 0 then return (0) else return (Som(n-1) +n) Not terminal Somme (a,b) if b = 0 then return (a) else return (Somme(a, b-1) +1) Not terminal Prod (a,b) if a = 0 ou b = 0 then return (0) else return (Prod(a, b-1) +a) Not terminal Puiss (a, b) if b = 0 then return (1) else return (Puiss(a, b-1) *a) Not terminal Quotient (a,b) if a<b then return (0) else return (Quotient(a-b, b) +1) Not terminal PCGD (a, b) if a=b then return (a) else if a <b then return (PGCD(a, b-a)) else return (PGCD(a-b, b)) Terminale Fib (n) if n = 0 ou n = 1 then return (n) else return (Fib (n-1)+Fib(n-2)) Not terminal TYPES OF RECURSION

19 3. Simple recursion where the algorithm makes a single recursive call in its body. Example: the factorial function Not terminal recursion Function Facto (n: integer): integer Begin if (n<=1) then return 1 else return n*Facto (n-1); End TYPES OF RECURSION

20 4. Multiple recursion where the algorithm makes multiple recursive calls in its body Example: the calculation of the continuation of the Fibonacci sequence TYPES OF RECURSION Function Fib (n: integer): integer Begin if n = 0 or n = 1 then return (n) else return (Fib (n-1)+Fib(n-2)) End

21 TYPES OF RECURSION Exercise 1 Algorithm Type Som (n) if n = 0 then return (0) else return (Som(n-1) +n) Simple Som (a,b) if b = 0 then return (a) else return (Som(a, b-1) +1) Simple Prod (a,b) if a = 0 ou b = 0 then return (0) else return (Prod(a, b-1) +a) Simple Puiss (a, b) if b = 0 then return (1) else return (Puiss(a, b-1) *a) Simple Quotient (a,b) if a<b then return (0) else return (Quotient(a-b, b) +1) Simple PCGD (a, b) if a=b then return (a) else if a <b then return (PGCD(a, b-a)) else return (PGCD(a-b, b)) Simple

22 5. Cross recursion (or mutual): reflects the fact that two modules call each other. A module M1 calls another module M2 which in turn makes another call to module M1. Example: The definition of the parity of an integer can be written as follows: TYPES OF RECURSION Module M1 () Begin ….; M2(); ….; End Module M2 () Begin ….; …..; M1(); ….; End

23 3. Cross recursion (or mutual): reflects the fact that two modules call each other. A module M1 calls another module M2 which in turn makes another call to module M1. Example: The definition of the parity of an integer can be written as follows: TYPES OF RECURSION Function Pair (n: integer): boolean Begin if (n=0 ) then return true; Else return ImPair (n-1); End Function ImPair (n: integer): boolean Begin if (n=0 ) then return false; Else return Pair (n-1); End

24 4. Nested recursion consists of making a recursive call within another recursive call. Example: The Ackermann function TYPES OF RECURSION Function Ackermann (m, n: integer):integer Begin if (m=0) then return (n+1); else if(n=0) then return Ackermann(m-1,1); else return Ackermann(m-1, Ackermann(m,n-1)); End

25 EXERCISE 2 Exercise 2 (Algorithms on arrays): Let T be an array of integers of real size N. For each module, write the corresponding recursive algorithm and specify the type of recursion used. a. Som b. Prod c. Moy g. RechSeq h. NbOcc i. RechSeqOrd j. EstTrieCroissant k. TriSelection

26 Recursion is a powerful tool for designing (simple) solutions without worrying about internal algorithmic details Divide and conquer paradigm : Specify the solution to the problem based on the solution(s) to a simpler sub-problem (s). How to find the solution of a sub-problem? This is not important because it will be assumed that each recursive call will solve a sub-problem If we manage to find a global solution using these assumptions, then these (assumptions) are necessarily correct, as is the global solution It looks like the "demonstration by recurrence" DIVIDE AND CONQUER PARADIGM

27 Divide rule Combine Global Problem Sub- Problem 1 Sub- Problem 2 Sub- Problem k Break down the problem into k under smaller size problem Sub- Solution 1 Sub- Solution 2 Sub- Solution K Each sub-problem will be solved by the same recursive decomposition ... until trivial sub-problems are obtained GLOBAL SOLUTION Combination of sub-solutions obtained DIVIDE AND CONQUER PARADIGM

28 EXERCISE 2 Exercise 2 (Algorithms on arrays): Let T be an array of integers of real size N. For each module, write the corresponding recursive algorithm and specify the type of recursion used. RechMin ou RechMax RechDicho TriFusion

29 EXERCISE 2: MAXIMUM SEARCH Let Tab be an array with n elements, write a recursive function to search for the index of the maximum in Tab using the divide and conquer paradigm 5 8 1 10 5 8 1 10 5 8 1 10 8 10 10 Divide Rule Combine

30 EXERCISE 2: MAXIMUM SEARCH Function RechMax ( Tab: Array [] of integer, indDeb, indFin:integer) : integer Begin if ( indDeb = indFin) then return (indDeb) else M (indDeb+indFin) div 2 // division du problème en 2 sous-problèmes k1 RechMax(Tab, indDeb, m ) // régner sur le 1er sous-problème k2 RechMax(Tab, m+1, indFin) // régner sur le 2ème sous-problème // Combiner les solutions if (Tab[k1] > Tab[k2]) then return (k1) else return (k2) End

31 EXERCISE 2: DICHOTOMIC SEARCH Let Tab be a sorted table (ascending order) with n elements. The dichotomic search (Binary search) compares the element to be searched x with the element in position m located in the middle of the sub-table (array): if Tab[m] = x: we found the element in position m if Tab[m] > x: it is impossible for x to be after position m in the table. Only the lower half of the table remains to be processed Similarly if Tab[m] < x: only the upper half of the table remains to be processed We continue the search until we find the element or end up on a zero size table, x is not present and the search stops.

32 EXERCISE 2: DICHOTOMIC SEARCH Function RechDicho(Tab :array[] of integer, borneinf, bornesup, x :integer) : boolean if (borneinf<=bornesup) then mil (borneinf+bornesup) DIV 2 ; if (Tab[mil]=x) then return (true) else if (Tab[mil]>x) then return (RechDicho(Tab, borneinf, mil-1, x)) else return(RechDicho(Tab, mil+1, bornesup, x)) else return (False)

33 The principle of merge sort is to sort two tables of size N/2 and then merge them so that the final table is sorted. EXERCISE 2: MERGE SORT PRINCIPLE 7 3 18 13 7 7 3 18 13 7 3 7 18 3 7 7 13 18 7 3 7 3 18 7 3 7 13 13 7

34 DIVISER: Diviser le tableau en deux tableaux: T [debut..fin] = T1[debut..milieu] + T2[milieu+1..fin] REGNER: trier (par fusion) les deux tableaux COMBINER: combiner les 2 tableaux de telle manière que le tableau T reste trie EXERCICE 2 : TRI PAR FUSION PARADIGME DIVISER POUR RÉGNER

35 DIVIDE: divide the array into two tables: T [start..end] = T1[start..middle] + T2[middle+1..end] RULE: sort (by merge) the two arrays COMBINE: combine the 2 arrays in such a way that array T remains sorted EXERCISE 2: MERGE SORTING DIVIDE AND CONQUER

36 Tri_Fusion (T: array [] of integer, debut, fin : integer) Begin if (debut<fin) then Begin milieu (debut + fin) div 2 Tri_Fusion(T, debut, milieu); Tri_fusion (T, milieu + 1, fin); Interclasser (T, debut, milieu, fin) End End EXERCICE 2 : TRI PAR FUSION

37 Procedure Interclasser(Var T: array [] of integer, debut, milieu, fin: entier) Var Tmp: array [fin-debut+1] of integer Begin i 0; i1 debut, i2 milieu + 1; while (i1≤milieu) and (i2 ≤ fin) do if (T[i1]<T[i2]) then Tmp[i] T[i1]; i1++; else Tmp [i] T[i2]; i2++; i++; while (i1<milieu) do Tmp[i] T[i1]; i1++; i++; while (i2<fin) do Tmp[i] T[i2]; i2++; i++; for i debut to fin do T[i]=tmp[i-debut]; // recopier le tableau End EXERCISE 2: MERGE SORTING PROCEDURE « INTERCLASSER »

38 In a recursive module (procedure or function) the parameters must be clearly specified In the body of the module, there must be: one or more special cases: these are simple cases that do not require recursive calls one or more general cases: these are the complex cases that are solved by recursive calls The recursive call of a general case must always lead to one of the particular cases DESIGN OF A RECURSIVE ALGORITHM

CONCLUSION Iterative programs are often more efficient, but recursive programs are easier to write. Compilers know, most of the time, how to recognize terminal recursive calls, and these do not generate additional costs compared to the iterative version of the same program. It is always possible to derecure a recursive algorithm. 39

COURSE SOURCES S. AROUSSI, Cours d’Algorithmique et Structures de données, Université Saad Dahlab de Blida, 2017, Disponible sur https://sites.google.com/a/esi.dz/informatiqueblida/algorithmique- et-structure-de-donn%C3%A9es. H. YKHLEF (2022), Cours d’algorithmique et structures de données dynamique, 2ème année Licence, Département Informatique, Faculté des Sciences, Université Saad Dahlab de Blida (USDB). D. BERRAMDANE (2023), Cours d’algorithmique et structures de données dynamique, 2ème année Licence, Département Informatique, Faculté des Sciences, Université Saad Dahlab de Blida (USDB). Walid-Khaled Hidouci, La récursivité, École nationale Supérieure d’Informatique, pp 107. Disponible sur hidouci.esi.dz/algo/cours_recursivite.pdf La récursivité, Cours d’ Algorithmique et Structures de données dynamiques, École nationale Supérieure d’Informatique, Année Universitaire 2009-2010. 40

Chapter VII RECURSION.pdf algor and data structure

More Related Content

Similar to Chapter VII RECURSION.pdf algor and data structure

Recently uploaded

Chapter VII RECURSION.pdf algor and data structure