5/25/2015 UOG, Computer science 1

The Handshake Problem

There are n people in a room. If each person shakes
hands once with every other person. What is the total
number h(n) of handshakes?

h(n) = h(n-1) + n-1 h(4) = h(3) + 3 h(3) = h(2) + 2 h(2) = 1

h(n): Sum of integer from 1 to n-1 = n(n-1) / 2

5/25/2015 UOG, Computer science 2

Recursion
o Recursion is one way to decompose a task into smaller
subtasks. At least one of the subtasks is a smaller
example of the same task.
• The smallest example of the same task has a non-
recursive solution.
Example: The factorial function
n! = n * (n-1)! and 1! = 1
 5/25/2015 UOG, Computer science 3

Recursion
• In general, There are two approaches to write repetitive
algorithm. One uses iteration; the other uses recursion.
• Recursion is a repetitive process in which an algorithm calls
itself or in other words “Recursion is a process in which
function calls itself”, and such functions are called as
recursive function.
Factorial – A Case Study:
1 if n=0
Factorial(n)=
n*(n-1)*(n-2)*…*3*2*1 if n>0
 5/25/2015 UOG, Computer science 4
factorial(4) =4*3*2*1 24
= 4 * factorial(3)
6
= 3* factorial(2)
2
= 2*factorial(1)
1
= 1*factorial(0)

If (n==0 || n==1)
return(1)
 5/25/2015 UOG, Computer science 5

Algorithm for factorial

• Input n
• Set I to 1
• Set fact to 1
• Loop (i<=n)
• Set fact=fact*I
• Increment I
• End loop
• Recturn fact
• End
 5/25/2015 UOG, Computer science 6

Recursive Algorithm
• recursiveFactorial(n)
• if(n equals 0)
• return 1
• else
• return( n * recursiveFactorial(n-1))
• end if
• end recursiveFactorial

1 if n=0
Factorial(n)=
n* factorial(F-1) if n>0
5/25/2015 UOG, Computer science 7

Recursive
a
Multiplication- A Case
if b=1
Study
Mult(a,b) =
mult (a * (b-1)) + a if b>1

15
mult(5,4) + 5= mult(5 * 3) + 5
= mult(5 * 2) +5 10
=mult(5,1) +5 5
 5/25/2015 UOG, Computer science 8

Algorithm
• mult(n,m)
• Input n,m
• if(m==1)
• return(n)
• else
• return( mult(n, m-1) + n)
• end if
• end
 5/25/2015 UOG, Computer science 9

Fibonacci series
• Fibonacci numbers are named after Leonardo Fibonacci, an
italian mathematician, who lived in the early thirteen century. In
this series each number is the sum of the previous numbers.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …..
0 if n=0
Fibonacci(n)= 1 if n=1
Fibonacci(n-1)+Fibonacci(n-2) otherwise

The generation of Fibonacci(4) is as follows

 5/25/2015 UOG, Computer science 10
• Fibonacci series
Fib(4)
3

2 Fib(3) Fib(2) 1
1
1
Fib(2) Fib(1) Fib(1) Fib(0)
0
1
Fib(1) Fib(0)
1
0
 UOG, Computer science 11

Binary Search
• The sequential search algorithm is very slow. If we have an
array of 1 million elements, we must do 1 million
comparisons in the worst case.
• It is suggested that you consider binary searches whenever
the list contains more than 50 elements.
• The Binary Search is applied only on sorted List, So if we
want to search an element form the List (Array), Then we
will have to first sort the Array then search it using the binary
search.
• Binary search starts by testing the data in the element at the
middle of the array. This determines if the target is in the first
half or the second half of the list.
 UOG, Computer science 12

• If it is in the first half, we do not need to check the second half.

If it is in the second half, we do not need to check the first half.
In other words, either ways we eliminate half the list from
further consideration. We repeat this process until we find the
target or satisfy ourselves that it is not in the list.
• To find the middle of the list, we need three variables, one to
identify the beginning of the list, one to identify the middle of
the list, and one to identify the end of the list.
• We will call our three indexes first, mid and last.
• Mid=(first+last)/2
 UOG, Computer science
13
• Binary search First mid last Target =85
Q. Search 85 from
0 3 7
58, 45, 92, 46, 85, 78, 23, 81

Index 0 1 2 3 4 5 6 7
23 45 46 58 78 81 85 92

85 > 58
First mid last
Target =85
4 5 7

Index 0 1 2 3 4 5 6 7
23 45 46 58 78 81 85 92

85 > 81
First mid last
Target =85
6 6 7

Index 0 1 2 3 4 5 6 7
23 45 46 58 78 81 85 92

85 ==85
 UOG, Computer science 14

if ( first > last)

return (-1);
mid=(first + last)/2;
if(x== a[mid]
return (mid);
if(x<a[mid])
search for x in a[first] to a[mid-1];
else
search for x in a[mid+1] to a[last];
 UOG, Computer science 15
First last Target =85
0 3 7

0 1 2 3 4 5 6 7
23 45 46 58 78 81 85 92

85 > 58
• Line 1: if (first > last) ? It is not true, so execute Line 3.
• Line 3: Mid=(0+7)/2=3
• Line 4: is x==a[3] ? 58!= 85, so execute Line 6.
• Line 6: if x<a[3] ? 85<58 it is not true, so per form else clause
at line 8
• Repeat the algorithm with first=mid+1=4 and last=7 i.e. search
the upper half of the array.
 UOG, Computer science 16
First mid last
Target =85
4 5 7

0 1 2 3 4 5 6 7
23 45 46 58 78 81 85 92

• Line 1: Is (4> 7) No, so execute line 3. 85 > 81

• Line 3. mid=(4+7)/2=5
• Line 4: Is x==a[5] ? 81 does not equal to 85, so execute line 6.
• Line 6: Is x< a[5] ? No , Since 85 < 81, so search for x in
a[mid+1] to a[last];
• Line 7: Repeat the algorithm with first=mid+1 and last=7
 UOG, Computer science 17
First mid last
Target =85
6 6 7

0 1 2 3 4 5 6 7
23 45 46 58 78 81 85 92

• Line 1: Is 5> 7 ? No, So execute line 3 85 ==85

• Line 3: mid=(6+7)/2=6
• Line 4: Since a[6]==85, return mid=6 and the answer , 85 is
indeed the sixth element of the array.
5/25/2015 UOG, Computer science 14-18

Types of Recursion
• Direct recursion
• a function calls itself
• Indirect recursion
• function A calls function B, and function B calls function A. Or,
• function A calls function B, which calls …, which calls function A
 5/25/2015 UOG, Computer science 14-19

Recursion vs. Iteration

• Benefits (+), disadvantages(-) for recursion:
+ Natural formulation of solution to certain problems
+ Results in shorter, simpler functions
- May not execute very efficiently
• Benefits (+), disadvantages(-) for iteration:
+ Executes more efficiently than recursion
- May not be as natural as recursion for some problems
5/25/2015 UOG, Computer science 20

Recursion
We have to pay a price for recursion:
• calling a function consumes more time and memory than
adjusting a loop counter.
• high performance applications (graphic action games,
simulations of nuclear explosions) hardly ever use recursion.
In less demanding applications recursion is an
attractive alternative for iteration (for the right
problems!)
5/25/2015 UOG, Computer science 21

Assignment
• Define n! by recursion
• Define GCD by recursion
• Write in brief about the recursion behavior of the
Fibonacci Series
• Define Recursion and recurrence.
• Differentiate between Recursion and the Iteration.