what is recursion in c++.

Discussion in 'C++' started by athar.mirchi@gmail.com, Jan 5, 2008.

  1. Guest

    ..plz define it.
     
    , Jan 5, 2008
    #1
    1. Advertising

  2. On Sat, 05 Jan 2008 20:17:17 +0100,
    <> wrote:

    > .plz define it.



    RTFM !
    Google is not dead !
     
    David Côme, Jan 5, 2008
    #2
    1. Advertising

  3. "" <> wrote 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
     
    Tomás Ó hÉilidhe, Jan 5, 2008
    #3
  4. Mark Guest

    Mark, Jan 5, 2008
    #4
  5. Salt_Peter Guest

    On Jan 5, 2:17 pm, "" <>
    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
    }
     
    Salt_Peter, Jan 5, 2008
    #5
  6. Salt_Peter Guest

    On Jan 5, 2:23 pm, David Côme <> wrote:
    > On Sat, 05 Jan 2008 20:17:17 +0100,
    >
    > <> wrote:
    > > .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.
     
    Salt_Peter, Jan 5, 2008
    #6
  7. Guest

    On Jan 5, 2:19 pm, Salt_Peter <> wrote:
    > On Jan 5, 2:17 pm, "" <>


    > 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, 2008
    #7
  8. On Sat, 05 Jan 2008 21:41:38 +0100, Salt_Peter <> wrote:

    > On Jan 5, 2:23 pm, David Côme <> wrote:
    >> On Sat, 05 Jan 2008 20:17:17 +0100,
    >>
    >> <> wrote:
    >> > .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....
     
    David Côme, Jan 5, 2008
    #8
  9. Salt_Peter <> wrote 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
     
    Tomás Ó hÉilidhe, Jan 5, 2008
    #9
  10. Jim Langston Guest

    Tomás Ó hÉilidhe wrote:
    > Salt_Peter <> wrote 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
     
    Jim Langston, Jan 5, 2008
    #10
  11. Pete Becker Guest

    On 2008-01-05 15:19:08 -0500, Salt_Peter <> said:

    > On Jan 5, 2:17 pm, "" <>
    > 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)
     
    Pete Becker, Jan 6, 2008
    #11
  12. red floyd Guest

    wrote:
    > .plz define it.



    RECURSION: see RECURSION.
     
    red floyd, Jan 6, 2008
    #12
  13. red floyd Guest

    Jim Langston wrote:

    > recursion [ri-kur'zhen] - (n) see recursion
    >


    Damn. I posted the exact same definition before I saw your post. GMTA.
     
    red floyd, Jan 6, 2008
    #13
  14. Jerry Coffin Guest

    In article <m3Xfj.33592$>,
    says...
    > 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.
     
    Jerry Coffin, Jan 6, 2008
    #14
  15. Kira Yamato Guest

    On 2008-01-05 21:30:42 -0500, red floyd <> said:

    > 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
     
    Kira Yamato, Jan 6, 2008
    #15
  16. Daniel T. Guest

    "" <> wrote:

    > .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();
    }
     
    Daniel T., Jan 6, 2008
    #16
  17. Lionel B Guest

    On Sat, 05 Jan 2008 20:26:10 -0700, Jerry Coffin wrote:

    > In article <m3Xfj.33592$>,
    > says...
    >> 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
     
    Lionel B, Jan 6, 2008
    #17
  18. James Kanze Guest

    On Jan 5, 9:19 pm, Salt_Peter <> wrote:
    > On Jan 5, 2:17 pm, ""
    > <> wrote:


    > > .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:
    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
     
    James Kanze, Jan 6, 2008
    #18
  19. Guest

    On Jan 6, 6:37 pm, James Kanze <> wrote:
    > On Jan 5, 9:19 pm, Salt_Peter <> wrote:
    >
    > > On Jan 5, 2:17 pm, ""
    > > <> wrote:
    > > > .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:
    > 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, 2008
    #19
  20. red floyd Guest

    red floyd, Jan 8, 2008
    #20
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Tim Mohler
    Replies:
    1
    Views:
    460
    Steve Grazzini
    Sep 16, 2003
  2. B McInnes

    recursion with perl

    B McInnes, Nov 1, 2003, in forum: Perl
    Replies:
    4
    Views:
    4,149
    B McInnes
    Nov 4, 2003
  3. Chris

    Recursion Query

    Chris, May 17, 2004, in forum: ASP .Net
    Replies:
    1
    Views:
    452
    avnrao
    May 17, 2004
  4. Iain
    Replies:
    3
    Views:
    1,835
    Robbe Morris [C# MVP]
    Mar 9, 2006
  5. Replies:
    8
    Views:
    798
    John Reye
    Apr 26, 2012
Loading...

Share This Page