Recursive Functions

D

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!
 
E

Eric Sosman

dmattis said:
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.
 
S

Sheldon Simms

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.programming, 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.
 
J

James Hu

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
 
R

Richard Heathfield

dmattis said:
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 ;}
 
G

Glen Herrmannsfeldt

Sheldon Simms said:
This question is off topic here. I would suggest you try
posting in comp.programming, 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
 
E

E. Robert Tisdale

dmattis said:
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;
}
 
J

Julian V. Noble

dmattis said:
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
(e-mail address removed)
^^^^^^^^
http://galileo.phys.virginia.edu/~jvn/

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

Julian V. Noble

Glen said:
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
(e-mail address removed)
^^^^^^^^
http://galileo.phys.virginia.edu/~jvn/

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

Eric Sosman

E. Robert Tisdale said:
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.
 
J

Jarno A Wuolijoki

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

Well, either that or the interpretation of "suitable base case to
stop the recursion" might need some clarification.
 
A

Arthur J. O'Dwyer

Well, either that or the interpretation of "suitable base case to
stop the recursion" might need some clarification.

In particular, where is it guaranteed that the base case (n <= 0)
is ever reached? I admit I'm not conversant in the details of
C floating point, but it seems like an unwarrantedly dubious
assumption to be making. What's to say that 1e-100/2 != 1e-100 ?

-Arthur
 
I

Irrwahn Grausewitz

Arthur J. O'Dwyer said:
In particular, where is it guaranteed that the base case (n <= 0)
is ever reached? I admit I'm not conversant in the details of
C floating point, but it seems like an unwarrantedly dubious
assumption to be making. What's to say that 1e-100/2 != 1e-100 ?

Err, n is of type unsigned int, thus all divisions are integer
divisions...

Regards
 
A

Arthur J. O'Dwyer

Err, n is of type unsigned int, thus all divisions are integer
divisions...

Oops. I was thrown by the use of 'double' everywhere else.
Seems silly to use 'double' for the first operand if you're only
going to allow positive integers for the second operand...
plus, in this case Tisdale's solution does exponentially more
work than it really has to. There should be only one call
to Power() within the function itself.

(Proper solution left as an exercise for the OP.)

-Arthur
 
C

Christian Bau

"Arthur J. O'Dwyer said:
Oops. I was thrown by the use of 'double' everywhere else.
Seems silly to use 'double' for the first operand if you're only
going to allow positive integers for the second operand...
plus, in this case Tisdale's solution does exponentially more
work than it really has to. There should be only one call
to Power() within the function itself.

I think it does more than exponentially more work than needed...

What is n - n/2 if n is equal to 1?
 
P

Peter Nilsson

Irrwahn Grausewitz said:
Err, n is of type unsigned int, thus all divisions are integer
divisions...

The floating point reference is a red herring. Think about what the
function will do when n is 1.
 
G

Glen Herrmannsfeldt

James Hu said:
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).

The algorithm described, in non-recursive form, is commonly used in
languages that supply an integer exponentiation operator. A table
dimensioned INT_MAX-INT_MIN+1 will take up a lot of memory.
<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>

Yes, he should do that.

-- glen
 
J

James Hu

The algorithm described, in non-recursive form, is commonly used in
languages that supply an integer exponentiation operator.

Yes, but those typically take a floating point type for the x argument,
and an int type for the n argument.
A table dimensioned INT_MAX-INT_MIN+1 will take up a lot of memory.

That is an imaginative approach, but not what I had in mind.

#include <stdint.h>

static int8_t hbit[256] =
{-1
,0
,1,1
,2,2,2,2
,3,3,3,3,3,3,3,3
,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4
,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5
,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6
,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6
,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
};

int int_pow(int x, uint8_t n)
{
int t = 1;
if (n == 0) return 1;
if (x == 0) return 0;
switch (hbit[n]) {
case 7: if (n & 1) t *= x; n >>= 1; x *= x;
case 6: if (n & 1) t *= x; n >>= 1; x *= x;
case 5: if (n & 1) t *= x; n >>= 1; x *= x;
case 4: if (n & 1) t *= x; n >>= 1; x *= x;
case 3: if (n & 1) t *= x; n >>= 1; x *= x;
case 2: if (n & 1) t *= x; n >>= 1; x *= x;
case 1: if (n & 1) t *= x; n >>= 1; x *= x;
default: if (n & 1) t *= x;
}
return t;
}

-- James
 
I

Irrwahn Grausewitz

Christian Bau said:
I think it does more than exponentially more work than needed...

What is n - n/2 if n is equal to 1?

Arrgh, Trollsdale did it again!

And on first glance I thought he actually posted valid code; stupid me.
 
M

Marcus Lessard

Maybe it's just me but doesn't the contrived nature of the function scream
out "Homework Assignment?" Maybe I'm missing something but I just can't see
why you'd ever want to compute this value..

Alea iacta

"Julian V. Noble"
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top