Recursive Functions

[dmattis]

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!

[Sheldon Simms]

On Mon, 27 Oct 2003 09:54:05 -0800, dmattis wrote:

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?

This question is off topic here. I would suggest you try
posting in comp.programmin g, but I can't actually figure out
what you want. You've described the algorithm completely,
what more do you want?

-Sheldon

p.s. I'm hoping that what you want isn't for someone to simply
do your homework for you.

[James Hu]

On 2003-10-27, dmattis <dm*****@yahoo. com> wrote:

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?

This is not a C question... but the C answer is use pow() (unless you
are purposefully avoiding floating point, in which case a table lookup
is in order).

<DYOHW> Rewrite your word problem into a recurrence relationship. Use
induction to prove this recurrence correctly calculates x to the nth
power. It should be obvious at that point what your function should
look like and what your base case is. </DYOHW>

-- James

[Eric Sosman]

dmattis wrote:

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?

This seems a fairly clear description of the procedure,
assuming `n' is a non-negative integer. (If `n' can be
negative the problem is harder; if `n' can be a non-integer
problem is much harder.) What problem are you having with
it? Perhaps if you'd show us what you've written thus far,
someone will be able to help.

--
Er*********@sun .com

[Richard Heathfield]

dmattis wrote:

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?

/*
untested,
unreadable,
unambitious,
unenthusiastic
*/
#define k \
unsigned char
k Power(k x,k
n){k r=1;if(n
){if(1==n){r=
x;}else{k t =
Power(x,n>>1)
;if(1&n){r=x;
}r *= t*t; }}
return r ;}

--
Richard Heathfield : bi****@eton.pow ernet.co.uk
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R answers, C books, etc: http://users.powernet.co.uk/eton

[Glen Herrmannsfeldt]

"Sheldon Simms" <sh**********@y ahoo.com> wrote in message
news:pa******** *************** *****@yahoo.com ...

On Mon, 27 Oct 2003 09:54:05 -0800, dmattis wrote:

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?

This question is off topic here. I would suggest you try
posting in comp.programmin g, but I can't actually figure out
what you want. You've described the algorithm completely,
what more do you want?

Well, to help make it on topic, I sometimes notice C's lack of an integer
power function, such as that described. (Though I believe that it works
better as an iterative function than a recursive function.) Sometimes I use
an SQ macro, which squares an expression through mutliplication. If the
expression is more than a single variable, I hope that the compiler does
common subexpression elimination.

-- glen

[Julian V. Noble]

dmattis wrote:

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!

Here is tested C code for raising an integer to an integer power,
recursively. (I hope this isn't a HW assignment but a legitimate
query.)

// Recursive raise integer to integer power
//
// If j is even, return (i^2)^(j/2), else return i * (i^2)^(j/2)
//
// ----------------------------------------------------
// (c) Copyright 2003 Julian V. Noble. //
// Permission is granted by the author to //
// use this software for any application pro- //
// vided this copyright notice is preserved. //
// ----------------------------------------------------
#include <math.h>
#include <stdio.h>

int power( int i, int j ); // prototype

int main( void )
{
int a;
int b;

printf("What are m and n? ");
scanf(" %d", &a);
scanf(" %d", &b);

printf( " %d\n", power(a,b) ) ;

return 0;
}

int power( int i, int j )
{
int k;
if (j==0) // i^0 = 1
{ return 1;
}

if (j & 1) // odd?
k = i;
else // even?
k = 1;

return k * power( i*i, j/2);
}

--
Julian V. Noble
Professor Emeritus of Physics
jv*@spamfree.vi rginia.edu
^^^^^^^^
http://galileo.phys.virginia.edu/~jvn/

"Science knows only one commandment: contribute to science."
-- Bertolt Brecht, "Galileo".

[Julian V. Noble]

Glen Herrmannsfeldt wrote:

"Sheldon Simms" <sh**********@y ahoo.com> wrote in message
news:pa******** *************** *****@yahoo.com ...

On Mon, 27 Oct 2003 09:54:05 -0800, dmattis wrote:

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?

This question is off topic here. I would suggest you try
posting in comp.programmin g, but I can't actually figure out
what you want. You've described the algorithm completely,
what more do you want?

Well, to help make it on topic, I sometimes notice C's lack of an integer
power function, such as that described. (Though I believe that it works
better as an iterative function than a recursive function.) Sometimes I use
an SQ macro, which squares an expression through mutliplication. If the
expression is more than a single variable, I hope that the compiler does
common subexpression elimination.

-- glen

You are correct in saying that the iterative is probably better than the
recursive version. If anyone is interested I'll post my iterative version.

--
Julian V. Noble
Professor Emeritus of Physics
jv*@spamfree.vi rginia.edu
^^^^^^^^
http://galileo.phys.virginia.edu/~jvn/

"Science knows only one commandment: contribute to science."
-- Bertolt Brecht, "Galileo".

[E. Robert Tisdale]

dmattis wrote:

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?

double Power(double x, unsigned int n) {
return (0 < n)? Power(x, n/2)*Power(x, n - n/2): 1.0;
}

[Eric Sosman]

"E. Robert Tisdale" wrote:

dmattis wrote:

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?

double Power(double x, unsigned int n) {
return (0 < n)? Power(x, n/2)*Power(x, n - n/2): 1.0;
}

I confess that I considered suggesting this method, but
then decided that wanton cruelty was not (yet) justified.

--
Er*********@sun .com