Solving a problem in terms of itself

n!

Recursion Is it:
n * (n-1) * (n-2) * ... 3 * 2 * 1

Dr. Gamal Tharwat

Dr. Gamal Tharwat

Or

n * (n - 1)!
[Link] 1 2

Solving a problem in terms of itself Recursion Defined

7! A procedure or function which calls itself.
Is it:
7 * 6 * 5 * 4 * 3 * 2 * 1 • Powerful mechanism for repetition.
Dr. Gamal Tharwat

Dr. Gamal Tharwat

• Makes algorithms more compact and

Or simple.
• Module calls a “clone” of itself.
7 * 6! • Very useful, especially for dynamic data
3 4
types.
Three Characteristics of Recursion Two Flavors of Recursion
if (terminating condition) then
do final actions
•Calls itself recursively else
move one step closer to terminating
condition
call “clone” of module
• Has some terminating condition

Dr. Gamal Tharwat

Dr. Gamal Tharwat

endif

- or -

• Moves “closer” to the terminating if (NOT (terminating condition)) then

move one step closer to terminating
condition. condition
5 6
call “clone” of module
endif

Everyday Example with No Final Actions

Everyday Example with Final Actions
procedure Pay_The_Bills() procedure Wash_The_Dishes()
if (No_More_Bills_To_Pay) then
Mail_The_Bills if (More_Dirty_Dishes) then
else Grab a dirty dish
Grab a bill
Dr. Gamal Tharwat

Dr. Gamal Tharwat

Wash it
Determine payment
Write a check Put it in drainer
Place check in envelope Wash_The_Dishes()
Place stamp on envelope endif
Pay_The_Bills()
endif endprocedure //Wash_The_Dishes
endprocedure //Pay_The_Bills 7 8
 Canonical Example A Recursive Procedure
Problem: Count from N to 10.
function fact returnsa Num(N iot in Num)
// Don’t forget comments!!! procedure CountToTen (count iot in Num)
if (count <= 10) then
if(N = 0) then print (count) // work
fact returns 1 CountToTen (count + 1) // recurse
else endif

Dr. Gamal Tharwat

Dr. Gamal Tharwat

endprocedure //CountToTen
fact returns N * fact(N - 1)
endif Call the procedure
endfunction // fact
CountToTen (7)
9 10

Tracing The Recursion procedure CountToTen (count iot in Num)

if (count <= 10) then
print (count) // work
To keep track of recursive execution, do what a computer does: CountToTen (count + 1) // recurse
maintain information on an activation stack. endif
endprocedure //CountToTen
Each stack frame contains:
• Module identifier and variables
Dr. Gamal Tharwat

Dr. Gamal Tharwat

• Any unfinished business

ModuleID: Data values Unfinished business

11 CountToTen: count=7 12
procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
if (count <= 10) then if (count <= 10) then
print (count) // work print (count) // work
CountToTen (count + 1) // recurse CountToTen (count + 1) // recurse
endif endif
endprocedure //CountToTen endprocedure //CountToTen

Dr. Gamal Tharwat

Dr. Gamal Tharwat

7 7

CountToTen: count=7 13 CountToTen: count=7 14

procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
if (count <= 10) then if (count <= 10) then
if (count <= 10) then if (count <= 10) then
print (count) // work print (count) // work
print (count) // work print (count) // work
CountToTen (count + 1) // recurse CountToTen (count + 1) // recurse
CountToTen (count + 1) // recurse CountToTen (count + 1) // recurse
endif endif
endif endif
endprocedure //CountToTen endprocedure //CountToTen
endprocedure //CountToTen endprocedure //CountToTen
Dr. Gamal Tharwat

Dr. Gamal Tharwat

7 7
8

CountToTen: count=8 CountToTen: count=8

CountToTen: count=7 15 CountToTen: count=7 16

procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
if (count <= 10) then procedure
if (count CountToTen
<= 10) then(count iot in Num)
if (count <= 10) then if (count <= 10) then
print (count) // work if (count
print <= 10)//then
(count) work
print (count) // work print (count) // work
CountToTen (count + 1) // recurse print (count)
CountToTen (count//+ work
1) // recurse
CountToTen (count + 1) // recurse CountToTen (count + 1) // recurse
endif CountToTen (count + 1) // recurse
endif
endif endif
endprocedure //CountToTen endif
endprocedure //CountToTen
endprocedure //CountToTen endprocedure //CountToTen
endprocedure //CountToTen

Dr. Gamal Tharwat

Dr. Gamal Tharwat

7 7
8 8
CountToTen: count=9

CountToTen: count=8 CountToTen: count=8

CountToTen: count=7 17 CountToTen: count=7 18

procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
procedure
if (count CountToTen
<= 10) then(count iot in Num) procedure
if (count CountToTen
<= 10) then(count iot in Num)
if (count <= 10) then if (count <= 10) then
if
print
(count
(count)
<= 10)//then
work if
print
(count
(count)
<= 10)//then
work
print (count) // work print (count) // work
CountToTen
print (count)
(count//+ work
1) // recurse CountToTen
print (count)
(count//+ work
1) // recurse
CountToTen (count + 1) // recurse CountToTen (count + 1) // recurse
endif
CountToTen (count + 1) // recurse endif
CountToTen (count + 1) // recurse
endif endif
endprocedure
endif //CountToTen endprocedure
endif //CountToTen
endprocedure //CountToTen endprocedure //CountToTen
endprocedure //CountToTen endprocedure //CountToTen
Dr. Gamal Tharwat

