Thread: Recursion...help,tips,suggestions

  1. #1
    Registered User
    Join Date
    Oct 2007
    Posts
    51

    Recursion...help,tips,suggestions

    hi there I need some serious help with recursions! i have read the tutorial on this site i am reading some info out of a book and i still find it hard to understand!

    if you have any tip or suggestions on how you understand recursion can you pleas post here so i can look at it.. also if you know any links of good explanations i would like to look at the also!

    thanks in advance!

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318

    Talking

    Here is a demonstration of recursion.

    The tutorial on this site for recursion is pretty good. You'll have to be more specific about what part you don't understand.
    Have you writen a non-recursive function that you would like to convert to being recursive, or do you have a particular algorithm you want to implement? It's not as easy to understand it if you aren't actually trying to program it.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Oct 2007
    Posts
    51
    well basicly.. im very confused about all of recursion.. i dont know how to write or even understand it.. i dont know how to convert a recursive function to a non-recursive function.. im just reading everything i can.. i think maybe im suffereing a little bit of over burn at the moment..

  4. #4
    Registered User
    Join Date
    Oct 2007
    Posts
    51
    i liked the link.. had me for a second but i understand it! lol

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > if you have any tip or suggestions on how you understand recursion
    Consider this dumb strlen function
    Code:
    int myStrlen ( const char *s ) {
      if ( *s == '\0' ) {
        return 0; /* trivial case */
      } else {
        /* a simplification of the problem */
        return 1 + myStrlen( s + 1 );
      }
    }
    In essence, recursion just re-uses the same code to work on a simplified version of the same problem. Eventually, you get to a point which is trivial to solve and that is when the recursion stops.

    Another example is walking a tree, where each sub-tree is a tree in it's own right.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  6. #6
    Registered User
    Join Date
    Oct 2007
    Posts
    51

    i defintlay understand it now..

    however i need to figure out how to problem solve with it! anyhelp would be greatly appreciated! here is a question im working on! my coding is wrong which ill show you if you could push me in the right direction and tell me if what im doing is rightish or wrongish that would be great! this Site has helped me so much! i hope one day to become a very regular and contributing member!
    okay.. here goes nothing!

    Question: One way to count the number of digits in a positive number is to use a recursive function -digits-. The number is passed as an argument to the function. The function returns the value 1 is the number is less than 10, otherwise it returns 1+the number of digits in the number when divided by 10. write the recursive function in C, then write a non-recursive version of the same function.

    now.. im going to show you my attempt.. its not very good.. but its the best i could do lol.. the code isnt even working.. can you please exapline to me why etc.. im not looking for an answer im just looking for explinations if that makes any sense.. lol

    Code:
    int main(){
    	int digits (/*i dont know how to give digit function a number for its argument*/){
    		if (digits > 9 ){
    			return 1;
    		}else{
    				return 1+(digits/10);/*not sure this is even close..but this is the recursive bit.. i think*/
    		}
    	}
    thanks for all the help so far! its really helped!

  7. #7
    Registered User
    Join Date
    Jun 2007
    Location
    Rome, NY
    Posts
    24
    It would maybe be best to look at it from more of a mathematical perspective. After all, recursion is rooted in mathematics, as is most of computer science.

    I am not saying you need to start cranking out math problems, but once you understand the mathematical concepts, programming them becomes much simpler. A good book on data structures and algorithms is a must.

    For example, the Fibonacci sequence.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    /* returns the n'th fibonacci number */
    int fibonacci(int n);
    
    int main(int argc, char **argv)
    {
            int num;
            if (argc == 2) {
                    num = atoi(argv[1]);
                    printf("fibonacci(&#37;d) = %d\n",num,fibonacci(num));
            }
            return 0;
    }
    
    int fibonacci(int n)
    {
            if (n == 0) {
                    return 0;
            } else if (n == 1) {
                    return 1;
            } else if (n > 1) {
                    return fibonacci(n - 1) + fibonacci(n - 2);
            } else {
                    printf("Must be postive integer\n");
                    return -1;
            }
    }
    The Fibonacci sequence is a recursively defined as F(n) = F(n-1) + F(n-2) and the bascases are 0, if n == 0, and 1 if n == 1.

    The Fibonacci sequence is a very famous problem, and usually used to introduce recursion to computer science students.

  8. #8
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    A perfect example is browsing for files:
    Code:
    void some_func(char* path)
    {
    // Check for sub-folders; and if found then do:
    some_func(new_sub_folder);
    // Now do something with all those files
    }
    And so on. Each time it finds a sub-folder, it calls itself to investiate that folder. Recursion, plain and simple. I have a snippet of code, though it may be a little tough to understand.

  9. #9
    Registered User
    Join Date
    Oct 2007
    Posts
    51

    okay.. i fully understand recursion now..

    maybe its this question thats trowing me off!

    How the heck would i make recursive code outta that question?
    i know how to make it non recursive.. thats easly done! but Recursive.. dose anyone have any idea how it could be done?

    please explain

  10. #10
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    That doesn't seem like a good code to use recursion on at all.

  11. #11
    Registered User ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,732
    do you mean how to convert a recursive to non-recursive function?

    EDIT: Never looked at the previous code of your. And yes. The question donst say any where what need to be recursive. I thnk thats not a good example for a recursive function.

    ssharish
    Last edited by ssharish2005; 10-25-2007 at 07:55 PM.

  12. #12
    Registered User
    Join Date
    Oct 2007
    Posts
    51
    I need to know how to make that question into a recursive function.
    I also need to know.. but know how to make it a non-recursive function.

  13. #13
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Your sample isn't recursive at all, so it's basically a non-recursive function. A recursive function is one that calls itself one or more times.
    But how to make it recursive? You don't just make something recursive. Either the task you want to do requires a recursive approach or it does not. Or so it is usually.
    The sample you have is just an example of a non-recursive task. I don't know how to turn it into a recursive function. And even if I did, it would just be a waste.
    Last edited by Elysia; 10-25-2007 at 08:04 PM.

  14. #14
    Registered User
    Join Date
    Oct 2007
    Posts
    51
    yea.. thats what i think.. and thats probably why its giving me headach!!! its in an old exam im studying from.. crazy! i wounder if its a mistake?

  15. #15
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Probably. This code was not made to be recursive. I think you should ignore the make-recursive part. If you want to train recursive, you can try to find a task that requires it and write code for it (for example, a function that finds all *.exe files on drive C).
    But anyway, it's up to you.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Template Recursion Pickle
    By SevenThunders in forum C++ Programming
    Replies: 20
    Last Post: 02-05-2009, 09:45 PM
  2. Recursion... why?
    By swgh in forum C++ Programming
    Replies: 4
    Last Post: 06-09-2008, 09:37 AM
  3. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM
  4. To Recur(sion) or to Iterate?That is the question
    By jasrajva in forum C Programming
    Replies: 4
    Last Post: 11-07-2001, 09:24 AM
  5. selection sorting using going-down and going-up recursion
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 11-02-2001, 02:29 PM