Recursion
Recursion
An algorithm is called recursive when it builds upon itself
Single recursion
For example, defining the function xn
Functions are defined recursively
1 khi n 0
x
n
n 1
x x khi n 1
Recursive algorithm
function power (x, n)
begin
if (n=0) then power = 1
else ham_mu = x * power(x, n-1)
endif
end 2
Recursion
Multiple recursion
A recursive definition can have more than one
recursive call
For example
Definition of Fibonacci sequence
F0 = 1, F1 = 1
Fn = Fn-1 + Fn-2
Algorithm
function fib(n)
begin
if ((n=0) or (n=1)) then fib = 1
else fib = fib(n-1) + fib(n-2)
endif
end 3
Recursion
Mutual recursion
Definitions are said to be mutual recursion, if they
depend on each other
For example
Definition of even/odd numbers
true if n 0 false if n 0
even(n) odd (n)
odd (n 1) else even(n 1) else
Algorithm
function even (n) function odd (n)
begin begin
if (n=0) then even = true if (n=0) then odd = false
else even = odd(n-1) else odd = even(n-1)
endif endif
end end 4
Recursion
Nested recursion
Definitions are called recursively nested
For example
Definition of Ackermann function
n 1 if m 0
A(m, n) A(m 1,1) if m 0, n 0
A(m 1, A(m, n 1)) else
Algorithm
function (m, n)
begin
if (m=0) then Ackermann = n+1
else if (n=0) Ackermann = Ackermann(m-1,1)
else Ackermann = Ackermann(m-1, Ackermann(m, n-1))
endif
endif 5
end
Design of recursive algorithm
Principle
We need to have
some cases where the solution is determined – “simple
cases”: the stopping cases of the recursion
a way to move from a “complex case” to a “simple case”
Difficulty
It is guaranteed that the recursion will stop when it
reaches a known solution
Functions must be defined across the entire data domain
Solution
The sequence of consecutive values of the called
parameters must vary monotonically and reach a value
for which the corresponding solution has been
determined
6
Design of recursive algorithm
Example 1
The following algorithm checks whether a is a
divisor of b
function divisor (a, b) // assume a>0, b>0
begin
if (a b) then
if (a=b) divisor = true
else divisor = false
endif
else divisor=divisor(a, b-a)
endif
end
The sequence of values b, b-a, b-2a… continuously
decreases until ab then it will stop, the case has
been determined 7
Design of recursive algorithm
Example 2
Algorithm
function syracuse (n)
begin
if (n=0 or n=1) then syracuse = 1
else
if (n mod 2 = 0) syracuse = syracuse(n/2)
else syracuse = syracuse(3*n+1)
endif
endif
end
Clearly defined algorithms
Does the algorithm stop?
8
Halting Problem
Unable to determine halting (1)
Problem
Is it possible to build a tool that automatically checks
whether an algorithm P can stop when executing on a
dataset D?
Inputs
Algorithm P
Data set D
Outputs
true, if algorithm P stops on data set D
false, otherwise
9
Halting Problem
Unable to determine halting (2)
Suppose there exists a program terminate that
automatically checks the termination of an algorithm
We build the following program Q basing on terminate
program Q
begin
result = terminate(Q)
while (result = true)
wait(1 minute)
endwhile
end
The stopping problem is indeterministic!
10
Order of recursive calls
Give the results of the following two algorithms
T(n) // n 0 G(n) // n 0
begin begin
if (n=0) then do nothing if (n=0) then do nothing
else else
T(n-1) print(n) //print n
print(n) //print n G(n-1)
endif endif
end end
Recursive algorithm to print the corresponding
binary sequence of an integer
11
Hanoi Tower (1)
There are 3 piles A, B and C. Each pile can
stack discs of different sizes, according to
the rule that larger disks must be below
smaller ones. The task is to move n discs
on pile A to pile C with the following
conditions:
Only one disc can be transferred at a time.
There is never a situation where a large disc is
stacked on top of a small disc.
Use one pile as an intermediate pile when
moving disc.
12
Hanoi Tower (2)
Assume
We solved the problem with n-1 disks
Principle
To move n disks from pile A to pile C, do
Move n-1 smaller disks from pile A to pile B
Move the largest disk from pile A to pile C
Move n-1 smaller disks from pile B to pile C
Algorithm
Hanoi(n, A, B, C)
begin
if (n=1) then move the large disk from pile A to pile C
else Hanoi(n-1, A, C, B)
Move the large disk from pile A to pile C
Hanoi(n-1, B, A, C)
endif 13
end
Hanoi Tower (3)
Evaluating complexity
Calculating the number of disk moves
1 if n 1
C n
C n 1 1 C n 1 else
1 if n 1
C n
2C n 1 1 else
C(n) = 2n -1
14
Recursion cost
Function call cost 1. Save context
2. Create a stack to store the
parameters, return address, …
…
f(x, y, z) 3. Go to function
…
4. Get from stack
5. Implementation
f(a, b, c)
… 6. Create a stack containing
end the returned result
7. Return to function call location
8. Get result from stack
15
9. Restore context
Recursion cost
Example
factorial(n)
factorial(n) begin
begin if (n = 1) then
factorial = 1 factorial = 1
for i = 2 to n else
factorial = factorial * i factorial = n * factorial(n-1)
endfor endif
end end
n-1 multiplication n-1 multiplication
n assignment n assignment
n assignment (loop) n-1 subtraction (calculate n-1)
n-1 increment by 1 (loop) n comparisons
n comparisons n function calls
Recursion cost is large due to function calls 16
Recursion elimination
Converting a recursive algorithm into an
equivalent algorithm that does not contain
recursive calls
Using loops
Two cases of single recursion
Tail recursion
An algorithm is said tail recursion if it does not contain any
processing after the recursive call.
Non-tail recursion
An algorithm is said to be non-tail recursion if it contains
processing after the recursive call.
17
Recursion elimination
Tail recursion
General diagram of tail recursion
P(U)
P'(U)
begin
begin
if C then
while C do
D
D
P((U))
U = (U)
else
endwhile
T
T
endif
end
end
U: list of parameters
C: condition depending on U
D: processing of the algorithm
(U): represents the parameter transformation
18
T: stop processing
Recursion elimination
Tail recursion
Eliminate the recursion of the following algorithm
bsearch(X, A, l, r)
begin
if (l r ) then
m = (l+r)/2
if (X = A[m]) then bsearch = m; return
else if (X < A[m]) then bsearch = bsearch(X, A, l, m-1)
else bsearch = bsearch(X, A, m+1, r)
endif
endif
else
bsearch = 0
endif
end
19
Recursion elimination
Tail recursion
Equivalent iterative algorithm
bsearch' (X, A)
begin
l=1
r=n
while (l r ) do
m = (l+r)/2
if (X = A[m]) then bsearch' = m; return
else if (X < A[m]) then r = m-1
else l = m+1
endif
endif
endwhile
bsearch' = 0
end
20
Recursion elimination
Non-tail recursion
It is important to memorize the context of the recursive
call
Typically the parameters of a recursive call
Use stack structure to store context
Stack operations
create
isempty
push
pop
top
Two ways to eliminate non-tail recursion
21
Recursion elimination
Non-tail recursion
Method 1 Q'(U)
begin
Q(U) create(S)
begin while C(U) do
if C(U) then B(U)
B(U) push(S, U)
Q((U)) U = (U)
E(U) endwhile
else T(U)
T(U) while not isempty(S) do
endif U = top(S)
end E(U)
pop(S)
endwhile
end
22
Recursion elimination
Non-tail recursion
Method 1
Illustration
Call Q(U0)
C(U0) is correct
B(U0)
Let Q((U0))
C((U0)) is correct Call Q'(U0) ?
B((U0))
Let Q(((U0)))
C(((U0))) is incorrect
T(((U0)))
E((U0))
E(U0)
23
Recursion elimination
Non-tail recursion
Method 1 T'(n) // n 0
Example begin
create(S)
if (n=0) then do nothing
T(n) // n 0 else
begin while (n>0) do
if (n=0) then do nothing push(S, n)
else n = n-1
T(n-1) endwhile
print(n) //print n while (not isempty(S)) do
endif n = top(S)
end print(n) //print n
pop(S)
endwhile
endif
24
end
Q'(U)
Recursion elimination begin
create(S)
push(S, (newcall, U))
Non-tail recursion while not isempty(S) do
Method 2 (state, V) = top(S)
pop(S)
if (state = newcall) then
Q(U) U=V
begin if C(U) then
if C(U) then B(U)
B(U) push(S, (end, U))
Q( (U)) push(S, (newcall, (U)))
E(U) else T(U)
else endif
T(U) endif
endif if (state = end) then
end U=V
E(U)
endif
endwhile
25
end
Recursion elimination
Non-tail recursion
Method 2
Illustration
Call Q(U0)
C(U0) is correct
B(U0)
Let Q((U0))
C((U0)) is correct Call Q'(U0) ?
B((U0))
Let Q(((U0)))
C(((U0))) is incorrect
T(((U0)))
E((U0))
E(U0)
26
Recursion elimination
T'(n)
Non-tail recursion begin
create(S)
Method 2
push(S, (newcall, n))
Example
while not isempty(S) do
(state, k) = top(S)
pop(S)
T(n) // n 0 if (state = newcall) then
begin if (k>0) then
if (n=0) then do nothing push(S, (end, k))
else push(S, (newcall, k-1))
T(n-1) else do nothing
print(n) //print n endif
endif endif
end if (state = end) then
print(k)
endif
endwhile
end 27
Recursion elimination
Iterative algorithms are often more efficient
Recursive algorithms are often easier to build
Most compilers can automatically eliminate tail
recursion
It is always possible to eliminate the recursion of
an algorithm
28
Exercises
Problem 1
Definition of Fibonacci sequence
Fib0 = 1, Fib1 = 1
Fibn = Fibn-1 + Fibn-2
Tasks
1. Build a recursive algorithm to calculate Fib(n)
2. Prove that the complexity (in terms of number of additions) of
the algorithm is (2n/2 )
3. Build an algorithm calculating the pair (Fib(n), Fib(n-1)) with n>0
4. Use the algorithm in question 3 to build a new algorithm to
calculate Fib(n)
5. Evaluate the complexity (by number of additions) of the above
algorithm
29
Exercises
Problem 2
The greatest common divisor of two positive integers is
defined as follows
if x = y then usc(x, y) = x
if x > y then usc(x, y) = usc(x-y, y)
if x < y then usc(x, y) = usc(x, y-x)
1. Build a recursive algorithm to calculate the greatest
common divisor of two positive integers
2. Eliminate the recursion
Problem 3
1. Build a recursive algorithm to print the corresponding
binary sequence of an integer
2. Eliminate the recursion
30