473,883 Members | 1,787 Online

# Recursive Functions

I am trying to write a recursive version of Power(x,n) that works by
breaking n down into halves(where half of n=n/2), squaring
Power(x,n/2), and multiplying by x again if n was odd, and to find a
suitable base case to stop the recursion. Can someone give me an
example of this?

Thanks!
Nov 13 '05
64 7341
James Hu <jx*@despammed. com> wrote in message news:<Se******* *************@c omcast.com>...
On 2003-10-29, Tim Woodall <go****@woodall .me.uk> wrote:
Richard Heathfield <do******@addre ss.co.uk.invali d> wrote in message news:<bn******* ***@hercules.bt internet.com>.. .
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.

double ulpow (double x, unsigned long n)
{
double t = 1;

if (n & 1) t = x;
while (n >>= 1) {
x *= x;
if (n & 1) t *= x;
}
return t;
}

Am I missing something? Where did we add an additional test per
iteration?

You need more tests that that. but an extra
while(!(n&1)) {
n >>= 1;
x*=x;
}
might be sufficient to cover the cases where the least significant
bit of n isn't 1. But you need an extra test for n==0 otherwise my
while loop is infinite. but you can then drop your first if as it will
always be true.

I think I was probably wrong about needing all the extra test but I
was thinking of trying to do it all in one loop where you need a
if(t==1) t=x else t*=x;

Tim.
Nov 13 '05 #61
go****@woodall. me.uk (Tim Woodall) wrote in message news:<fa******* *************** ****@posting.go ogle.com>...
James Hu <jx*@despammed. com> wrote in message news:<Se******* *************@c omcast.com>...

double ulpow (double x, unsigned long n)
{
double t = 1;

if (n & 1) t = x;
while (n >>= 1) {
x *= x;
if (n & 1) t *= x;
}
return t;
}

You need more tests that that. [...]

Tim, I seem to be unable to find a case that causes the
above routine to misbehave. Could you give me a hint?

Thanks,

-- James
Nov 13 '05 #62
James Hu wrote:

go****@woodall. me.uk (Tim Woodall) wrote in message news:<fa******* *************** ****@posting.go ogle.com>...
James Hu <jx*@despammed. com> wrote in message news:<Se******* *************@c omcast.com>...

double ulpow (double x, unsigned long n)
{
double t = 1;

if (n & 1) t = x;
while (n >>= 1) {
x *= x;
if (n & 1) t *= x;
}
return t;
}

You need more tests that that. [...]

Tim, I seem to be unable to find a case that causes the
above routine to misbehave. Could you give me a hint?

This code avoids multiplying by unity if `n' is odd,
but still performs the "wasted" multiplication if `n' is
even. Consider the case for `n' equal to 2:

t = 1
if (n & 1) [false]
while (n >>= 1) [n <- 1, true]
x *= x
if (n & 1) [true]
t *= x [t <- 1 * x, wasted]
while (n >>= 1) [n <- 0, false]

The most convenient way to avoid the wastage may be
to use two loops in sequence. Just typed in, untested:

if (n == 0)
return 1;
while (!(n & 1)) {
x *= x;
n >>= 1;
}
t = x;
while (n >>= 1) {
x *= x;
if (n & 1)
t *= x;
}

--
Er*********@sun .com
Nov 13 '05 #63
Eric Sosman <Er*********@su n.com> wrote in message news:<3F******* ********@sun.co m>...
James Hu wrote:
Tim, I seem to be unable to find a case that causes the
above routine to misbehave. Could you give me a hint?

This code avoids multiplying by unity if `n' is odd,
but still performs the "wasted" multiplication if `n' is
even.

I see now. Thanks!

-- James
Nov 13 '05 #64
Richard Heathfield wrote:
Well, I was indeed comparing different algorithms. My mistake was to label
them "recursive" and "iterative" . It was in fact the difference between
square-and-multiply and multiply-n-times that I was attempting to
highlight, and I made a complete pig's breakfast of it by attaching
informal labels ("recursive" and "iterative" ) to these algorithms instead
of spelling out precisely what I mean. Silly of me.

When tail-recursion optimization can be performed on a recursive
algorithm, it can be written iteratively.

AFAIU, in such cases, the iterative version will perform better than
the recursive version.

Nov 13 '05 #65

This thread has been closed and replies have been disabled. Please start a new discussion.

### Similar topics

 4 1924 by: Magnus Lie Hetland | last post by: Hi! I've been looking at ways of dealing with nested structures in regexps (becuase I figured that would be faster than the Python parsing code I've currently got) and came across a few interesting things... First there is this, mentioning the (?) and (?<-DEPTH>) constructs of the .NET regexp matcher: http://www.rassoc.com/gregr/weblog/archive.aspx?post=590 7 567 by: Jon Slaughter | last post by: #pragma once #include class empty_class { }; template class RDES_T { 7 6134 by: Aloo | last post by: Dear friends, If we declare a recursive function as 'inline' then does it actually convert to an iterative form during compilation ( the executable code is iterative)? Is it possible ? Please reply. 9 16858 by: Csaba Gabor | last post by: Inside a function, I'd like to know the call stack. By this I mean that I'd like to know the function that called this one, that one's caller and so on. So I thought to do: