[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 Code function linRec( x ) { if( p( x ) ) // base case process( x ); else // recursive case { s1( x ); linRec( f(x) ); s2( x ); } }//linRec linRec('y'); // initial call of linRec() ©L.Allison. 2000 Output Needs JavaScript1.1+, Netsc@pe4.7+ Exercise: Write a non-recursive routine that behaves in exactly the same way as linRec - L.Allison, Computer Science and SWE, Monash University, Australia

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

• T0 = a

 --     recurrence relation
• Tn = b + Tn-1

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
• process x   -- base case

• 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
• process x   -- base case

• 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

• s1( x );

• x := f( x )

• 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
• process x   -- base case

• 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 ) )
• . . .
• process fn( y )
• . . .
• s2( f( y ) )
• . . .
• s3( f( y ) )
• s2( y )
• s1( g( y ) )
• . . .
• s2( g( y ) )
• . . .
• process gm( 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

• T0 = b  --     recurrence relation
• Tn = a + 2 * Tn-1

 --give proof by induction

Solution

• Tn = (a+b)*2n - a

### nAryRecn( x )

• begin
• if p( x ) then
• process x   -- base case

• else
• for i from g(x) to h(x) do

• if constraints( x, i ) then
• nAryRecn ( f ( x, i ) )

• end_if
• end_for
• end_if
• end nAryRec   -- general form
 var maxDepth = , maxWidth = ; Code function NR(depth, str) { var iter; if( depth >= maxDepth ) // base case print(str + '.base\n'); else // general case { for( iter = 1; iter <= maxWidth; iter++ ) NR(depth+1, str + '.' + iter); } }//f NR(1, 'trace = '); // initial call of NR() ©L.Allison. 2000 Output You need a browser such as Netscape4.7 or later with JavaScript1.1 or later turned ON! - L.Allison, Computer Science, Monash University, Australia

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

## Recursion:   Summary

• 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, 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).