By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
459,995 Members | 1,090 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 459,995 IT Pros & Developers. It's quick & easy.

what is recursion in c++.

P: n/a
..plz define it.
Jan 5 '08 #1
Share this Question
Share on Google+
20 Replies


P: n/a
On Sat, 05 Jan 2008 20:17:17 +0100, at**********@gmail.com
<at**********@gmail.comwrote:
.plz define it.

RTFM !
Google is not dead !
Jan 5 '08 #2

P: n/a
"at**********@gmail.com" <at**********@gmail.comwrote in comp.lang.c++:
.plz define it.
Mainly "recursion" is where a function calls itself. Something like:

long unsigned Factorial(unsigned const input)
{
if (0 == input) return 1;

if (1 == input) return input;

return input * Factorial(input - 1);
}

--
Tomás Ó hÉilidhe
Jan 5 '08 #3

P: n/a
On 2008-01-05 19:17:17 +0000, "at**********@gmail.com"
<at**********@gmail.comsaid:
.plz define it.
http://en.wikipedia.org/wiki/Recursion

Jan 5 '08 #4

P: n/a
On Jan 5, 2:17 pm, "athar.mir...@gmail.com" <athar.mir...@gmail.com>
wrote:
.plz define it.
As the English word suggests: a recursion is simply a function that
calls itself.
Which is neither efficient nor beneficial.
Each call generates a new local stack which eventually all need to be
unwound.
So in C++, its usually replaced with better alternatives.
An example of a preferred alternative would then be a function object
(functor).
Recursive functions have no state (what does that mean?).

To give you an example of recursion:
(that incidentally doesn't do what you'ld expect)

#include <iostream>

void recursion(int n)
{
std::cout << "n = ";
std::cout << n << std::endl;
if(n < 10)
recursion(++n);
}

int main()
{
recursion(0); // prints 11 times
}
Jan 5 '08 #5

P: n/a
On Jan 5, 2:23 pm, David Côme <davidc...@wanadoo.frwrote:
On Sat, 05 Jan 2008 20:17:17 +0100, athar.mir...@gmail.com

<athar.mir...@gmail.comwrote:
.plz define it.

RTFM !
Google is not dead !
And neither is a little respect.
Some come here hoping others do their homework,
others prefer to ask rather than remain clueless.
Some of those know very little English.

So please: if you feel the need to reply with a patronising remark,
consider ignoring them, redirecting them to Wikipedia/Google or offer
them a link to the FAQ.
Jan 5 '08 #6

P: n/a
On Jan 5, 2:19*pm, Salt_Peter <pj_h...@yahoo.comwrote:
On Jan 5, 2:17 pm, "athar.mir...@gmail.com" <athar.mir...@gmail.com>
Each call generates a new local stack which eventually all need to be
unwound.
So in C++, its usually replaced with better alternatives.

I agree. But my old college professors thought it was great.

And personally, I also find it more difficult to debug.
Jan 5 '08 #7

P: n/a
On Sat, 05 Jan 2008 21:41:38 +0100, Salt_Peter <pj*****@yahoo.comwrote:
On Jan 5, 2:23 pm, David Côme <davidc...@wanadoo.frwrote:
>On Sat, 05 Jan 2008 20:17:17 +0100, athar.mir...@gmail.com

<athar.mir...@gmail.comwrote:
.plz define it.

RTFM !
Google is not dead !

And neither is a little respect.
Some come here hoping others do their homework,
others prefer to ask rather than remain clueless.
Some of those know very little English.

So please: if you feel the need to reply with a patronising remark,
consider ignoring them, redirecting them to Wikipedia/Google or offer
them a link to the FAQ.


You could have a basic question because everybody has been noob when he
started programmation.
Howerver before ask usenet,forums... you must make some research.

And recursion on google was the fisrt link so....

Jan 5 '08 #8

P: n/a
Salt_Peter <pj*****@yahoo.comwrote in comp.lang.c++:
As the English word suggests: a recursion is simply a function that
calls itself.
Which is neither efficient nor beneficial.

It's great though for template metaprogramming. For instance:

template<long unsigned x>
struct Factorial {
static long unsigned const val = x * Factorial<x-1>::val;
};

template<>
struct Factorial<1{
static long unsigned const val = val;
};

template<>
struct Factorial<0{
static long unsigned const val = 1;
}
--
Tomás Ó hÉilidhe
Jan 5 '08 #9

P: n/a
Tomás Ó hÉilidhe wrote:
Salt_Peter <pj*****@yahoo.comwrote in comp.lang.c++:
>As the English word suggests: a recursion is simply a function that
calls itself.
Which is neither efficient nor beneficial.


It's great though for template metaprogramming. For instance:

template<long unsigned x>
struct Factorial {
static long unsigned const val = x * Factorial<x-1>::val;
};

template<>
struct Factorial<1{
static long unsigned const val = val;
};

template<>
struct Factorial<0{
static long unsigned const val = 1;
}
recursion [ri-kur'zhen] - (n) see recursion

--
Jim Langston
ta*******@rocketmail.com
Jan 5 '08 #10

P: n/a
On 2008-01-05 15:19:08 -0500, Salt_Peter <pj*****@yahoo.comsaid:
On Jan 5, 2:17 pm, "athar.mir...@gmail.com" <athar.mir...@gmail.com>
wrote:
>.plz define it.

As the English word suggests: a recursion is simply a function that
calls itself.
Which is neither efficient nor beneficial.
Bummer. We'll have to stop using quicksort.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

Jan 6 '08 #11

P: n/a
at**********@gmail.com wrote:
.plz define it.

RECURSION: see RECURSION.
Jan 6 '08 #12

P: n/a
Jim Langston wrote:
recursion [ri-kur'zhen] - (n) see recursion
Damn. I posted the exact same definition before I saw your post. GMTA.
Jan 6 '08 #13

P: n/a
In article <m3*****************@newssvr21.news.prodigy.net> ,
no*****@here.dude says...
at**********@gmail.com wrote:
.plz define it.


RECURSION: see RECURSION.
Error stack overflow at 1.

Recursion: if (understood) return; else see Recursion.

--
Later,
Jerry.

The universe is a figment of its own imagination.
Jan 6 '08 #14

P: n/a
On 2008-01-05 21:30:42 -0500, red floyd <no*****@here.dudesaid:
at**********@gmail.com wrote:
>.plz define it.


RECURSION: see RECURSION.
That's not recursion. That's just circular reasoning.

The difference is that circular reasoning is not logically sound, but
recursion is. More specifically, a definition using recursion admits
existence and uniqueness of an object under that definition, while
circular reasoning is ambiguous.

For example, the recursion
f(n+1) = f(n) + 1
f(0) = 0
admits the actual function
f(n) = n.

On the other hand, the circular-reasoning "definition"
g(n) = g(n)
admits any function since that definition is vacuously true for any function.

--

-kira

Jan 6 '08 #15

P: n/a
"at**********@gmail.com" <at**********@gmail.comwrote:
.plz define it.
Here is an example of recursion that people don't often think of as
such...

class Foo {
public:
list< Foo* foos;
void bar() {
for_each( foos.begin(), foos.end(), mem_fun( &Foo::bar ) );
}
};

int main() {
Foo f[10];
f[0].foos.push_back( &f[1] );
f[0].foos.push_back( &f[2] );
f[0].foos.push_back( &f[3] );
f[2].foos.push_back( &f[4] );
f[2].foos.push_back( &f[5] );
f[2].foos.push_back( &f[6] );
f[3].foos.push_back( &f[7] );
f[7].foos.push_back( &f[8] );
f[8].foos.push_back( &f[9] );

f[0].bar();
}
Jan 6 '08 #16

P: n/a
On Sat, 05 Jan 2008 20:26:10 -0700, Jerry Coffin wrote:
In article <m3*****************@newssvr21.news.prodigy.net> ,
no*****@here.dude says...
>at**********@gmail.com wrote:
.plz define it.


RECURSION: see RECURSION.

Error stack overflow at 1.

Recursion: if (understood) return; else see Recursion.
Warning: condition always evaluates to false

--
Lionel B
Jan 6 '08 #17

P: n/a
On Jan 5, 9:19 pm, Salt_Peter <pj_h...@yahoo.comwrote:
On Jan 5, 2:17 pm, "athar.mir...@gmail.com"
<athar.mir...@gmail.comwrote:
.plz define it.
As the English word suggests: a recursion is simply a function
that calls itself. Which is neither efficient nor beneficial.
It's beneficial when its beneficial. On most modern
architectures, it's often as efficient as the alternatives. (I
once benchmarked a recursive version of quick sort, and one
which avoided recursion. the recursive version was faster.)
Each call generates a new local stack which eventually all
need to be unwound. So in C++, its usually replaced with
better alternatives. An example of a preferred alternative
would then be a function object (functor).
How is that relevant to recursion. A functional object is still
a function, and can still be recursive or not, according to how
you write it.
Recursive functions have no state (what does that mean?).
I don't know? I have no idea what you're trying to say there.
To give you an example of recursion: (that incidentally
doesn't do what you'ld expect)
#include <iostream>
void recursion(int n)
{
std::cout << "n = ";
std::cout << n << std::endl;
if(n < 10)
recursion(++n);
}
int main()
{
recursion(0); // prints 11 times
}
And your point is?

Any iterative algorithm can be rewritten to use recursion. Some
languages don't even have looping constructions, but in C++,
using recursion to simluate iteration is poor programming
practice. On the other hand, recursion is considerably more
powerful than iteration, and not all recursive algorithms can be
rewritten in terms of pure iteration, unless you introduce a
manually managed stack, which is a lot more work for the
programmer, and typically less efficient in terms of run-time.
How would you do a depth first visit of a tree without
recursion, for example? (Or quick sort, for that matter? The
standard non-recursive iteration requires a user managed stack.)

Note that recursion is typically less efficient in terms of
memory than managing the stack yourself, so you'll normally want
to avoid recursing too deeply.

--
James Kanze (GABI Software) email:ja*********@gmail.com
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
Jan 6 '08 #18

P: n/a
On Jan 6, 6:37*pm, James Kanze <james.ka...@gmail.comwrote:
On Jan 5, 9:19 pm, Salt_Peter <pj_h...@yahoo.comwrote:
On Jan 5, 2:17 pm, "athar.mir...@gmail.com"
<athar.mir...@gmail.comwrote:
.plz define it.
As the English word suggests: a recursion is simply a function
that calls itself. *Which is neither efficient nor beneficial.

It's beneficial when its beneficial. *On most modern
architectures, it's often as efficient as the alternatives. *(I
once benchmarked a recursive version of quick sort, and one
which avoided recursion. *the recursive version was faster.)
Each call generates a new local stack which eventually all
need to be unwound. *So in C++, its usually replaced with
better alternatives. *An example of a preferred alternative
would then be a function object (functor).

