Re: Recursive Functions

From: Tim Woodall (google_at_woodall.me.uk)
Date: 10/29/03 

Date: 29 Oct 2003 05:27:39 -0800

Richard Heathfield <dontmail@address.co.uk.invalid> wrote in message news:<bnmmch$oe8$1@hercules.btinternet.com>...
> Glen Herrmannsfeldt wrote:
>
<snip>
> > However, requiring it as a recursive function does scream of homework. A
> > simple for loop should be easier and faster.
>
> Hmmm. I raised 7 to the power 7777 using recursion and iteration. (Since the
> result occupies over 6500 decimal digits, I won't display it here!)
>
> The recursive calculation took 0.22 seconds, and the iterative version 1.06
> seconds - almost five times slower. Perhaps you could demonstrate an
> iterative version that can hold a candle to the recursive technique?
I'm surprised there is much if any difference:

long mpow(long x, long e)
{
    long r=1;

    while(e)
    {
        if(e&1)
            r*=x;
        x*=x;
        e>>=1;
    }
    return r;
}

Its fairly trivial to remove one multiplication at the cost of n if
tests (where n is the number of bits in e) and one multiplication can
become an assignment but other than that I don't think fewer
multiplications are possible using the square and multiply idiom. IIRC
Knuth goes into this in some detail and mentions some exponents where
this idiom does not use the minimum possible number of
multiplications. (e=15 being the smallest which can be evaluated as
mpow(mpow(x,3),5))

(Getting very OT now. squaring is particularly fast when very big
number are involved where FFT techniques become "efficient")

Tim.

Relevant Pages

  • Re: Any use for recursion?
    ... better done as a recursive function? ... ridiculous overhead in terms of execution speed and stack usage. ... that putchar is routed into a communications link that's running at 1 ... try writing that in a loop and making it easy to understand. ...
    (comp.programming)
  • RE: Recursive function help
    ... You could use a single query and return all employees sorted in to levels and use nested do while loops or a recursive function. ... > Microsoft VBScript runtime error '800a01fb' ... > Function GetParents() ...
    (microsoft.public.inetserver.asp.general)
  • Re: Iteration in lisp
    ... In Common Lisp, always prefer a loop where practical unless you know ... recursive function can run out of stack since CL does not guarantee ... Even if you have tail recursion, you are still wasting productivity by ...
    (comp.lang.lisp)
  • Re: Iteration in lisp
    ... If the recursive function defines a iterative process, it might be as good as a loop. ... If the loop defines a linear recursive process, it might be as bad as the recursive function. ...
    (comp.lang.lisp)