473,883 Members | 1,787 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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 (?<DEPTH>) 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 <vector> class empty_class { }; template <int _I, int _J, class _element, class _property> 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: <script type='text/javascript'> function myFunc(lev) { // if (lev) return myFunc(lev-1); var aStack=; nextFunc = arguments.callee;
41
3411
by: Harry | last post by:
Hi all, 1)I need your help to solve a problem. I have a function whose prototype is int reclen(char *) This function has to find the length of the string passed to it.But the conditions are that no local variable or global variable should be used.I have to use recursive functions.
5
4953
by: Digital Puer | last post by:
I got this on an interview: Is it possible to write inline recursive functions? I said yes, but there is no guarantee that the compiler will definitely inline your code even if you write "inline". Is this a right answer? It seems to be independent of whether or not the function is recursive. Another question: how can you tell if the compiler has inlined your
10
2579
by: AsheeG87 | last post by:
Hello Everyone! I have a linked list and am trying to include a recursive search. However, I am having trouble understanding how I would go about that. I don't quite understand a recursive search....would any of you be so kind to explain it to me...maybe include some examples. I would GREATLY appreciate it!!!
9
2649
by: pereges | last post by:
Hello I need some ideas for designing a recursive function for my ray tracing program. The idea behind ray tracing is to follow the electromagnetic rays from the source, as they hit the object.The object is triangulated. The rays can undergo multiple reflections, diffractions etc of the same object i.e. a ray hits a surface of the object, undergoes reflection resulting in a reflected ray which can again hit a surface, corner or edge...
3
4255
by: from.future.import | last post by:
Hi, I encountered garbage collection behaviour that I didn't expect when using a recursive function inside another function: the definition of the inner function seems to contain a circular reference, which means it is only collected by the mark-and-sweep collector, not by reference counting. Here is some code that demonstrates it: === def outer():
6
9624
KevinADC
by: KevinADC | last post by:
This snippet of code provides several examples of programming techniques that can be applied to most programs. using hashes to create unique results static variable recursive function serialization The code itself generates a list of strings comprised of random numbers. No number will be repeated within a string, and no string will be repeated within the list of strings. Following the code is a brief discussion of how the above...
0
9944
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
11153
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
0
10757
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
1
10860
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
9583
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
7134
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
6002
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
2
4225
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
3239
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.