Dr.

Islam El-Maddah
[email protected]
Ain shams University Faculty of Engineering
Spring 2021
 Definitionof a Recursion
 Simple Examples of Recursion
 Conditions for Recursion to
Work
 How Recursion Works Internally
 Binary Search
 Merge Sort

2
  A function is said to be recursive if it
calls itself
//Pre-condition: n is a non-negative integer
//Post-condition: returns n!, which is 1*2*3*…*n; 0!=1
// Principle for recursion: n!=(n-1)! * n.
long factorial(int n){
if (n==0) return 1;
long m=factorial(n-1); // recursion
m *=n;
return m;
}

3
factorial(3){
if (3==0) return 1;
long m=factorial(2);
m *=3;
return m;
} factorial(2){
if (2==0) return 1;
long m=factorial(1);
m *=2;
return m;
} factorial(1){
if (1==0) return 1;
long m=factorial(0);
m *=1;
return m; factorial(0){
} if (1==0) return 1;
long m=factorial(0);
m *=1;
return m;
}
factorial(3){
if (3==0) return 1;
long m=factorial(2);
m *=3;
return m;
} factorial(2){
if (2==0) return 1;
long m=factorial(1);
m *=2;
return m;
} factorial(1){
if (1==0) return 1;
long m=1;
m *=1;
return 1;
}
factorial(3){
if (3==0) return 1;
long m=factorial(2);
m *=3;
return m;
} factorial(2){
if (2==0) return 1;
long m=1;
m *=2;
return 2;
}
factorial(3){
if (3==0) return 1;
long m=2;
m *=3;
return 6;
}
 T(n) = T(n-1) + a
 T(0) = b

 T(n) = T(n-1) +a = T(n-2) +a +a = T(n-3) +

3*a
 In general T(n) = T(n-m)+ m*a
 Put m= n
 T(n) = T(0) + n * a = b+ n*a
So factorial(n) has O(n)
// Precondition: the input is a double array x[ ] of at least end
// elements. start and end are nonnegative integer indexes
// marking the portion of x[ ] over which to find the minimum.
// end >= start;
// Postcondition: returns the smallest value in x[ ].
// Recursion principle: if you we have the minimum of the 1st
// half of x and the minimum of the 2nd half of x, then the
// global minimum is the smaller of those two minimums
double min(double x[ ], int start, int end){
// …. On the next slide
}

9
double min(double x[ ], int start, int end){
assert(end >= start && start >=0);
if (end == start) // one number to minimize over
return x[start];
int mid=(start+end)/2; // mid-point index
double min1=min(x, start, mid); // 1st recursive call
double min2=min(x, mid+1, end); // 2nd recursive call
if (min1 <= min2)
return min1;
else
return min2;
}

10
 T(n) = 2*T(n/2) + a
 T(1) = b
 Analysis:
 T(n/2) = 2*T(n/4) +a
 T(n) = 2*T(n/2) +a = 4*T(n/4) +2*a +a =
 Use n = 2k
 T(2k ) = 2*T(2k-1 ) +a = 4*T(2k-2) +2*a +a =
 In general
 T(2k ) = 2m *T(2k-m)+ a*2m-1 + a*2m-2…+a
 Put m= k
 T(n) = n*T(1) + sum of a geometric series
= b*n + c*n ➔ minimum has O(n)
From graph
a: to compare m1, m2
T(n) =a +2a + ..+(n/2)a a and return
+nb b: to return the base
case
=a(n-1) + b n
a a

a a a a

b b b b
b b b b
 For recursive functions to work correctly,
two conditions must be met:
◦ The parameters of every recursive call must
be smaller in value or size than the input of
the original function
◦ There must be a basis step where the input
value or size is
 the smallest possible, and
 in which case the processing is non-
recursive.

13
long factorial(int n)
{
if (n==0) return 1; // basis step.
Input value n is minimum (0).
long m=factorial(n-1); // recursion.
Input value of recursive call is n-1<n
m *=n;
return m;
}

14
double min(double x[ ], int start, int end){
assert(end >= start && start >=0);
if (end == start) // Basis step. Input size is
minimum = 1.
return x[start]; // No recursion
int mid=(start+end)/2; // mid-point index
double min1=min(x, start, mid); // 1st recursive call
double min2=min(x, mid+1, end); // 2nd recursive call
// In both recursive calls, the input size is half the
original, and so less.
if (min1 <= min2)
return min1;
else This version is good when dealing
return min2; with parallel processing each call can
} be done on a separate core or a
machine T(n) = O (log n)

15
 When coding, do not concern yourself how
recursion is unfolding during execution
 Rather, think of yourself as a boss, and
treat each recursive call as an order to one
of your trusted subordinates to do some
job for you.
 As a boss, you need not worry how the
subordinate does their work. Instead, take
the outcome of their work
 Finally, use the outcomes to compute by
yourself the final result.