Dr. Gamal Tharwat

7 7
8 8
CountToTen: count=9 9 CountToTen: count=9 9
CountToTen: count=8 CountToTen: count=8

CountToTen: count=7 19 CountToTen: count=7 20

 procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
procedure
if (count CountToTen
<= 10) then(count iot in Num) procedure
if (count CountToTen
<= 10) then(count iot in Num)
procedure
if CountToTen
(count <= 10) then (count iot in Num) procedure
if CountToTen
(count <= 10) then (count iot in Num)
if (count
print <= 10)//then
(count) work if (count
print <= 10)//then
(count) work
print
if (count
(count)
<= 10)
// then
work print
if (count
(count)
<= 10)
// then
work
print (count)
CountToTen (count//+ work
1) // recurse print (count)
CountToTen (count//+ work
1) // recurse
CountToTen
print (count)
(count //
+ 1)
work// recurse CountToTen
print (count)
(count //
+ 1)
work// recurse
CountToTen (count + 1) // recurse
endif CountToTen (count + 1) // recurse
endif
endifCountToTen (count + 1) // recurse endifCountToTen (count + 1) // recurse
endif
endprocedure //CountToTen endif
endprocedure //CountToTen
endprocedure
endif //CountToTen endprocedure
endif //CountToTen
endprocedure //CountToTen endprocedure //CountToTen
endprocedure //CountToTen endprocedure //CountToTen

Dr. Gamal Tharwat

Dr. Gamal Tharwat

CountToTen: count=10 7 CountToTen: count=10 7
8 8
CountToTen: count=9 9 CountToTen: count=9 9
CountToTen: count=8 CountToTen: count=8 10
CountToTen: count=7 21 CountToTen: count=7 22

procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
procedure
if (count CountToTen
<= 10) then(count iot in Num) procedure
if (count CountToTen
<= 10) then(count iot in Num)
if
procedure
(count <=
CountToTen
10) then (count iot in Num) if
procedure
(count <=
CountToTen
10) then (count iot in Num)
if
print
(count
(count)
<= 10)//then
work procedure
if
print
(count CountToTen
(count)
<= 10)//then
work(count iot in Num)
print
if (count
(count)
<= 10)
// then
work print
if (count
(count)
<= 10)// then
work
CountToTen
print (count)
(count//+ work
1) // recurse if (count
CountToTen
print (count)<= 10)
(count //+then
work
1) // recurse
CountToTen
print (count)
(count //
+ 1)
work// recurse CountToTen
print (count)
(count // + 1)
work// recurse
endif
CountToTen (count + 1) // recurse endif print (count)
CountToTen (count // work// recurse
+ 1)
endifCountToTen (count + 1) // recurse endifCountToTen (count + 1) // recurse
endprocedure
endif //CountToTen endifCountToTen
endprocedure (count + 1) // recurse
//CountToTen
endif
endprocedure //CountToTen endif
endprocedure //CountToTen
endprocedure //CountToTen endif
endprocedure //CountToTen
endprocedure //CountToTen endprocedure //CountToTen
endprocedure //CountToTen
Dr. Gamal Tharwat

Dr. Gamal Tharwat

CountToTen: count=11

CountToTen: count=10 7 CountToTen: count=10 7

8 8
CountToTen: count=9 9 CountToTen: count=9 9
CountToTen: count=8 10 CountToTen: count=8 10
CountToTen: count=7 23 CountToTen: count=7 24
 procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
procedure
if (count CountToTen
<= 10) then(count iot in Num) procedure
if (count CountToTen
<= 10) then(count iot in Num)
procedure
if CountToTen
(count <= 10) then (count iot in Num) if (count <= 10) then
if (count
print <= 10)//then
(count) work if (count
print <= 10)//then
(count) work
print
if (count
(count)
<= 10)
// then
work print (count) // work
print (count)
CountToTen (count//+ work
1) // recurse print (count)
CountToTen (count//+ work
1) // recurse
CountToTen
print (count)
(count //
+ 1)
work// recurse CountToTen (count + 1) // recurse
CountToTen (count + 1) // recurse
endif CountToTen (count + 1) // recurse
endif
endifCountToTen (count + 1) // recurse endif
endif
endprocedure //CountToTen endif
endprocedure //CountToTen
endprocedure
endif //CountToTen endprocedure //CountToTen
endprocedure //CountToTen endprocedure //CountToTen
endprocedure //CountToTen

Dr. Gamal Tharwat

Dr. Gamal Tharwat

CountToTen: count=10 7 7
8 8
CountToTen: count=9 9 CountToTen: count=9 9
CountToTen: count=8 10 CountToTen: count=8 10
CountToTen: count=7 25 CountToTen: count=7 26

procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
procedure CountToTen (count iot in Num)
if (count <= 10) then if (count <= 10) then
if (count <= 10) then
print (count) // work print (count) // work
print (count) // work
CountToTen (count + 1) // recurse CountToTen (count + 1) // recurse
CountToTen (count + 1) // recurse
endif endif
endif
endprocedure //CountToTen endprocedure //CountToTen
endprocedure //CountToTen
Dr. Gamal Tharwat

Dr. Gamal Tharwat

7 7
8 8
9 9
CountToTen: count=8 10 10
CountToTen: count=7 27 CountToTen: count=7 28
 Reversing the Work and Recursion
Problem: Count from 10 to N.
Return to the algorithm. procedure CountToTen (count iot in Num)
if (count <= 10) then
CountToTen (count + 1) // recurse

Dr. Gamal Tharwat

Dr. Gamal Tharwat

print (count) // work
endif
endprocedure //CountToTen
7
8
9 Now the work will happen as the frames pop off the
10 stack!

29 30

procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
if (count <= 10) then if (count <= 10) then
CountToTen (count + 1) // recurse CountToTen (count + 1) // recurse
print (count) // work print (count) // work
endif endif
endprocedure //CountToTen endprocedure //CountToTen
Dr. Gamal Tharwat

Dr. Gamal Tharwat

CountToTen: count=7 31 CountToTen: count=7 32

procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
if (count <= 10) then if (count <= 10) then
if (count <= 10) then if (count <= 10) then
print (count) // work print (count) // work
CountToTen (count + 1) // recurse CountToTen (count + 1) // recurse
CountToTen (count + 1) // recurse CountToTen (count + 1) // recurse
print (count) // work print (count) // work
endif endif
endif endif
endprocedure //CountToTen endprocedure //CountToTen
endprocedure //CountToTen endprocedure //CountToTen

Dr. Gamal Tharwat

Dr. Gamal Tharwat

CountToTen: count=8 CountToTen: count=8

CountToTen: count=7 33 CountToTen: count=7 34

procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
procedure
if (count CountToTen
<= 10) then(count iot in Num) procedure
if (count CountToTen
<= 10) then(count iot in Num)
if (count <= 10) then if (count <= 10) then
if
print
(count
(count)
<= 10)//then
work if
print
(count
(count)
<= 10)//then
work
print (count) // work print (count) // work
CountToTen
CountToTen(count
(count+ +1)1) ////recurse
recurse CountToTen
CountToTen(count
(count+ +1)1) ////recurse
recurse
CountToTen (count + 1) // recurse CountToTen (count + 1) // recurse
endif
print (count) // work endif
print (count) // work
endif endif
endprocedure
endif //CountToTen endprocedure
endif //CountToTen
endprocedure //CountToTen endprocedure //CountToTen
endprocedure //CountToTen endprocedure //CountToTen
Dr. Gamal Tharwat

Dr. Gamal Tharwat

CountToTen: count=9 CountToTen: count=9

CountToTen: count=8 CountToTen: count=8

CountToTen: count=7 35 CountToTen: count=7 36

 procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
procedure
if (count CountToTen
<= 10) then(count iot in Num) procedure
if (count CountToTen
<= 10) then(count iot in Num)
procedure
if CountToTen
(count <= 10) then (count iot in Num) procedure
if CountToTen
(count <= 10) then (count iot in Num)
if (count
print <= 10)//then
(count) work if (count
print <= 10)//then
(count) work
print
if (count
(count)
<= 10)
// then
work print
if (count
(count)
<= 10)
// then
work
print (count)
CountToTen (count//+ work
1) // recurse print (count)
CountToTen (count//+ work
1) // recurse
CountToTen
CountToTen(count
(count+ 1)
+ 1)// //
recurse
recurse CountToTen
CountToTen(count
(count+ 1)
+ 1)// //
recurse
recurse
CountToTen (count + 1) // recurse
endif CountToTen (count + 1) // recurse
endif
endifprint (count) // work endifprint (count) // work
endif
endprocedure //CountToTen endif
endprocedure //CountToTen
endprocedure
endif //CountToTen endprocedure
endif //CountToTen
endprocedure //CountToTen endprocedure //CountToTen
endprocedure //CountToTen endprocedure //CountToTen

Dr. Gamal Tharwat

Dr. Gamal Tharwat

CountToTen: count=10 CountToTen: count=10

CountToTen: count=9 CountToTen: count=9

CountToTen: count=8 CountToTen: count=8

CountToTen: count=7 37 CountToTen: count=7 38

procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
procedure
if (count CountToTen
<= 10) then(count iot in Num) procedure
if (count CountToTen
<= 10) then(count iot in Num)
if
procedure
(count <=
CountToTen
10) then (count iot in Num) if
procedure
(count <=
CountToTen
10) then (count iot in Num)
procedure
if
print
(count CountToTen
(count)
<= 10)//then
work(count iot in Num) if
print
(count
(count)
<= 10)//then
work
print
if (count
(count)
<= 10)// then
work print
if (count
(count)
<= 10)
// then
work
if (count
CountToTen
print <= 10)
(count)
(count //+then
work
1) // recurse CountToTen
print (count)
(count//+ work
1) // recurse
CountToTen
print (count)
(count // + 1)
work// recurse CountToTen
CountToTen(count
(count+ 1)
+ 1)// //
recurse
recurse
endif CountToTen
CountToTen (count
(count + 1)// //
+ 1) recurse
recurse endif
CountToTen (count + 1) // recurse
endifCountToTen (count + 1) // recurse endifprint (count) // work
endifprint //CountToTen
endprocedure (count) // work endprocedure
endif //CountToTen
endif
endprocedure //CountToTen endif
endprocedure //CountToTen
endif
endprocedure //CountToTen endprocedure //CountToTen
endprocedure //CountToTen endprocedure //CountToTen
endprocedure //CountToTen
Dr. Gamal Tharwat

Dr. Gamal Tharwat

CountToTen: count=11

CountToTen: count=10 CountToTen: count=10 10

CountToTen: count=9 CountToTen: count=9

CountToTen: count=8 CountToTen: count=8

CountToTen: count=7 39 CountToTen: count=7 40

 procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
procedure
if (count CountToTen
<= 10) then(count iot in Num) procedure
if (count CountToTen
<= 10) then(count iot in Num)
procedure
if CountToTen
(count <= 10) then (count iot in Num) if (count <= 10) then
if (count
print <= 10)//then
(count) work if (count
print <= 10)//then
(count) work
print
if (count
(count)
<= 10)
// then
work print (count) // work
print (count)
CountToTen (count//+ work
1) // recurse CountToTen(count
CountToTen (count+ +1)1) ////recurse
recurse
CountToTen
CountToTen(count
(count+ 1)
+ 1)// //
recurse
recurse CountToTen (count + 1) // recurse
CountToTen (count + 1) // recurse
endif print (count) // work
endif
endifprint (count) // work endif
endif
endprocedure //CountToTen endif
endprocedure //CountToTen
endprocedure
endif //CountToTen endprocedure //CountToTen
endprocedure //CountToTen endprocedure //CountToTen
endprocedure //CountToTen

Dr. Gamal Tharwat

Dr. Gamal Tharwat

CountToTen: count=10 10 10
9
CountToTen: count=9 CountToTen: count=9

CountToTen: count=8 CountToTen: count=8

CountToTen: count=7 41 CountToTen: count=7 42

procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
procedure
if (count CountToTen
<= 10) then(count iot in Num) if (count <= 10) then
if (count <= 10) then if (count <= 10) then
if
print
(count
(count)
<= 10)//then
work print (count) // work
print (count) // work CountToTen (count + 1) // recurse
CountToTen
CountToTen(count
(count+ +1)1) ////recurse
recurse CountToTen (count + 1) // recurse
CountToTen (count + 1) // recurse print (count) // work
endif
print (count) // work endif
endif endif
endprocedure
endif //CountToTen endprocedure //CountToTen
endprocedure //CountToTen endprocedure //CountToTen
endprocedure //CountToTen
Dr. Gamal Tharwat

Dr. Gamal Tharwat

10 10
9 9
CountToTen: count=9 8
CountToTen: count=8 CountToTen: count=8

CountToTen: count=7 43 CountToTen: count=7 44

procedure CountToTen (count iot in Num) procedure CountToTen (count iot in Num)
procedure CountToTen (count iot in Num)
if (count <= 10) then if (count <= 10) then
if (count <= 10) then
print (count) // work CountToTen (count + 1) // recurse
CountToTen (count + 1) // recurse
CountToTen (count + 1) // recurse print (count) // work
print (count) // work
endif endif
endif
endprocedure //CountToTen endprocedure //CountToTen
endprocedure //CountToTen

Dr. Gamal Tharwat

Dr. Gamal Tharwat

10 10
9 9
8 8
CountToTen: count=8 7
CountToTen: count=7 45 CountToTen: count=7 46

procedure CountToTen (count iot in Num)

if (count <= 10) then
CountToTen (count + 1) // recurse
print (count) // work
endif
endprocedure //CountToTen Return to the algorithm.
Dr. Gamal Tharwat

Dr. Gamal Tharwat

10 10
9 9
8 8
7 7
CountToTen: count=7 47 48
 Recursive Function
Example: Factorial
Advanced Problem: calculate n! (n factorial)
n! = 1 if n = 0

Recursion n! = 1 * 2 * 3 *...* n if n > 0

Dr. Gamal Tharwat

Dr. Gamal Tharwat

Recursively:
if n = 0, then n! = 1
if n > 0, then n! = n * (n-1)!
[Link] 49 50

Solving Recursive Problems Factorial Function

function Factorial returnsa Num
• See recursive solutions as two sections: (n isoftype in Num)
• Current // Calculates n factorial, n!
// Precondition: n is a non-negative
• Rest //
if (n = 0) then
integer
Dr. Gamal Tharwat

Dr. Gamal Tharwat

Factorial returns 1
else
N! = N * (N-1)! Factorial returns n * Factorial(n-1)
endif
7! = 7 * 6! endfunction //Factorial

7! = 7 * (6 * 5 * 4 * 3 * 2 * 1 * 1) 51 52
 if (0 = 0)
then Fact returns 1
Tracing Details
else
if (1 = 0)
thenFact
Factreturns
returns1 1
elseendif
endfunction 1. Actual parameters stored
Fact returns//Fact
1 * Fact(0) 5. Return value and
release stack frame on the stack
endif
if (2 = 0)
endfunction //Fact
then Fact returns 1 function Fact returnsa Num (2) 3. Create a new
else

Dr. Gamal Tharwat

Dr. Gamal Tharwat

if (2 = 0) Stack Frame
Fact returns 2 * Fact(1) then Fact returns 1
if (3endif
= 0) else
endfunction //Fact 1
then Fact returns Fact returns 2 * Fact(1)
endif
else
endfunction //Fact
Fact returns 3 * Fact(2)
endif Test
algorithm 4. Unfinished
2. Recursive call
endfunction
ans <- Fact(3)//Fact Business
to Fact
endalgorithm 53 54

Activation Stack for Factorial Activation Stack for Factorial

Call the function: answer <- Fact(5)

Dr. Gamal Tharwat

Dr. Gamal Tharwat

Fact. 1st: N=5, Unfinished: 5*Fact(4)

55 56
Main Algorithm: Unfinished: answer <- Fact (5) Main Algorithm: Unfinished: answer <- Fact (5)
 Activation Stack for Factorial Activation Stack for Factorial

Dr. Gamal Tharwat

Dr. Gamal Tharwat

Fact. 3rd: N=3, Unfinished: 3*Fact(2)

Fact. 2nd: N=4, Unfinished: 4*Fact(3) Fact. 2nd: N=4, Unfinished: 4*Fact(3)

Fact. 1st: N=5, Unfinished: 5*Fact(4) Fact. 1st: N=5, Unfinished: 5*Fact(4)
57 58
Main Algorithm: Unfinished: answer <- Fact (5) Main Algorithm: Unfinished: answer <- Fact (5)

Activation Stack for Factorial Activation Stack for Factorial

Dr. Gamal Tharwat

Dr. Gamal Tharwat

Fact. 5th: N=1, Unfinished: 1*Fact(0)

Fact. 4th: N=2, Unfinished: 2*Fact(1) Fact. 4th: N=2, Unfinished: 2*Fact(1)

Fact. 3rd: N=3, Unfinished: 3*Fact(2) Fact. 3rd: N=3, Unfinished: 3*Fact(2)

Fact. 2nd: N=4, Unfinished: 4*Fact(3) Fact. 2nd: N=4, Unfinished: 4*Fact(3)

Fact. 1st: N=5, Unfinished: 5*Fact(4) Fact. 1st: N=5, Unfinished: 5*Fact(4)
59 60
Main Algorithm: Unfinished: answer <- Fact (5) Main Algorithm: Unfinished: answer <- Fact (5)
 Activation Stack for Factorial Activation Stack for Factorial

Fact. 6th: N=0, Finished: returns 1

Dr. Gamal Tharwat

Dr. Gamal Tharwat

Fact. 5th: N=1, Unfinished: 1*Fact(0) Fact. 5th: N=1, Finished: returns 1*1

Fact. 4th: N=2, Unfinished: 2*Fact(1) Fact. 4th: N=2, Unfinished: 2*Fact(1)

Fact. 3rd: N=3, Unfinished: 3*Fact(2) Fact. 3rd: N=3, Unfinished: 3*Fact(2)

Fact. 2nd: N=4, Unfinished: 4*Fact(3) Fact. 2nd: N=4, Unfinished: 4*Fact(3)

Fact. 1st: N=5, Unfinished: 5*Fact(4) Fact. 1st: N=5, Unfinished: 5*Fact(4)
61 62
Main Algorithm: Unfinished: answer <- Fact (5) Main Algorithm: Unfinished: answer <- Fact (5)

Activation Stack for Factorial Activation Stack for Factorial

Dr. Gamal Tharwat

Dr. Gamal Tharwat

Fact. 4th: N=2, Finished: returns 2*1

Fact. 3rd: N=3, Unfinished: 3*Fact(2) Fact. 3rd: N=3, Finished: returns 3*2

Fact. 2nd: N=4, Unfinished: 4*Fact(3) Fact. 2nd: N=4, Unfinished: 4*Fact(3)

Fact. 1st: N=5, Unfinished: 5*Fact(4) Fact. 1st: N=5, Unfinished: 5*Fact(4)
63 64
Main Algorithm: Unfinished: answer <- Fact (5) Main Algorithm: Unfinished: answer <- Fact (5)
 Activation Stack for Factorial Activation Stack for Factorial

Dr. Gamal Tharwat

Dr. Gamal Tharwat

Fact. 2nd: N=4, Finished: returns 4*6

Fact. 1st: N=5, Unfinished: 5*Fact(4) Fact. 1st: N=5, Finished: returns 5*24
65 66
Main Algorithm: Unfinished: answer <- Fact (5) Main Algorithm: Unfinished: answer <- Fact (5)

Activation Stack for Factorial Exponentiation

baseexponent
e.g. 53
Dr. Gamal Tharwat

Dr. Gamal Tharwat

Could be written as a function

Power(base, exp)
67 68
Main Algorithm: Finished: answer <- 120
 Can we write it recursively? Another Recursive Function
function Power returnsa Num
(base, exp isoftype in Num)
be = b * b(e-1) // Computes the value of BaseExp
// Pre: exp is a non-negative integer
if (exp = 0) then
Power returns 1

Dr. Gamal Tharwat

Dr. Gamal Tharwat

What’s the limiting case? else
Power returns base * Power(base, exp-1)
endif
endfunction //Power
When e = 0 we have b0 which always
equals?
69 70
1

Activations Stack Example

Function Power returnsa Num (base, exp isoftype in Num) Bunnies?
//Computes the value of BaseExp
//Preconditions: exp is a non-negative integer
if(exp = 0 ) then
Power returns 1 • The Time: 13th Century
else • The Place: Italy
Power returns Power base = 3 exp = 0 Finished: 1
(base * 1 • The Man: Fibonacci
Power(base, exp – 1))Power base = 3 exp = 1 1
3 *Power(3,0) • The Problem: We start with a pair of newborn rabbits. At the end of the
Dr. Gamal Tharwat

Dr. Gamal Tharwat

endif 3 2nd month, and each month thereafter the female gives birth to a new
endfunction //Power pair of rabbits: one male and one female. The babies mature at the
Power base = 3 exp = 2 3
3 *Power(3,1)
same rate as the parents and begin to produce offspring on the same
9
schedule. So how many rabbits do we have at the end of one year?
Power base = 3 exp = 3 9
3 *Power(3,2)
27
Power base = 3 exp = 4 27
3 *Power(3,3)
81 Slide 72
Algo: total <-Total
Power(3,4)
<- 81 71
 = 1 pair bunnies (m/f) A More Complex Recursive Function

Fibonacci Number Sequence

if n = 1, then Fib(n) = 1
if n = 2, then Fib(n) = 1

Dr. Gamal Tharwat

Dr. Gamal Tharwat

if n > 2, then Fib(n) = Fib(n-2) + Fib(n-1)

Numbers in the series:

1, 1, 2, 3, 5, 8, 13, 21, 34, ...

73 74

Fibonacci Sequence Function Tracing with Multiple Recursive Calls

function Fib returnsa Num (n iot in Num)
// Calculates the nth Fibonacci number
// Precondition: N is a positive integer
if ((n = 1) OR (n = 2)) then
Fib returns 1
Dr. Gamal Tharwat

Dr. Gamal Tharwat

else
Fib returns Fib(n-2) + Fib(n-1)
endif
endfunction //Fibonacci

75 76
Main Algorithm: answer <- Fib(5)
Tracing with Multiple Recursive Calls Tracing with Multiple Recursive Calls

Dr. Gamal Tharwat

Dr. Gamal Tharwat

Fib(3): Fib returns Fib(1) + Fib(2)

Fib(5): Fib returns Fib(3) + Fib(4) Fib(5): Fib returns Fib(3) + Fib(4)
77 78
Main Algorithm: answer <- Fib(5) Main Algorithm: answer <- Fib(5)

Tracing with Multiple Recursive Calls Tracing with Multiple Recursive Calls
Dr. Gamal Tharwat

Dr. Gamal Tharwat

Fib(1): Fib returns 1

Fib(3): Fib returns Fib(1) + Fib(2) Fib(3): Fib returns 1 + Fib(2)

Fib(5): Fib returns Fib(3) + Fib(4) Fib(5): Fib returns Fib(3) + Fib(4)
79 80
Main Algorithm: answer <- Fib(5) Main Algorithm: answer <- Fib(5)
Tracing with Multiple Recursive Calls Tracing with Multiple Recursive Calls

Dr. Gamal Tharwat

Dr. Gamal Tharwat

Fib(2): Fib returns 1

Fib(3): Fib returns 1 + Fib(2) Fib(3): Fib returns 1 + 1

Fib(5): Fib returns Fib(3) + Fib(4) Fib(5): Fib returns Fib(3) + Fib(4)
81 82
Main Algorithm: answer <- Fib(5) Main Algorithm: answer <- Fib(5)

Tracing with Multiple Recursive Calls Tracing with Multiple Recursive Calls
Dr. Gamal Tharwat

Dr. Gamal Tharwat

Fib(4): Fib returns Fib(2) + Fib(3)

Fib(5): Fib returns 2 + Fib(4) Fib(5): Fib returns 2 + Fib(4)

83 84
Main Algorithm: answer <- Fib(5) Main Algorithm: answer <- Fib(5)
Tracing with Multiple Recursive Calls Tracing with Multiple Recursive Calls

Dr. Gamal Tharwat

Dr. Gamal Tharwat

Fib(2): Fib returns 1

Fib(4): Fib returns Fib(2) + Fib(3) Fib(4): Fib returns 1 + Fib(3)

Fib(5): Fib returns 2 + Fib(4) Fib(5): Fib returns 2 + Fib(4)

85 86
Main Algorithm: answer <- Fib(5) Main Algorithm: answer <- Fib(5)

Tracing with Multiple Recursive Calls Tracing with Multiple Recursive Calls
Dr. Gamal Tharwat

Dr. Gamal Tharwat

Fib(1): Fib returns 1

Fib(3): Fib returns Fib(1) + Fib(2) Fib(3): Fib returns Fib(1) + Fib(2)

Fib(4): Fib returns 1 + Fib(3) Fib(4): Fib returns 1 + Fib(3)

Fib(5): Fib returns 2 + Fib(4) Fib(5): Fib returns 2 + Fib(4)

87 88
Main Algorithm: answer <- Fib(5) Main Algorithm: answer <- Fib(5)
Tracing with Multiple Recursive Calls Tracing with Multiple Recursive Calls

Dr. Gamal Tharwat

Dr. Gamal Tharwat

Fib(2): Fib returns 1

Fib(3): Fib returns 1 + Fib(2) Fib(3): Fib returns 1 + Fib(2)

Fib(4): Fib returns 1 + Fib(3) Fib(4): Fib returns 1 + Fib(3)

Fib(5): Fib returns 2 + Fib(4) Fib(5): Fib returns 2 + Fib(4)

89 90
Main Algorithm: answer <- Fib(5) Main Algorithm: answer <- Fib(5)

Tracing with Multiple Recursive Calls Tracing with Multiple Recursive Calls
Dr. Gamal Tharwat

Dr. Gamal Tharwat

Fib(3): Fib returns 1 + 1

Fib(4): Fib returns 1 + Fib(3) Fib(4): Fib returns 1 + 2

Fib(5): Fib returns 2 + Fib(4) Fib(5): Fib returns 2 + Fib(4)

91 92
Main Algorithm: answer <- Fib(5) Main Algorithm: answer <- Fib(5)
Tracing with Multiple Recursive Calls Tracing with Multiple Recursive Calls

Dr. Gamal Tharwat

Dr. Gamal Tharwat

Fib(5): Fib returns 2 + 3
93 94
Main Algorithm: answer <- Fib(5) Main Algorithm: answer <- 5

Example 2: Fibonacci Numbers Fibonacci Numbers

//Calculate Fibonacci numbers using recursive function.
//A very inefficient way, but illustrates recursion well
• Fibonacci Numbers : int fib(int number)
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, {
if (number == 0) return 0;
... where each number is the sum of
if (number == 1) return 1;
the preceding two. .‫حيث كل عدد هو مجموع السابقتين‬
Dr. Gamal Tharwat

Dr. Gamal Tharwat

return (fib(number-1) + fib(number-2));

• Recursive definition: }
• F(0) = 0; int main(){
int inp_number;
// driver function

• F(1) = 1;
cout << "Please enter an integer: ";
cin >> inp_number;
cout << "The Fibonacci number for "<< inp_number
• F(number) = F(number-1)+ F(number-2); << " is "<< fib(inp_number)<<endl;
return 0;
95 } 96
 Trace a Fibonacci Number Trace a Fibonacci Number
int fib(int num)
{
• Assume the input number is 4, that is, num=4: if (num == 0) return 0;
if (num == 1) return 1;
fib(4): return
fib(0):
4 == 0 ? No; 4 == 1? No. (fib(num-1)+fib(num-2)); 0 == 0 ? Yes.
} fib(0) = 0;
fib(4) = fib(3) + fib(2)
return fib(0);
fib(3):
fib(2) = 1 + 0 = 1;

Dr. Gamal Tharwat

Dr. Gamal Tharwat

3 == 0 ? No; 3 == 1? No. return fib(2);
fib(3) = fib(2) + fib(1) fib(3) = 1 + fib(1)
fib(2): fib(1):
2 == 0? No; 2==1? No. 1 == 0 ? No; 1 == 1? Yes
fib(2) = fib(1)+fib(0) fib(1) = 1;
fib(1): return fib(1);
1== 0 ? No; 1 == 1? Yes. fib(3) = 1 + 1 = 2;
return fib(3)
fib(1) = 1;
return fib(1);
97 98

Trace a Fibonacci Number Mutual Recursion

fib(2):
Recursion doesn’t always occur because a routine calls
2 == 0 ? No; 2 == 1? No. itself...
fib(2) = fib(1) + fib(0)
fib(1):
1== 0 ? No; 1 == 1? Yes. Mutual Recursion occurs when two routines call each
other.
Dr. Gamal Tharwat

Dr. Gamal Tharwat

fib(1) = 1;
return fib(1);
fib(0):
0 == 0 ?
fib(0) = 0;
Yes.
A B
return fib(0);
fib(2) = 1 + 0 = 1; A
return fib(2);
B
fib(4) = fib(3) + fib(2)
99 100
= 2 + 1 = 3;
return fib(4);
 Mutual Recursion Example Example Implementation
Problem: Determine whether a number, N, is odd or function Odd returnsa Boolean (n iot in Num)
if (n = 0) then
even. Odd returns FALSE
else
Odd returns Even (n - 1)
• If N is equal to 0, then n is even endif
• N is odd if N-1 is even endfunction //Odd

Dr. Gamal Tharwat

Dr. Gamal Tharwat

function Even returnsa Boolean (n iot in Num)
if (n = 0) then
Even returns TRUE
else
Even returns Odd (n - 1)
endif
endfunction //Even
101 102

Example : Towers of Hanoi Tower of Hanoi

How to solve the 4 pegs
Dr. Gamal Tharwat

Dr. Gamal Tharwat

• Only one disc could be moved at a time

• A larger disc must never be stacked above a
smaller one
• One and only one extra needle could be 103 104
used for intermediate storage of discs
 Tower of Hanoi Tower of Hanoi
The puzzle is well known to students of Computer Science since it
Recursive Solution for the Tower of Hanoi with algorithm appears in virtually any introductory text on data structures or
algorithms.
Let’s call the three peg Src(Source), Aux(Auxiliary) and st(Destination). A function solve with four arguments (number of disks) and three
pegs (source, intermediary and destination) could look like this.
1) Move the top N – 1 disks from the Source to Auxiliary tower

