[Subject home], [FAQ], [progress],   Bib', Alg's,  C , Java - L.A., Sunday, 28-Nov-2021 05:04:04 AEDT
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.

  var maxDepth =  ;   // Linear recursion
 
C
o
d
e

©
L
.
A
l
l
i
s
o
n
.

2
0
0
0


O
u
t
p
u
t

Also try deleting s1(x), or s2(x), or both.


linRecn( y ) does . . .

Time Complexity of Linear Recursion assuming that

then

Solution

 
©
L
.
A
l
l
i
s
o
n
Linear Recursion

Beware, the time-complexity is linear in what? . . .

e.g. define expn(x,n) = xn :

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

Tail Recursion:  a special case when s2( x ) is absent:

tailRecn( x ) wasRec( x ) Can replace goto with a loop . . .
wasRec2( x ) NB. transformation is only this simple for tail recursion because [________________].

binRecn( x )

[lecturer: draw tree of calls; class: take notes!]

binRecn( y ) does . . .

Time Complexity of Binary Recursion, assuming that

then

--give proof by induction

Solution

nAryRecn( x )

  var maxDepth = , maxWidth = ;
 
C
o
d
e

©
L
.
A
l
l
i
s
o
n
.

2
0
0
0


O
u
t
p
u
t

[lecturer: discuss at least one of the combinatorial problems. class: take notes!]

Recursion:   Summary

Prepare: Design Techniques, paradigms, general problem solving strategies.
© L.Allison, Sunday, 28-Nov-2021 05:04:04 AEDT users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/22recursion.shtml
Computer Science, Software Engineering, Science (Computer Science).