questions for recursion practise.

Discussion in 'C++' started by Muzammil, Nov 4, 2008.

  1. Muzammil

    Muzammil Guest

    i want good practice over recursion.
    can any one give me links for recursion questions site.?? or
    question.
    Muzammil, Nov 4, 2008
    #1
    1. Advertising

  2. Muzammil

    Salt_Peter Guest

    On Nov 3, 11:56 pm, Muzammil <> wrote:
    > i want good practice over recursion.
    > can any one give  me  links for recursion questions site.?? or
    > question.


    Consider trying "C++ recursion" of "C++ Fibonacci" in google.

    You need a question? sure...

    #include <iostream>

    void recurse(int n)
    {
    std::cout << "n = " << n << std::endl;
    if(n > 0)
    recurse(--n);
    }

    int main()
    {
    recurse(10);
    }

    How many times will recurse() call itself? (its not 10 times)
    What would happen if a negative number were used instead of 10?
    What happens when infinite recursion occurs? Can you explain why?
    Salt_Peter, Nov 4, 2008
    #2
    1. Advertising

  3. Muzammil

    James Kanze Guest

    On Nov 4, 5:56 am, Muzammil <> wrote:
    > i want good practice over recursion.
    > can any one give me links for recursion questions site.?? or
    > question.


    Well, factorial and fibonaci are the classical examples,
    although both have iterative solutions which are perhaps
    simpler. What you might try is a simple expression parser which
    handles parentheses.

    --
    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, Nov 4, 2008
    #3
  4. "James Kanze" <> wrote in message
    news:...
    >On Nov 4, 5:56 am, Muzammil <> wrote:
    >> i want good practice over recursion.
    >> can any one give me links for recursion questions site.?? or
    >> question.


    >Well, factorial and fibonaci are the classical examples,
    >although both have iterative solutions which are perhaps
    >simpler. What you might try is a simple expression parser which
    >handles parentheses.


    The first example I ever saw that showed recursion was useful
    (factorial does not, anyone who can understand it can see that
    iteration is easier) was the Tower of Hanoi. Summarising the
    solution, in a manner that obviously works, and maps directly to
    recursion

    To move N discs from A to B, first move N-1 discs from A to C,
    then move disc N from A to B, then move N-1 discs from B to C.

    A non-recursive solution exists (of course) but is a lot less obvious.

    (I'm assuming the underlying problem is well-known. If not, I'm sure
    Google will give you many explanations.)
    Christopher Dearlove, Nov 4, 2008
    #4
  5. blargg wrote:
    > Salt_Peter wrote:
    > [...]
    >> void recurse(int n)
    >> {
    >> std::cout << "n = " << n << std::endl;
    >> if(n > 0)
    >> recurse(--n);
    >> }
    >>
    >> int main()
    >> {
    >> recurse(10);
    >> }
    >>
    >> How many times will recurse() call itself? (its not 10 times)

    >
    > Really? Looks like it calls itself 10 times to me.


    It looks like it at first glance but note that the decrement is done
    AFTER the conditional.

    --
    George Kettleborough
    G Kettleborough, Nov 4, 2008
    #5
  6. G Kettleborough wrote:

    >>> How many times will recurse() call itself? (its not 10 times)


    >> Really? Looks like it calls itself 10 times to me.

    >
    > It looks like it at first glance but note that the decrement is done
    > AFTER the conditional.


    I, too, believe that recurse() calls itself 10 times. (The number of all
    calls to recurse() is 11.)
    Eberhard Schefold, Nov 4, 2008
    #6
  7. Muzammil

    Salt_Peter Guest

    On Nov 4, 6:09 am, Eberhard Schefold <>
    wrote:
    > G Kettleborough wrote:
    > >>> How many times will recurse() call itself? (its not 10 times)
    > >> Really? Looks like it calls itself 10 times to me.

    >
    > > It looks like it at first glance but note that the decrement is done
    > > AFTER the conditional.

    >
    > I, too, believe that recurse() calls itself 10 times. (The number of all
    > calls to recurse() is 11.)


    The original question was worded badly, should have been 'how many
    times is recurse called?". 10 recursions and 11 calls is indeed right.
    Salt_Peter, Nov 4, 2008
    #7
  8. Muzammil <> writes:

    > i want good practice over recursion.
    > can any one give me links for recursion questions site.?? or
    > question.


    The best examples are ones where a recursive solution is natural.
    This is often the case with nested structures (binary tree algorithms
    for example) or which use "divide and conquer" (merge sort of a linked
    list). If these involve data structures you have not yet learnt, then
    here are some other examples:

    Counting change. Given a set of denominations for coinage (e.g. {1,
    2, 5, 10, 20, 50}) how many ways are there of making up a given amount
    of change? For example, there are 68 ways to make 25 from those
    denominations.

    Solve the Towers of Hanoi puzzle (just search the web for it, but
    avert your eye from any solutions you might come across!).

    If have access to a graphics package, write programs to draw some
    fractal shapes. The Koch snowflake is one of my favourites, though
    you can have more creative fun drawing recursive trees: each tree is a
    trunk with 2 or maybe 3 trees growing from the top at randomly chosen
    angles. At the limit of the recursion, draw a leaf. You can have
    great fun altering the range of angles you choose for the branches and
    the way the trunk length shrinks (or grows!) with the recursion.

    Searching for solutions to puzzles is often naturally recursive. For
    example, how many ways are there of putting N queens on an NxN chess
    board so that no two queens are on the same row, rank or diagonal?

    Write a simple pattern matcher. A pattern is either a primitive or a
    sequence of primitives, or a primitive followed by * to indicate zero
    or more repetitions of the preceding primitive. It helps to have a
    primitive like . that can match any single character. Once you've got
    a really clean implementation of this, add in ()s that can turn a
    sequence into a primitive. I.e. a(bc)*d maches "ad", "abcd", "abcbcd"
    etc.

    That should be enough for a while!

    [1] http://en.wikipedia.org/wiki/Koch_snowflake

    --
    Ben.
    Ben Bacarisse, Nov 4, 2008
    #8
  9. Muzammil

    Muzammil Guest

    On Nov 4, 9:51 pm, Ben Bacarisse <> wrote:
    > Muzammil <> writes:
    > > i want good practice over recursion.
    > > can any one give  me  links for recursion questions site.?? or
    > > question.

    >
    > The best examples are ones where a recursive solution is natural.
    > This is often the case with nested structures (binary tree algorithms
    > for example) or which use "divide and conquer" (merge sort of a linked
    > list).  If these involve data structures you have not yet learnt, then
    > here are some other examples:
    >
    > Counting change.  Given a set of denominations for coinage (e.g. {1,
    > 2, 5, 10, 20, 50}) how many ways are there of making up a given amount
    > of change?  For example, there are 68 ways to make 25 from those
    > denominations.
    >
    > Solve the Towers of Hanoi puzzle (just search the web for it, but
    > avert your eye from any solutions you might come across!).
    >
    > If have access to a graphics package, write programs to draw some
    > fractal shapes.  The Koch snowflake is one of my favourites, though
    > you can have more creative fun drawing recursive trees: each tree is a
    > trunk with 2 or maybe 3 trees growing from the top at randomly chosen
    > angles.  At the limit of the recursion, draw a leaf.  You can have
    > great fun altering the range of angles you choose for the branches and
    > the way the trunk length shrinks (or grows!) with the recursion.
    >
    > Searching for solutions to puzzles is often naturally recursive.  For
    > example, how many ways are there of putting N queens on an NxN chess
    > board so that no two queens are on the same row, rank or diagonal?
    >
    > Write a simple pattern matcher.  A pattern is either a primitive or a
    > sequence of primitives, or a primitive followed by * to indicate zero
    > or more repetitions of the preceding primitive.  It helps to have a
    > primitive like . that can match any single character.  Once you've got
    > a really clean implementation of this, add in ()s that can turn a
    > sequence into a primitive.  I.e. a(bc)*d maches "ad", "abcd", "abcbcd"
    > etc.
    >
    > That should be enough for a while!
    >
    > [1]http://en.wikipedia.org/wiki/Koch_snowflake
    >
    > --
    > Ben.


    thanks. i got my point.enough.
    Muzammil, Nov 5, 2008
    #9
    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. Rabbit
    Replies:
    3
    Views:
    2,093
    Terry Burns
    Apr 1, 2006
  2. exquisitus
    Replies:
    0
    Views:
    454
    exquisitus
    Feb 20, 2005
  3. VisionSet
    Replies:
    0
    Views:
    821
    VisionSet
    Aug 19, 2003
  4. Carsten Fuchs
    Replies:
    5
    Views:
    343
    Jerry Coffin
    May 19, 2005
  5. Replies:
    8
    Views:
    710
    John Reye
    Apr 26, 2012
Loading...

Share This Page