CPT212-04-Recursive

Analysis of
Recursion
Algorithms
TAN TIEN PING
Introduction
Recursion is a technique by which a method makes one or more calls to itself during execution
When one invocation of the method makes a recursive call, that invocation is suspended until
the recursive call completes.
Complexity analysis can be easier done on algorithm implemented using loops, for algorithms
implemented using recursive, it is more challenging.
Note: All implementation of loops can be implemented using recursive and vice versa.
Many algorithms that uses divide and conquer techniques uses recursive approach. For divide
and conquer algorithms, there are 2 main steps, division and combination. Analysis of
algorithms can be done on the division step and combination step.
We will discuss few algorithms that uses recursive in solving a problem.
Loop vs Recursion
Loop Recursion
int j= 10; public void main(){

for(int i=0; i<N; i++){ recursive(0, 10, N);
j = j + 5; }
}
return j; public int recursive(int i, int j, int N){
if (i < N){
return recursive(i+1, j+5, N);
Total = 10 + N*5 } else{
return j;
}
}
Loop vs Recursion
Recursion Example: What is the answer when N=3?
public void main(int N){ call main(3);

recursive(0, 10, N);
} call recursive(0, 10, 3) +1 op
public int recursive(int i, int j, int N){ call recursive(1, 15, 3); +5 op
if (i < N){ call recursive(2, 20, 3); +5 op

return recursive(i+1, j+5, N);
call recursive(3, 25, 3); +5 op
} else{
return j;
return 25; +2 op
}
}
f(n) = 5n + 3, So f(n) = O(n)
Analyzing Recursive Algorithms
What can we summarize from the analysis of time complexity of the previous recursive
algorithm?
1. Determine how deep the recursive algorithm will go.
2. At each level, how many operations will be carried out.
Factorial Function
Factorial function can be implemented using linear recursive.
Linear recursive makes at most 1 recursive call in a recursive function.
Factorial Function
Example: What is the answer when n=4?
call factorial(4);
call factorial(3) return 1 * 1
call factorial(2); return 2 * 1
return 1;
Factorial Function
When the number of input, x, increases from 1, 2, 3 … n, the factorial(n)
number of multiplications performed, f(x) increases 1, 2,
3, ..., n respectively.
Complexity: O(n)
n # Activation # Multiplication n
1 2 1
2 3 2
3 4 3
…
n n+1 n
Binary Search
The binary_search() will check whether the key
value is larger or lower than mid. If larger than mid,
then call binary_search() and check upper half, else
if lower, check lower half, else we got the value we
searching for.
Each binary_search() recursively call maximum a
single binary_search()
Binary Search: Worst Case
Complexity
When input size, x=n, there Input size, x
When input size, x=n, there are
are how many comparisons?
or in another word, what is 2k-1 c*n comparisons how many comparisons? or in
another word, what is f(x=n) in
f(x=n) in worst case? worst case?
..
2k-1 = n 15 c*4 comparisons
k lg 2 = lg (n+1)
k = lg (n+1)
Height = log n 7 c*3 comparisons
3 c*2 comparisons
Binary search = O(log n)
Look at the binary_search(), there are 1 c*1 comparison
max 4 if…else statements, so c=3
Binary Search is log n
You have an array. If you shrink the size of your Every time binary_search() is called,
array to half every time. How many times you can maximum 3 if…else statements will be
shrink it? if… executed.
Size of the array is 2. Ans=1 f(n) = 3 . log n
Size of the array is 4. Ans=2 So, O(log n).
Size of the array is 8. Ans=3
Size of the array is 16. Ans=4
Size of the array is n. Ans=log n

Computing Power (Simple)
The power function can be implemented simply like below:
What is the complexity?

Computing Power (Simple)
When the number of input, x, increases x= f(x)
from 1, 2, 3 … n, the number of
multiplications performed, f(x) increases 1, 5n n multiplications
2, 3, ..., n respectively.
..
Complexity: O(n).
e.g. 53 = 5 x power(5,2) 53 3 multiplications
5 x power(5,1) 52 2 multiplications
5 x power(5,0) 51 1 multiplication
Computing Power (Efficient)
How to do better?
Idea: instead of computing 24 = 2 * 2 * 2 * 2 (note: 3 multiplications), we will compute it as (2 2)2
(note: 2 multiplications).
k)
k
k/2);
k
Note: f(k) = xk
When the number of input, x increases from x2, x4, x8 …,xn the number of multiplications
performed, f(x) increases 1, 2, 3, 4...,log n respectively.
Complexity: O(log n)
n=2, x=2, k=2 n=4, x=2, k=2 n=8 ... n

•2 •2 • Worst case: 3 • Worst case: n =
multiplications multiplications comparisons 2k
• k = log n
To calculate the number of
multiplication for calculating xk.
xn log n multiplications
The number of multiplications
involves does not depend on x, but
only on k. ...
when k increases from 0 …. n, the
number of multiplication involves x8 4 multiplications
increase from 0 to log n.
Height = log n
x4 3 multiplications
x2 2 multiplications
x0
Drawing English Ruler
A recursive method can be used to draw
English ruler as shown.
The algorithm uses binary recursion, where
each recursion method made 2 recursion calls.
For this problem, assume the number of
inches is a constant.
Drawing English Ruler
drawLine() majorLength=2
c
drawInterval() c
c
n
drawLine() c c c
c
drawRuler() drawInterval()
If you analyze the number of time drawInterval()
is called. Except on the drawRuler() which is only
called once*x (where x=nInches), other time,
drawInterval() is call 2 times in the
drawInterval().
When majorLength increases from 1, 2, 3 …, n
the number of drawInterval() called, f(n)
increases 1c, 3c, 7c, ...,c(2n-1) respectively.
Assuming c is the constant time for executing
drawLine().
So, f(n) = 2n-1, Complexity O(2n)
a line correspond
to a call to
x=1, f(1)=c*1 drawInterval()
x=2, f(2)= c*3
x=3, f(3)=c*7 … x=n, f(n)=c(2n-1)

CPT212-04-Recursive

Uploaded by

Copyright:

Available Formats

CPT212-04-Recursive

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CPT212-04-Recursive

Uploaded by

Copyright:

Available Formats

Analysis of

int j= 10; public void main(){

public void main(int N){ call main(3);

if (i < N){ call recursive(2, 20, 3); +5 op

call factorial(3) return 1 * 1

call factorial(2); return 2 * 1

call factorial(1); return 3 * 2

call factorial(0); return 4 * 6

Size of the array is 2. Ans=1 f(n) = 3 . log n

Size of the array is 4. Ans=2 So, O(log n).

Size of the array is 8. Ans=3

Size of the array is 16. Ans=4

Size of the array is n. Ans=log n

What is the complexity?

n=2, x=2, k=2 n=4, x=2, k=2 n=8 ... n

x=2, f(2)= c*3

x=3, f(3)=c*7 … x=n, f(n)=c(2n-1)

You might also like