University – BLIDA1
Department: Mathematics
Algorithms and Data Structures
Recursion
LAOUICI.Z
1
Recursion
How many people are in front of
me?
Sir, which number are you?
number 1 + 7 number 1 + 1
number 1
Recursion
1. Define a base case: When would the process end?
<The stopping condition >
2. Define a recursive case: What is the basic task I can
do?
<break down this problem into sub-problems>
Recursion : ……….
Function GetPosition (personN:Person ) : int;
Begin
if( [Link]=null) then
Return 1;
else
Return (1+ GetPosition([Link]));
Endif
End
4
Recursion
Definition
Recursion is the process in which a function calls itself directly or
indirectly
A Mathematical Interpretation: the sum of first n natural numbers
approach(1) – Simply adding one by one
f(n) = 1 + 2 + 3 +……..+ n
approach(2) – Recursive adding
f(n) = 1 n=1
f(n) = n + f(n-1) n>1
5
Recursion : Execution trace
(progression) .
Example
1. Write a recursive function Fact(n) to calculate the factorial of a natural
number n.
2. Provide the execution trace (sequence of recursive calls) for n=4.
Slide /6
Recursion : Execution trace
(progression)
Example 1 <
Function Fact(n: int):int;
Variable i, f : int;
Factorial>
Begin
if (n <=1)then Return (1);
else
Return (n * Fact(n-1)) ;
Endif ;
End
0! = 1! = 1 {base case}
n! = n*(n-1)*…*1 = n * (n-1)!
7
Recursion : Execution trace
(progression) Example <
Fact(4) Descent Factorial>
Function Fact(n: int):int;
Variable i, f : int;
phase Begin
24 if (n <=1)then Return (1);
4 * Fact(3) else
Return (n * Fact(n-1)) ;
Endif ;
6 End
3 * Fact(2)
2
2 * Fact(1)
1
8
Recursion : Execution trace
(progression) .
Example 2
1. Write a program and recurrence relation to find the Fibonacci series of n
where n>2 .
2. Provide the execution trace (sequence of recursive calls) for n=4.
Mathematical Equation:
if n == 0, n == 1;
fib(n) = fib(n-1) + fib(n-2) otherwise;
Recurrence Relation:
T(n) = T(n-1) + T(n-2)
Slide /9
Recursion : Execution trace
(progression)
Example <
Fibonacci>
Fib(4) 3
Function Fib(n: int):int;
Variable i, f : int;
2 Fib(3) + Fib(2)
Begin 1
if (n =0)then Return (0);
1 Fib(2) + Fib(1) 1 else
Fib(1)+ Fib(0)
if (n =1)then Return (1);
1else 0
Fib(1)+ Fib(0) Return (Fib(n-1)+ Fib(n-
2));
1 0 Endif ;
Endif ;
End;
Recursion : Exercises
Exercise
1. Write a recursive function that calculates the sum of two natural numbers, a and b.
a + b
5 + 4 5 +(1+1+1+1) if(b=0) => Sum = a +0 =a => 5
else add 1, b times
Sum2Nbr(5, 4) 4
9=1+8( 1 + Sum2Nbr(5, 3))
Function Sum2Nbr (a: int, b: int ):int ;
8=1+7( 1 + Begin 2))
Sum2Nbr(5,
if(b=0) then Return(a) ;
7=1+6( 1 + Sum2Nbr(5, 1))
else
Return( 1 + Sum2Nbr
( 1 +
(a, b-1))
Sum2Nbr(5, 0))
;
6=1+5
Slide /11
endif ;
End (b=0) => Sum = 5
Exercice Recursion : Exercises
2. Write a recursive function that calculates 'a' raised to the power of 'b' (where 'a' is a real number and 'b' is a
natural number)
𝒃
𝒂𝟒 5*5*5*5
4 if(b=0) => Power =1
𝟓 5*5*5*5
else multiply * 5, b times
Power(5, 4) 3
625 5*5*5
2
625=5*125( 5 * Power(5, 3))
Function Power(a: 5*5 real, b: int ):real ;
1
125=5*25(Begin
5 * Power(5, 2))
if(b=0) alors Return(1) ;
else ( 5 * Power(5, 1))
25=5*5
Return ( a * Power (a, b-1)) ;
5=1*5 ( 5 * Power(5, 0))
Slide /12
Endif ;
End (b=0) => power = 1
Recursion : Exercises
Exercise
Let T be an array of integers of size n (n ≤ 100). Write recursive functions to perform the
following operations:
1. Prod: which returns the product of the elements of array T.
13
Prod: which returns the product of the
elements of array T. T 5 2 3 1 n
Prod (T ,n) prod =30
=
Product of subarray T[n-1]= T[3]= 1
(T ,size n-1)
Prod (T ,n-1) =
*
Product of subarray
(T ,size n-2)
Prod (T ,n-2) = T[n-1]= T[2]= 3
Product of subarray *
(T ,size n-3) Prod (T ,n-3) = T[n-1]= T[1]= 2
Product of subarray *
T[n-1]= T[0]= 5
(T ,size n-4 = 4-4=0)
If there are no elements in the vector
Prod (T ,n-4) Prod (T ,0)=1
* n=0<nbr of element =0> => prod =1
14
Recursion : Exercises
Function Prod(T:array[50] int,n: int):int ;
Begin Number of elements
if(n=0) alors Return (1) ;
else
Return (T[n-1] * Prod(T,n-1)) ;
Endif ; index Size of vector
End
15
Recursion : Exercises
Exercise
Let T be an array of integers of size n (n ≤ 100). Write recursive functions to perform the
following operations:
1. Prod: which returns the product of the elements of array T.
2. sorted: which indicates whether this array is sorted in ascending order or not
16
sorted: which indicates whether this array is
sorted in ascending order or not T 1 4 6 9 n
Sorted =vrai
Sorted(T ,n) =
The result is at the level of the T[n]> T[n-1]
subarray (T with size n-1).
Sorted(T ,n-1) = T[3]> T[2]=9>6
The result is at the level of the
subarray (T with size n-2).
Sorted(T ,n-2) = T[n-1]> T[n-2]
T[2]> T[1]=6>4
The result is at the level of the
Sorted(T ,n-3) T[n-2] > T[n-3]
subarray (T with size n-3).
= T[1]> T[0]=4>1
Sorted(T ,n-4) Sorted(T ,0)=True
If there is only one element in the
17
array,. n=0 => Sorted=True
Recursion : Exercises
Function Sorted(T:array[50]int,n: int):boolean ;
begin Number of elements=1
if (n=1) then Return (True) ;
else index
if(T[n-1]<T[n-2]) then Return (False) ;
else Return ( sorted(T, n-1)) ;
Size of vector
ensdif ;
endif ;
end 18
Recursion : Exercises
Function Prod(T:array[50] int,n: int):int ;
Begin Number of elements
if(n=0) alors Return (1) ;
else
Return (T[n-1] * Prod(T,n-1)) ;
Endif ; index Size of vector
End
19