Dr. Gamal Tharwat

Dr. Gamal Tharwat

2) Move the Nth disk from Source to Destination tower Solve (N, Src, Aux, Dst)
3) Move the N – 1 disks from Auxiliary tower to Destination tower. If N is 0
Transferring the top N – 1 disks from Source to Auxiliary tower can
Exit
again be thought of as a fresh problem and can be solved in the same
manner. So once you master solving Tower of Hanoi with three disks, Else solve (N-1, Src, Dst, Aux)
you can solve it with any number of disks with the above algorithm. Move from Src to Dst
105
Solve(N -1 , Aux, Src, Dst) 106

Tower of Hanoi Tower of Hanoi

For N = 4 we get the following sequence
This actually serves as the definition of the function Solve. The
function is recursive in that it calls itself repeatedly with decreasing 1. Move from Src to Aux
values of N until a terminating condition (in our case N = 0) has been 2. Move from Src to Dst
met. To me the sheer simplicity of the solution is breathtaking. For 3. Move from Aux to Dst
4. Move from Src to Aux
N =3 it translates into
5. Move from Dst to Src
6. Move from Dst to Aux
Dr. Gamal Tharwat

Dr. Gamal Tharwat

1. Move from Src to Dst 7. Move from Src to Aux

2. Move from Src to Aux 8. Move from Src to Dst
3. Move from Dst to Aux 9. Move from Aux to Dst
4. Move from Src to Dst 10. Move from Aux to Src
5. Move from Aux to Src 11. Move from Dst to Src
6. Move from Aux to Dst 12. Move from Aux to Dst
7. Move from Src to Dst 13. Move from Src to Aux
14. Move from Src to Dst
107 15. Move from Aux to Dst 108
Of course "Move" means moving the topmost disk.
 Tower of Hanoi Tower of Hanoi