16
double min(double x[ ], int start, int end){
assert(end >= start && start >=0);
if (end == start) // Basis step.
return x[start]; // The boss does the basis step
int mid=(start+end)/2; // mid-point index
double min1=min(x, start, mid); // subordinate produces
min1
double min2=min(x, mid+1, end); // subordinate produces
min2
// The two recursive calls are the work of “subordinates”.
Don’t
// worry how the subordinates do their work.
if (min1 <= min2)
return min1; // You, the boss, take the
else // outcome min1 and min2
return min2; // from subordinates, and use
// them to get the final result.
}

17
 Input:
◦ A sorted array X[ ] of size n
◦ A value b to be searched for in X[ ]
 Output:
◦ If b is found, return the index k where X[k]=b
◦ If b is not found, return -1

 Definition: An X[ ] is said to be sorted if:

X[0] ≤ X[1] ≤ X[2] ≤ … ≤ X[n-1]

18
 The method is recursive:
 Compare b with the middle value X[mid]
 If b = X[mid], return mid
 If b < X[mid], then b can only be in the
left half of X[ ], because X[ ] is sorted. So
call the function recursively on the left
half.
 If b > X[mid], then b can only be in the
right half of X[ ], because X[ ] is sorted.
So call the function recursively on the
right half.
19
 X[12]: 1 5 7 12 15 20 25 27 35 40 47 60
0 1 2 3 4 5 6 7 8 9 10 11

 Search for b=12

 mid = (0+11)/2 = 5. Compare b with X[5]: 12<20.
 So search in left half X[0..4]
1 5 7 12 15 20 25 27 35 40 47 60
0 1 2 3 4 5 6 7 8 9 10 11
 mid = (0+4)/2 = 2. Compare b with X[2]: 12 > 7.
 So search right half X[3..4]
1 5 7 12 15 20 25 27 35 40 47 60
0 1 2 3 4 5 6 7 8 9 10 11
 mid = (3+4)/2 = 3.Compare b with X[3]: b=X[3]=12.
 Return 3.

20
int binarySearch(double b, double X[], int left,
int right){
if (left == right)
if (b==X[left]) return left;
else return -1;
int mid = (left+right)/2;
if (b==X[mid]) return mid;
if (b < X[mid]) return binarySearch (b, X, left,
mid-1);
if (b > X[mid]) return binarySearch(b, X, mid+1,
right);
}

21
 Call T(n) the time of binarySearch when the
array size is n.
 T(n) = T(n/2) + c, where c is some constant
representing the time of the basis step and
the last if-statement to choose between
min1 and min2
 Assume for simplicity that n= 2k. (so k=log2
n)
 T(2k)=T(2k-1)+c=T(2k-2)+c+c=T(2k-
3)+c+c+c = … =

T(20)+c+c+…c=T(1)+kc=O(k)=O(log n)
 Therefore, T(n)=O(log n).

22
 The general problem of sorting is to take
as input an unordered array X[ ], and give
as output the same set of data but sorted
in increasing/decreasing order
 Example:
◦ Input: 3 5 2 7 10 8 20 15 14 3 -1 2 -5
◦ Output: -5 -1 2 2 3 3 5 7 8 10 14 15 20
 We are interested in developing an
algorithm that does the sorting

24
 Need to
compare
8x7
O(n2)

Need to
compare
4+3
O(n)
Must be
sorted
 Need to
compare
8x7
O(n2)

Need to
compare
3+3
O(n)

younger pivot older

A recursive sorting function works as follows:

1. Make a recursive call to the sorting function

to sort the first half of the input array
2. Make another recursive call to sort the 2nd
half of the input array
3. Finally, merge the two sorted halves into a
single fully sorted array

27
 Say Y[ ] and Z[ ] are two sorted arrays to
be merged into a single sorted array
 Call the first element of an array the head
 While both arrays Y and Z are non-
empty, repeat the following steps:
◦ Compare the two heads of Y and Z
◦ Remove the smaller head and put it next in the
output
 Now either Y or Z is empty. Move the
non-empty array to the end of output,
and stop.
 The output is now fully sorted.

28
void merge(double X1[ ], int left1, int right1, //merge X1[left1..right1]
doubleX2[ ], int left2, int right2, //and X2[left2..right2]
double X[ ], int left)
{ // to X[left…]
int i1 = left1; int i2=left2; int i= left; // heads of X1, X2, X.
while (i1 <= right1 && i2 <= right2)
if (X1[i1] <= X2[i2]) {X[i]=X1[i1]; i1++; i++;}
else {X[i]=X2[i2]; i2++; i++;}
if (i1<right1) // copy leftovers of X1 to the end of X
while (i1<= right1) {X[i]=X1[i1]; i1++; i++;}
if (i2<right2) // copy leftovers of X2 to the end of X
while (i2<= right2) {X[i]=X2[i2]; i2++; i++;}
}

Time: Since each element of X1 and X2 and X are touched once,

the time is proportional to the sum of the sizes of X1 and X2.

29
void mergeSort(double X[ ], double Y[ ], int left, int right){
if (left==right) {Y[left] = X[left]; return;}
int mid = (left+right)/2;
double *Z= new double[right+1];

// sort left half of X and put the result in left half of Z

mergeSort(X,Z,left,mid);

// sort right half of X and put the result in right half of Z

mergeSort(X,Z,mid+1,right);

// merge the two halves of Z and put result in Y

merge(Z,left,mid, Z,mid+1,right, Y,left);
}
 Time T(n) = 2T(n/2) + cn, where cn is time for merge, and n is size of X.
 This implies: T(n) = O(n log n).

