Mmm...recursion~

This is a discussion on Mmm...recursion~ within the C++ Programming forums, part of the General Programming Boards category; Could anyone afford something on recursion ? I have test Hanoi code but still feel it is not enought for ...

  1. #1
    flashing vampire black's Avatar
    Join Date
    May 2002
    Posts
    563

    Arrow Mmm...recursion~

    Could anyone afford something on recursion ? I have test Hanoi code but still feel it is not enought for comprehension because of my poor knowledge on Math.

    thanx in advanced.
    Never end on learning~

  2. #2
    Registered User
    Join Date
    May 2002
    Posts
    21
    You should go and learn some data structures(especially linked lists and binary trees) to practice a lot of recursion problems.

    Some very good problems are in Stanford computer science library online. They are both introductory and challenging to some extent.

    Then you can go further and learn about game theory and compression. Ask me if you can't have enough information and links.

  3. #3
    flashing vampire black's Avatar
    Join Date
    May 2002
    Posts
    563
    Originally posted by |deep|
    You should go and learn some data structures(especially linked lists and binary trees) to practice a lot of recursion problems.

    Some very good problems are in Stanford computer science library online. They are both introductory and challenging to some extent.

    Then you can go further and learn about game theory and compression. Ask me if you can't have enough information and links.
    thanx~

    Would u mind supporting me anything which would help me to understand recursion utterly ?
    Last edited by black; 07-04-2002 at 03:12 AM.
    Never end on learning~

  4. #4
    Unregistered
    Guest
    recursion means calling the same function within the function:

    Code:
    bool function(int data)
    {
      //whatever
      function(newData);//recursive call of function()
      //whatever
    }
    This can lead to an endless loop, so you should always be sure you use a terminating condition to prevent this:

    Code:
    bool function(int data)
    {
       //terminating condition
       //do something different if terminating condition exists
       //otherwise continue blithely onward
       function(newData);
      //whatever
    }
    let's say you wanted to print all integers from 0 to 10 in order using recursion. You would pass 0 first; check to see if it equaled 10. If it does you would stop any further funciton calls. If it didn't you would increment it and pass it again.

    Code:
    bool function(int data)
    {
       if(data == 10)
       {
         cout << data << endl;  //print out data
         return false; 
       } 
    
    /*if data equals 10 this will stop this call and return false to the function that made this call.  The calling function ignores the return, but that doesn't matter, and it won't be ignored in all recursive functions.   IF data equals 10 none of the stuff below will be used.  If data != 10 then function() will proceed to stuff below
    */
    
       cout << data << endl;  //here we print out the desired info
       int newData = ++data; 
    /*here we increment data and assign it to newData.  You could pass ++data itself but I think this is clearer
    */
        
       function(newData); //here's the recursive call
       
       return false;
    /*this return won't happen untile the line immediately above it is completed if data isn't 10.  
    */
    }
    Here it is in a program:

    Code:
    #include <iostream.h>
    
    bool function(int data);
    
    int main()
    {
      int  Data = 0;
      function(Data);
      return 0;
    }
      
    bool function(int data)
    {
       if(data == 10)
       {
          cout << data << endl;
          return false;
        }
    
        cout << data << endl;
        int newData = ++data;
        function(newData);
        return false;
    }
    To see an interesting effect try this variant of function. Note the critical difference placement of the single line of code makes. You can use this effect to your advantage sometimes.

    Code:
    bool function(int data)
    {
       if(data == 10)
       {
          cout << data << endl;
          return false;
        }
    
        //cout << data << endl;
        int newData = ++data;
        function(newData);
    
        cout << data << endl;
    
        return false;
    }

  5. #5
    ....
    Join Date
    Aug 2001
    Location
    Groningen (NL)
    Posts
    2,386
    Another famous example, the factorial function:

    n! = n x (n-1) x (n-2) x .. x 3 x 2 x 1

    This is a recursive definition. The is reached when 1 is reached, which is the end-step of the recursion. The recursion step is n x n-1)!. This can be easily seen as follows:

    2! = 2 x 1
    3! = 3 x 2 x 1 = 3 x 2!
    4! = 4 x 3 x 2 x 1 = 4 x 3!
    n! = n x (n-1) x .. x 2 x 1 = n x (n-1)!

    This leads to this recursive function:

    Code:
    int fac (int n)
    {
        if (n == 1) /* the end-step */
            return n;
        else
            return (n * fac (n - 1));
    Hope this example helps a little in understanding recursion. To understand recursion, I used to study mathematical relations and then translate them to code. Another famous example is the Fibonacci numbers:

    F[0] = 0
    F[1] = 1
    F[n] = F[n-1] + F[n-2]

    Here the end-step is reached if n = 1. The recursion step is the recursive relation F[n] = F[n-1] + F[n-2]. This leads to the recursive function:

    Code:
    int fib (int n)
    {
        if (n == 1)
            return (n);
        else
            return (fib (n-1) + fib (n-2));
    }
    More on Fibonacci can be found here:

    http://mathworld.wolfram.com/FibonacciNumber.html

  6. #6
    flashing vampire black's Avatar
    Join Date
    May 2002
    Posts
    563

    Thumbs up

    thanx guys.

    I am a bit confused 1 second ago and now clearly with all your help~

    In fact, I had written some functions with recursion already. I will paste them here for sharing.
    Never end on learning~

  7. #7
    flashing vampire black's Avatar
    Join Date
    May 2002
    Posts
    563

    Smile

    //these functions below are all with recursion method:

    PHP Code:
    //function 1;
    int Fact(int n)
    {
      if(
    n==0)
      {
        return 
    1;
      }
      else if(
    n>0)
      {
        return 
    n*Fact(n-1);
      }
    }

    //function 2;
    int Fib(int n)
      if(
    n==|| n==2)
      {
        return 
    1;
      }
      else if(
    n>2)
      {
        return 
    Fib(n-1)+Fib(n-2);
      }

    Never end on learning~

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21