How many moves will it take to transfer n disks from the left post to the • Explicit Pattern
right post? • Number of Disks Number of Moves
1 1
2 3
• the recursive pattern can help us generate more numbers to find an 3 7
explicit (non-recursive) pattern. Here's how to find the number of moves 4 15
needed to transfer larger numbers of disks from post A to post C, 5 31

Dr. Gamal Tharwat

Dr. Gamal Tharwat

remembering that M = the number of moves needed to transfer n-1 disks
from post A to post C: • Powers of two help reveal the pattern:
• for 1 disk it takes 1 move to transfer 1 disk from post A to post C; • Number of Disks (n) Number of Moves
1 2^1 - 1 = 2 - 1 = 1
• for 2 disks, it will take 3 moves: 2M + 1 = 2(1) + 1 = 3 2 2^2 - 1 = 4 - 1 = 3
• for 3 disks, it will take 7 moves: 2M + 1 = 2(3) + 1 = 7 3 2^3 - 1 = 8 - 1 = 7
• for 4 disks, it will take 15 moves: 2M + 1 = 2(7) + 1 = 15 4 2^4 - 1 = 16 - 1 = 15
5 2^5 - 1 = 32 - 1 = 31
• for 5 disks, it will take 31 moves: 2M + 1 = 2(15) + 1 = 31 109 110
• for 6 disks... ?

