Improvinging recursive programs
Burstall and Darlington's 1977 paper (http://cafeen.nat.ku.dk/undervisning/2005e/224/papers/Burstall-1977-TransSystem.pdf) presents a system of rules for transforming programs described by recursive equations. The system of rules and the strategy described in the paper allows one to make very interesting changes (like increase in efficiency) to a program. As far as I understand it is possible to prove that the steps involved preserves the correctness of the program. The paper provides a set of examples to illustrate the point.

I have chosen to work through two of the examples illustrated in the paper: calculating Fibonacci numbers and calculating a table of factorials (upto the specified number).
Code snippet (I): Function for computing Fibonacci numbers 
	def fib(n):
	    if n == 0: return 0
	    if n == 1: return 1
	    return fib(n-1) + fib(n-2)
  Call tree
  
Code snippet (II): Function for tabulating Factorials upto n 
	def fact(n):
	    if n == 0: return 1
	    return n * fact(n-1)
	    
	def fact_table(n):
	    if n == 0: return [fact(0)]
	    table = fact_table(n-1)
	    table.insert(0, fact(n))
	    return table
  Call tree
  
Note: each rectangle is call to fact_table for specified number. Each elipse is a call to fact for the specified number.


Refactoring is the process of changing the software in such a way that the external behavior (of software) is not changed and yet it improves the internal structure (of software). Apart from possible renaming (variable or function names) there does not seem to be any 'code smell'.

Looking at the call tree shown on the right hand side for code snippet (I), in order to calculate fib(5): It is obvious that a lot of unnecessary computations are being performed. For larger n, the number of computations increases exponentially. Intution says that it does not have to be that way. The image shown on the right hand side for code snipped (I) shows (dotted area) the minimal number of computations to be performed for calculating fib(5).

Code snippet (II) and the call tree shown on its right hand side show a similar problem in the case of factorial table calculation.

Code smell taxonomy does not include the above wasted computations as a smell. To the best of my knowledge there is no technique prescribed in the refactoring catalog too. Is one supposed to rely just on intution and common sense hoping to find a way to remove this unwanted behavior?

Transformation of Code snippet (I)
Follows the sequence of steps involved in transforming program snippet (I) as per rules specified in the paper (mentioned above):

Following table shows the original code snippet (I) and the transformed code snippet (I):
Code snippet (I): Function for computing Fibonacci numbers 
	def fib(n):
	    if n == 0: return 0
	    if n == 1: return 1
	    return fib(n-1) + fib(n-2)
Transformed code snippet (I): (recursive) 
     def transformed_recursive_fib(n):
         if n == 0: return 0
         if n == 1: return 1
         def g(n):
            if n == 0: return (1,0)
            (u,v) = g(n-1)
            return (u+v, u)
         (u, v) = g(n-2)
         return u+v
Transformed code snippet (I): (iterative) 
     1. def transformed_fib(n):
     2. #{n ≥ 0 }
     3.    if n == 0: return 0
     4. # { n > 0 }
     5.    if n == 1: return 1
     6. # { n > 1 }
     7.    x, u, v= 0, 1, 0
     8. # { n > 1 AND x == 1 AND u(1) == 1 AND v(1) == 0 }
     9. # {P: 1 ≤ x ≤ n-2 AND u(x+1) = u(x) + v(x) _AND_ v(x+1)=u(x) }
    10.    while (x <= n-2):
    11.        previous_u = u
    12.        u = u+v
    13.        v = previous_u
    14.        x= x+1
    15. # {Q: x == n-2 AND {u(n-1) = u(n-2)+ v(n-2) _AND_ v(n-1) = u(n-2)} }
    16.    return u+v
    17. # { u(n-1)+v(n-1) = u(n-1) + u(n-2) }


Transformation of Code snippet (II)
Follows the sequence of steps involved in transforming program snippet (II) as per rules specified in the paper (mentioned above):

Following table shows the original code snippet (II) and the transformed code snippet (II):
Code snippet (II): Function for computing factorial table upto n 
    @ensure_nonnegative
    def fact(n):
        if n == 0: return 1
        return n * fact(n-1)
	    
    @ensure_nonnegative
    def fact_table(n):
        if n == 0: return [fact(0)]
        table = fact_table(n-1)
        table.insert(0, fact(n))
        return table
Transformed code snippet (II): (recursive) 
    @ensure_nonnegative
    def linear_recursive_factorial_list(n):
       if n == 0: return [1]
       def g(n):
           if n == 0: return (1, [1])
           (u, v) = g(n-1)
           v.insert(0, u)
           return ((n+1) * u, v)
       (u,v) = g(n-1)
       v.insert(0, u)
       return v
Transformed code snippet (II): (iterative) 
       @ensure_nonnegative
    1. def linear_factorial_list(n):
    2. # { n >= 0 }
    3.     if n == 0: return [1]
    4. # { n > 0 }
    5.     x, u, v = 1, 1, [1]
    6. # { x == 1 AND u == 1 AND v = [1] }
    7. # {P:  0 ≤ x > n AND u(x+1) = (x+1) * u(x) _AND_ v(x+1) = cons(u(x), v(x))}
    8.     while x < n:
    9.         v.insert(0, u)
   10.         u = (x+1) * u
   11.         x = x+1
   12. # {Q: x== n AND {u(n)= (n)* u(n-1) _AND_ v(n) = cons(u(n-1), v(n-1))} }     
   13.     v.insert(0, u)
   14. # {cons(u(n), v(n)) = cons(n * u(n-1), u(n-1)) }
   15.     return v


Here are few questions to consider: