Recursive Functions

 

Functions can be recursive, i.e. a function may call itself either directly or indirectly. For example:

 

// factorial function

fac(x)

{

    if (x <= 0)

        return(1);

    else

        return(x*fac(x-1));

}

 

Each invocation of a recursive function receives a private copy of its arguments and local variables.

 

An interesting example of recursion occurs in a solution to the classic problem of finding a root of a real valued function. A real number x that satisfies the equation f(x) = 0 is called a root of function f. Suppose that f is a real valued function and is continuous on the interval [a, b]. If f(a) and f(b) are of opposite sign, then the continuity of the function guarantees that it has a root in the interval [a, b].

 

The condition that f(a) and f(b) have opposite sign is equivalent to the product of f(a) and f(b) being negative. The method of bisection proceeds as follows. Let m be the midpoint of the interval. If f(m) is zero, a root has been found. If not, then either f(a) and f(m) are of opposite sign or f(m) and f(b) are of opposite sign. If the first case holds, f has a root in the interval [a, m], and the bisection process starts again for this interval. After each iteration, an interval is obtained that is half the length of the previous interval. When the interval is sufficiently small, the midpoint is taken as a root of f.

 

The SPL solution uses a small routine called froot that evaluates an arbitrary function at a specified point. Using recursion, the froot code is remarkably clear and concise:

 

/*

 *  feval evaluates a function f at value val, i.e. returns

 *        y = f(val). Function f must be passed in as a string,

 *        e.g. feval("sin", pi/2) returns 1.0.

 */

 

/* find root of function f over interval [a, b] */

froot(f, a, b, eps)

{

    local m;

 

    /* midpoint of interval [a, b] */

    m = (a + b) / 2.0;

 

    /* found root within tolerance */

    if (feval(f, m) == 0.0 || b - a < eps)

    {

        return(m)

    }

 

    /* left edge */  

    else if (feval(f, a) * feval(f, m) < 0.0)

    {

        return(froot(f, a, m, eps));  

    }  

 

    /* right edge */  

    else  

    {

        return(froot(f, m, b, eps));   

    }

}

 

 

The built-in FEVAL evaluates a function passed in as a string (the related EVAL function evaluates an expression as if it were typed as an expression directly at the command line) and the STRCAT function combines two or more strings.

 

As a test, let froot solve for the root of a fifth-degree polynomial p(x).

 

p(x)

{

    return(x^5 + x + 3.0);

}

 

Now,

 

froot("p", -2, 0, 1e-6) returns: -1.13299799

 

but

 

froot("p", -2, 0, 1e-7)

 

returns: p: Function Nested Too Deep

 

because too many nested calls to p were made in the froot function.

 

In general, a recursive algorithm will be slower (sometimes much slower) than the equivalent iterative algorithm. However, recursive solutions are often simpler and quite appropriate when the problem at hand is recursive in nature.