Today’s Material

• Recursion & Recursive Functions

– Divide & Conquer as an algorithm design strategy
– How to implement divide & conquer algorithms using recursion
 Recursive Functions
• It is possible for a function to call itself
– Called a recursive function
– Some problems are very easily solved using recursion

• The strategy by which recursion is used to solve a problem

is called divide-and-conquer
 Divide & Conquer Strategy (1)
• Divide the problem into smaller problems of the same type (divide)
• Solve each subproblem recursively using the same algorithm
(conquer)
• Merge the solutions to subproblems to obtain the solution for the
original problem
P

P1 ...................
P2 Pn
......

P1 P1 ... P1 P2 P2 ... P2n Pn Pn ... Pn

1 2 n 1 2 1 2 n

.................................................................................................................
...............................
Cases
Base

P P P P P P P P P ................ P P P
 Divide & Conquer Strategy (2)
/* Solve a problem P */
Solve(P){
/* Base case(s) */
if P is a base case problem
return the solution immediately

/* Divide P into P1, P2, ..Pn each of smaller scale (n>=2) */

/* Solve subproblems recursively */
S1 = Solve(P1); /* Solve P1 recursively to obtain S1 */
S2 = Solve(P2); /* Solve P2 recursively to obtain S2 */
…
Sn = Solve(Pn); /* Solve Pn recursively to obtain Sn */

/* Merge the solutions to subproblems */

/* to get the solution to the original big problem */
S = Merge(S1, S2, …, Sn);

/* Return the solution */

return S;
} //end-Solve
 Computing 1+2+..+N Recursively
• Compute the sum of the numbers from 1 to n:
– Sum(n) = 1+2+3+..+n

• Base case
– If n = 1, then Sum(1) = 1

• Recursive Formulation:
– Sum(n) = 1+2+…+(n-1) + n
– Sum(n) = Sum(n-1) + n
Computing 1+2+..+N Recursively
[Link]

/* Computes 1+2+3+…+n */ int main(){

int sum(int n){ int x = 0;
/* Base case */
if (n == 1) return 1; x = sum(4);
cout << x << endl;
/* Divide and conquer */
int partialSum = sum(n-1); return 0;
} /* end-main */
/* Merge */
return partialSum + n;
} /* end-sum */
 Recursion Tree for Sum(4)
[Link]
main
/* Computes 1+2+3+…+n */
x=sum(4) =1
int sum(int n){
0
/* Base case */
sum(4) return 6+4
if (n == 1) return 1;
partialSum=sum(3) =
/* Divide and conquer */ 6
int partialSum = sum(n-1);
return 3+3
sum(3)
/* Merge */
return partialSum + n; partialSum=sum(2) =
} /* end-sum */ 3
return 1+2
sum(2)
main(){
int x = sum(4); partialSum=sum(1) =
cout << “Sum: “ << x << endl; 1
} /* end-main */
sum(1)
return 1
 Call Stack for Sum(4)
[Link]
/* Computes 1+2+3+…+n */
Stack
int sum(int n){
/* Base case */ x = sum(4) =10 main
if (n == 1) return 1; n=4
Sum(4)
partialSum = sum(3) =6
/* Divide and conquer */
int partialSum = sum(n-1); n=3
Sum(3)
partialSum = sum(2) =3
/* Merge */
n=2
return partialSum + n; Sum(2)
} /* end-sum */ 1
partialSum = sum(1) =
n=1
Sum(1)
main(){ partialSum
int x = sum(4);
cout << “Sum: “ << x << endl;
} /* end-main */
 Computing N! Recursively
• Consider the problem of computing n! = 1*2*3*…*n

• Base cases
– If n = 0, then Factorial(0) = 1
– If n = 1, then Factorial(1) = 1

• Recursive Formulation:
– Factorial(n) = 1*2*…*(n-1)*n
– Factorial(n) = Factorial(n-1)*n
 Computing N! Recursively
[Link]
/* Computes 1*2*3*..*n */ int main(){
int factorial(int n){ int x = 0;
/* Base cases */
if (n <= 1) return 1; // 0!=1!=1 x = factorial(4);
cout << x << endl;
/* Divide and conquer */
int partialAns = factorial(n-1); return 0;
} /* end-main */
/* Merge */
return partialAns*n;
} /* end-factorial */
 Recursion Tree for factorial(4)
[Link] main
/* Computes 1*2*3*..*n */ factorial(4) =2
int factorial(int n){ 4
/* Base cases */
if (n <= 1) return 1; // 0!=1!=1 factorial(4) return 6*4
partialAns=factorial(3)=
/* Divide and conquer */ 6
int partialAns = factorial(n-1); return 2*3
factorial(3)
/* Merge */ partialAns=factorial(2)=
return partialAns*n; 2
} /* end-factorial */ return 1*2
factorial(2)
main(){
cout << factorial(4) << endl; partialAns=factorial(1)=
1
} /* end-main */
factorial(1)
return 1
 Call Stack for factorial(4)
[Link]
/* Computes 1*2*3*..*n */ Stack
int factorial(int n){
/* Base cases */ factorial(4) =24 main
if (n <= 1) return 1; // 0!=1!=1 n=4
factorial(4)
/* Divide and conquer */ partialAns = factorial(3) =6
int partialAns = factorial(n-1); n=3
factorial(3)
partialAns = factorial(2) =2
/* Merge */
n=2
return partialAns*n; factorial(2)
} /* end-factorial */ 1
partialAns = factorial(1) =
n=1
main(){ factorial(1)
partialAns
cout << factorial(4) << endl;
} /* end-main */
 Printing a Triangle Recursively (1)
• Consider the problem of printing a triangle with “n” rows
– Here is a triangle with 7 rows

