----- NEEDS JAVASCRIPT ON. -----
[Subject home ],
[FAQ ],
[progress ],
Bib' ,
Alg's ,
C ,
Java
- L.A. ,
Friday, 03-May-2024 11:16:24 AEST
Instructions :
Topics discussed in these lecture notes are examinable
unless otherwise indicated.
You need to follow instructions,
take more notes &
draw diagrams especially as [indicated] or
as done in lectures,
work through examples, and
do extra reading.
Hyper-links not in [square brackets] are mainly for revision,
for further reading, and for lecturers of the subject.
Recursion
(more / revision):
Introduction.
Linear
recursion
Binary
recursion
n-ary
(general) recursion, e.g. permutations
Mutual recursion,
e.g. parsing
Recursion in the divide & conquer paradigm, e.g.
You need a browser such as Netscape3 or
later and JavaScript turned ON !
Also try deleting s1(x)
, or s2(x)
, or both.
linRecn( y )
does . . .
s1(y)
s1(f(y))
s1(f(f(y))
. . .
until p( fn ( y ) ) is true
when . . .
process fn ( y )
. . .
s2(f(f(y))
s2(f(y))
s2(y)
Time Complexity of
Linear Recursion
assuming that
p(x), f(x), s1(x), s2(x), process(x)
each take constant (or bounded) time
then
Solution
--give proof by induction
Tn = a + b * n
Linear Recursion
Beware , the time-complexity is linear
in what? . . .
e.g. define expn(x,n) = xn :
expn(x, 0) = 1
expn(x, -n) = 1 / expn(x, n)
expn(x, 2n) = (expn(x, n))2
expn(x, 2n+1) = expn(x, 2n) * x
expn is linear recursive
BUT its time-complexity is linear in the length of n,
the numbers of bits in n ,
i.e. O(log(n))-time.
Linear Recursion
[lecturer: give non-recursive version of linRec; class: take notes!]
Tail Recursion:
a special case when s2( x ) is absent:
tailRecn ( x )
begin
if p( x ) then
else -- assert not p( x )
s1( x );
tailRecn (f ( x ) )
end_if
end tailRecn --
Called tail recursion because [__________________].
wasRec ( x )
begin
start:
if p( x ) then
else -- assert not p( x )
s1( x );
x := f( x );
goto start -- !
end_if
end wasRec
Can replace goto with a loop . . .
wasRec2 ( x )
begin
while not p( x ) do
end_while;
process x -- base case
end wasRec2
NB. transformation is only this simple for tail recursion
because [________________].
binRecn ( x )
begin
if p( x ) then
else -- assert not p( x )
s1( x );
binRecn ( f ( x ) );
s2( x );
binRecn ( g ( x ) );
s3( x )
end_if
end binRec
[lecturer: draw tree of calls; class: take notes!]
binRecn( y )
does . . .
s1( y )
s1( f( y ) )
s2( f( y ) )
s3( f( y ) )
s2( y )
s1( g( y ) )
s2( g( y ) )
s3( g( y ) )
s3( y )
Time Complexity of
Binary Recursion ,
assuming that
recursion stops at level `n',
i.e. ( f | g )n ( y ) are the base cases
p, process, f, g, s1, s2, s3, take constant (or bounded) time
then
--give proof by induction
Solution
begin
if p( x ) then
else
for i from g(x) to h(x) do
if constraints( x, i ) then
end_if
end_for
end_if
end nAryRec -- general form
You need a browser such as Netscape3 or
later and JavaScript turned ON !
[lecturer: discuss at least one of the
combinatorial
problems. class: take notes! ]
A powerful technique
giving short algorithms for difficult problems;
it is often easy to prove the algorithms correct.
Linear recursion
~ iterative, non-recursive, but
must introduce a stack to remove rec'n in general ,
unless s2(x) is absent.
Binary recursion
beware - may take exponential time
(but not necessarily)
must introduce a stack to remove recursion.
Prepare:
Design Techniques, paradigms, general problem solving strategies.
© L.Allison ,
Friday, 03-May-2024 11:16:24 AEST
users.monash.edu/~lloyd/tilde/CSC2/CSE2304/Notes/22recursion.shtml
Computer Science,
Software Engineering,
Science (Computer Science).