How is that relevant to recursion. *A functional object is still
a function, and can still be recursive or not, according to how
you write it.
Recursive functions have no state (what does that mean?).

I don't know? *I have no idea what you're trying to say there.
To give you an example of recursion: (that incidentally
doesn't do what you'ld expect)
#include <iostream>
void recursion(int n)
{
* std::cout << "n = ";
* std::cout << n << std::endl;
* if(n < 10)
* * recursion(++n);
}
int main()
{
* recursion(0); // prints 11 times
}

And your point is?

Any iterative algorithm can be rewritten to use recursion. *Some
languages don't even have looping constructions, but in C++,
using recursion to simluate iteration is poor programming
practice. *On the other hand, recursion is considerably more
powerful than iteration, and not all recursive algorithms can be
rewritten in terms of pure iteration, unless you introduce a
manually managed stack, which is a lot more work for the
programmer, and typically less efficient in terms of run-time.
How would you do a depth first visit of a tree without
recursion, for example? *(Or quick sort, for that matter? *The
standard non-recursive iteration requires a user managed stack.)

Note that recursion is typically less efficient in terms of
memory than managing the stack yourself, so you'll normally want
to avoid recursing too deeply.

--
James Kanze (GABI Software) * * * * * * email:james.ka...@gmail.com
Conseils en informatique orientée objet/
* * * * * * * * * *Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
I need some memory related information about recursion.
That is how it is implemented
Jan 8 '08 #19

P: n/a
ta********@gmail.com wrote:
>
I need some memory related information about recursion.
That is how it is implemented
You answer is found here:

http://www.parashift.com/c++-faq-lit...t.html#faq-5.2
Jan 8 '08 #20

P: n/a
ta********@gmail.com wrote:
[SNIP]
I need some memory related information about recursion.
That is how it is implemented
AFAIK a recursive function isn't different than a non recursive function.
The function just calls itself like it could call any function pushing the
parameters onto the stack, in an implementation that uses a stack.

With enough recursion you can run out of stack space, which is why there's a
practicle limit to the number of times you can recurse.

--
Jim Langston
ta*******@rocketmail.com
Jan 8 '08 #21

This discussion thread is closed

Replies have been disabled for this discussion.