30
 T(n) = 2T(n/2) + a n

T(n/2) = 2T(n/4) +
a n/2
T(n/4) = 2aT(n/8)
+ a n/4

T(1) = c

T(n) = a log n * n+ c n
f(n)
{O(nd)
f(n/b)
:
a T(n) = a T(n/b) +n d
:
f(n/b)}
F(n)
{O(nd)
f(n/b)
:
a
:
f(n/b)}

Binary Search a=1, b=2, d=0 O(log n )

Merge Sort a=2, b =2, d=1 O(n log n)
Minimum of array a=2, b =2, d=0 O(n)
 int binarySearch(double b, double X[], int
left, int right){
if (left == right)
if (b==X[left]) return left;
n=right- else return -1;
left+1 int mid = (left+right)/2;
{O(nd)
= constant if (b==X[mid]) return mid;
d=0 if (b < X[mid]) return binarySearch (b, X, left,
Because of mid-1);
exclusive if if (b > X[mid]) return binarySearch(b, X,
a =1
mid+1, right);
And mid= ..
Makes }
b=2 Binary Search a=1, b=2, d=0 O(log n )
54
 Uses the divide-and-conquer technique to
sort a list
◦ List partitioned into two sublists
 Two sublists sorted and combined into one list
 Combined list then sorted using quicksort (recursion)
 Trivial to combine sorted lowerSublist and
upperSublist
 All sorting work done in partitioning the list

Data Structures Using C++ 2E 55

 Pivot divides list into two sublists
◦ lowerSublist: elements smaller than pivot
◦ upperSublist: elements greater than pivot
 Choosing the pivot
◦ lowerSublist and upperSublist nearly equal

List before the partition

List after the partition

Data Structures Using C++ 2E 56
 45 82 25 94 50 60 78 32 92

index

50 82 25 94 45 60 78 32 92

Small index =0
Pivot =50
Small index =0

Data Structures Using C++ 2E 57

 45 82 25 94 50 60 78 32 92
index

50 82 25 94 45 60 78 32 92

Small index =1
Pivot =50
Swap
25, 82

Data Structures Using C++ 2E 58

 45 82 25 94 50 60 78 32 92

index

45 25 82 94 45 60 78 32 92

Small index =1
Pivot =50
No swap

Data Structures Using C++ 2E 59

 45 82 25 94 50 60 78 32 92

index

50 25 45 94 82 60 78 32 92

Small index =1
Pivot =50
No swap,
cont

Data Structures Using C++ 2E 60

 45 82 25 94 50 60 78 32 92
index

50 25 45 94 82 60 78 32 92

Small index =1
Pivot =50

cont

Data Structures Using C++ 2E 61

 45 82 25 94 50 60 78 32 92

index

50 25 45 94 82 60 78 32 92

Small index =2
Pivot =50

cont

Data Structures Using C++ 2E 62

 45 82 25 94 50 60 78 32 92
index

50 25 45 32 82 60 78 94 92

Small index =3
Pivot =50 Swap 32, 94

Data Structures Using C++ 2E 63

 45 82 25 94 50 60 78 32 92
index

50 25 45 32 82 60 78 94 92

Small index =3
finish
Pivot =50

Data Structures Using C++ 2E 64

 45 82 25 94 50 60 78 32 92
index

32 25 45 50 82 60 78 94 92

Small index =3
Final swap
Pivot =50 50, 32

Data Structures Using C++ 2E 65

 45 82 25 94 50 60 78 32 92

32 25 45 50 82 60 78 94 92

Small index =3
Repeat with the two
Pivot =50 new sub lists

Data Structures Using C++ 2E 66

 Partition algorithm
◦ Determine pivot; swap pivot with first list element
 Suppose index smallIndex points to last element
smaller than pivot. smallIndex initialized to first list
element
◦ For the remaining list elements (starting at second
element): If current element smaller than pivot
 Increment smallIndex
 Swap current element with array element pointed to by
smallIndex
◦ Swap first element (pivot) with array element
pointed to by smallIndex

Data Structures Using C++ 2E 67

 Function partition
◦ Passes starting and ending list indices
◦ Swaps certain elements of the list

Data Structures Using C++ 2E 68

 Given starting and ending list indices
◦ Function recQuickSort implements the recursive
version of quicksort
 Function quickSort calls recQuickSort

Data Structures Using C++ 2E 69

Repeat with the two
new sub lists

45 82 25 94 50 60 78 32 92

50 82 25 94 45 60 78 32 92

32 25 45 50 82 60 78 94 92

32 25 45 82 60 78 94 92

25 32 45 78 60 82 94 92

25 32 45 60 78 82 94 92

Data Structures Using C++ 2E 70

TABLE 10-2 Analysis of quicksort for a list of length n

Data Structures Using C++ 2E 71