A function definition is recursive if the right side of the definition calls the function being defined.  For example, if n is a nonnegative integer, the factorial of n can be computed recursively by the rules


       n! = 1                if n = 0, and
       n! = n(n-1)!        if n > 0.


The first rule is the terminal case for this definition.  The second rule is the recursive case.  The Derive definition corresponding to the above rules is


       FACT(n) := IF(n = 0, 1, n·FACT(n - 1))


To be computable, recursive definitions must have one or more terminal case rules, and the recursive case rules must make finite progress toward the terminal cases.  The above definition for computing factorials is computable because


•        When the terminal case rule is applicable (i.e. when n=0), the recursion is terminated.  


•        When the recursive case rule is applicable (i.e. when n>0), the problem is reduced to one closer to the terminal case.


•        The terminal case is reached after a finite number of applications of the recursive case rule.


If x is an expression and n is a nonnegative integer, raising x to the n power can be computed recursively by the rules


       RAISE(x, n) = 1                        if n = 0, and
       RAISE(x, n) = x RAISE(x, n-1)        if n > 0.


If m and n are integers, the greatest common divisor (gcd) of m and n can be computed recursively by the rules


       GCD(m, n) = |m|                        if n = 0, and
       GCD(m, n) = GCD(n, |m-n|)        if n /= 0.


The recursion terminates because both arguments must become nonnegative after two recursions, and thereafter the second argument decreases toward the terminal case by at least 1 for each recursion.  It is also true that any integer that evenly divides m and n, also evenly divides n and |m - n|, including the greatest common divisor.  It is also true that the greatest common divisor of m and 0 is |m|.  


The speeds of FACT and ! are approximately proportional for large n, as are the speeds of RAISE, POWER, and ^.  Although built-in operators or functions are faster, recursively defined functions can be reasonably efficient as well.  The next example illustrates the importance of writing efficient definitions.


If n is a nonnegative integer, the nth Fibonacci number can be computed recursively by the rules


       FIB(n) = 0                        if n = 0,
       FIB(n) = 1                        if n = 1, and
       FIB(n) = FIB(n-1) + FIB(n-2)        if n > 1.


An iterative definition of FIB that implemented these rules was discussed using the ITERATE FunctionThe_ITERATE_Function.  The following recursive definition of FIB_SLOW is another way to implement this recurrence:


FIB_SLOW(n) := 
       IF(n < 2, n, FIB_SLOW(n - 1) + FIB_SLOW(n - 2))


The reason FIB_SLOW is so slow is because to compute FIB_SLOW(n), FIB_SLOW(n-2) is computed twice: once for FIB_SLOW(n) and once for FIB_SLOW(n-1).  Similarly, FIB_SLOW(n-3) is computed three times: once for FIB_SLOW(n-1) and once for each of the two computations of FIB_SLOW(n-2).  In general, FIB_SLOW(n-i) must be computed the ith Fibonacci number of times.  Thus the number of redundant calculations, and hence the time required to compute the nth Fibonacci number using FIB_SLOW increases rapidly (i.e. Fibonaccially!) with n.


Such redundant computation is typical for recursive definitions that naively implement recurrences, like Fibonacci, that are doubly recursive.  Note that the recurrences for factorial, raising to a power, and gcd were just singly recursive and so did not suffer such redundancy.


In the case of Fibonacci this inefficiency is easy to overcome:  Just define an auxiliary helper function that has extra accumulation arguments to retain previously computed values so that they do not have to be recomputed.  The main function then invokes this helper function with the appropriate starting arguments.


FIB_AUX(n, f1, f0) := 
       IF(n=0, f0, FIB_AUX(n - 1, f1 + f0, f1))


FIB_FAST(n) := FIB_AUX(n, 1, 0)


For additional examples of recursive functions, see the definition of POLY_DEGREE in the file MiscellaneousFunctions.mth144O15P or the definitions of SPHERICAL_BESSEL_J and SPHERICAL_BESSEL_Y in the file BesselFunctions.mth3JDX.V4.


Other Programming in DERIVEProgramming 

Created with the Personal Edition of HelpNDoc: Easily create Help documents