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.
  • merge sort & quick sort
  • Hirschberg's algorithm
  • multiplication of big integers
  • Strassen's matrix multiplication algorithm (not examinable)
  
  

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

linRecn( y ) does . . .

• s1(y)
  • s1(f(y))
    • s1(f(f(y))
      
      
      • . . .
        • until p( fⁿ ( y ) ) is true when . . .
          process   fⁿ ( 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

• T₀ = a
  
  

  --     recurrence relation

• T_n = b + T_n-1

Solution

--give proof by induction

• T_n = a + b * n

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

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

• expn(x, 0) = 1
  
  
• expn(x, -n) = 1 / expn(x, n)
  
  
• expn(x, 2n) = (expn(x, n))²
  
  
• 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:

• 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 [__________________].

• 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
  
  

• begin
  
  
  • while not p( x ) do
    
    
    • s1( x );
      
      
    • x := f( x )
      
      
  • end_while;
    
    
  • process x   -- base case
    
    
• end wasRec2
  
  

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

binRecn( y ) does . . .

• s1( y )
  • s1( f( y ) )
    • . . .
      • process fⁿ( y )
    • . . .
  • s2( f( y ) )
    • . . .
  • s3( f( y ) )
• s2( y )
  • s1( g( y ) )
    • . . .
  • s2( g( y ) )
    • . . .
      • process g^m( y )
    • . . .
  • s3( g( y ) )
• s3( y )

Time Complexity of Binary Recursion, assuming that

• recursion stops at level `n',
  
  i.e. ( f | g )ⁿ ( y ) are the base cases
  
  
• p, process, f, g, s1, s2, s3, take constant (or bounded) time
  
  

then

• T₀ = b

  --     recurrence relation

• T_n = a + 2 * T_n-1
  
  

Solution

• T_n = (a+b)*2ⁿ - 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

[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.