Towers of Hanoi Towers of Hanoi

void hanoi(int from, int to, int num) int main() {
{ int num_disc; //number of discs
int temp = 6 - from - to; //find the temporary
//storage column
if (num == 1){ cout << "Please enter a positive number (0 to quit)";
cout << "move disc 1 from " << from cin >> num_disc;
<< " to " << to << endl;
}
while (num_disc > 0){
Dr. Gamal Tharwat

Dr. Gamal Tharwat

else {
hanoi(from, temp, num - 1); hanoi(1, 3, num_disc);
cout << "move disc " << num << " from " << from cout << "Please enter a positive number ";
<< " to " << to << endl;
hanoi(temp, to, num - 1); cin >> num_disc;
} }
} return 0;
}
111 112
 Towers of Hanoi Building Recursive Modules
int main() {
int num_disc; //number of discs
Summary
• Decide on the terminating condition
cout << "Please enter a positive number (0 to quit)";
cin >> num_disc;
• Decide the final actions when you terminate
• There may be none

Dr. Gamal Tharwat

Dr. Gamal Tharwat

while (num_disc > 0){
• If you are computing something, this usually starts a
hanoi(1, 3, num_disc);
cout << "Please enter a positive number ";
“ripple” of returned data
cin >> num_disc; • Decide how to take a step closer to terminating
} • think about how to make your original, complex
return 0;
problem simpler
}
113 • Decide how to call a “clone” of this module 114

• Decide what work to do at this step in recursion