• Base Case
– Print nothing if n <= 0

Triangle • Recursive Formulation

with n-1
rows – Print a triangle with “n-1” rows
– Then print the last row with “n” star
chars
Printing a Triangle Recursively (2)
[Link]

triangle(5) *****

triangle(4) ****

triangle(3) ***

triangle(2) **

triangle(1) *

triangle(0)
 Finding the first digit of a number (1)
• You are given a positive integer “n”
• Write a recursive function to return the first digit of the
number
– firstDigit(34257)  3
– firstDigit(8)  8

• Base case
– if n <= 9, return n

• Recursive Formulation
– Peel off the last digit of “n” and recursively find the first digit of the
remaining number -> return firstDigit(n/10)
– firstDigit(654) -> firstDigit(65) -> firstDigit(6)  return 6
Finding the first digit of a number (2)
[Link] return 4

firstDigit(456385)
return 4

firstDigit(45638)
return 4

firstDigit(4563)
return 4

firstDigit(456)
return 4

firstDigit(45)
return 4
firstDigit(4)
 Counting the number of digits of a number
(1)
• You are given a positive integer “num”
• Write a recursive function to count the number of digits in
num
– numDigits(34257)  5
– numDigits(8) -> 1

• Base case
– if n <= 9, return 1

• Recursive Formulation
– Count the number of digits in n/10 and add 1 to it
Counting the number of digits of a number
(2)
[Link] return 6

numDigits(456385)
return 5

numDigits(45638)
return 4

numDigits(4563)
return 3

numDigits(456)
return 2

numDigits(45)
return 1
numDigits(4)
 Counting the number of even digits of a
number (1)
• You are given a positive integer “num”
• Write a recursive function to count the number of even digits
in num
– numEvenDigits(34257)  2
– numEvenDigits(8) -> 1
– numEvenDigits(153) -> 0

• Base case
– if n <= 9, return 1 if n%2 == 0 else return 0;

• Recursive Formulation
– Count the number of even digits in n/10. If the last digit is even, add 1
to it
Counting the number of even digits of a number
(2)
[Link]
return 3
numEvenDigits(456385)
return 3

numEvenDigits(45638)
return 2

numEvenDigits(4563)
return 2

numEvenDigits(456)
return 1

numEvenDigits(45)
return 1
numEvenDigits(4)
 Range Sum of Numbers (1)
• Consider the problem of computing the sum of the numbers
from x to y, where x <= y
– int rangeSum(int x, int y)

– rangeSum(5, 7): 5+6+7 = 18

– rangeSum(10, 15): 10+11+12+13+14+15 = 75
– rangeSum(20, 20): 20
– rangeSum(21, 20): 0
 Range Sum of Numbers (2)
• Base cases:
– x > y  return 0
– x == y  return x

• Recursive Formulations:
1. RangeSum(x, y)x + RangeSum(x+1, y)

2. RangeSum(x, y)RangeSum(x, y-1) + y

3. RangeSum(x, y):
• int middle = x+(y-x)/2;
• RangeSum(x, middle) + RangeSum(middle+1, y)
Range Sum of Numbers (3)
[Link] [Link]

[Link]
 Recursion Tree for RangeSum3(3,9)
42

RS3(3,9)
24

18
RS3(3,6) RS3(7,9)
1 9
7 1 15
RS3(3,4) RS3(5,6) RS3(7,8) RS3(9,9)

4 6 8
3 5 7

RS3(3,3) RS3(4,4) RS3(5,5) RS3(6,6) RS3(7,7) RS3(8,8)

 Fibonacci Numbers
• Fibonacci numbers are defined as
follows
– F(0) = 0
– F(1) = 1
– F(n) = F(n-1) + F(n-2)
[Link]
/* Computes nth Fibonacci number */
int fibonacci(int n){
/* Base cases */
if (n == 0) return 0;
if (n == 1) return 1;

return fibonacci(n-1) + fibonacci(n-2);

} /* end-fibonacci */
 Recursion Tree for F(5)
5
F(5)
F(4)+F(3)
2
3
F(4) F(3)
F(3)+F(2) F(2)+F(1)
1
1 1
2
F(3) F(2) F(2) F(1)
F(2)+F(1) F(1)+F(0) F(1)+F(0)
1 1 1 0 1 0
F(2) F(1) F(1) F(0) F(1) F(0)
F(1)+F(0)
1 0
F(1) F(0)
 Euclid’s gcd Algorithm (1)
• Consider calculating the gcd(a, b)
– gcd(35, 25)  5
– gcd(48, 32)  16
– gcd(60, 54)  6
– gcd(70, 27)  1
 Euclid’s gcd Algorithm (2)
• Let gcd(a, b) = d
• Then we can write: a = x*d, b = y*d for some positive integers x & y
>= 1
• Assume that a > b. Then we can write a = q*b + r, where
– “q” is some positive integer >= 1
– “r” is the remainder of a divided by b, i.e., r = a % b

• a = q*b + r
• r = a – q*b
• r = x*d – q*y*d = (x-q*y)*d

• This means that “d” is also the gcd for “r”

• So, to compute gcd(a, b)  compute gcd(b, r) (Recursive formulation)
• We stop when r = 0. That is, gcd(a, 0)  a (Base case)
 Euclid’s gcd Algorithm (3)
[Link]

• gcd(35, 25)  gcd(25, 10)  gcd(10, 5)  gcd(5, 0)  5

• gcd(48, 32)  gcd(32, 16)  gcd(16, 0)  16

• gcd(60, 54)  gcd(54, 6)  gcd(6, 0)  6

• gcd(70, 27)  gcd(27, 16)  gcd(16, 11)  gcd(11, 5)  gcd(5, 1) 

gcd(1, 0)  1