Thread: is this infinite recursion?

  1. #1
    Registered User msp's Avatar
    Join Date
    Jul 2007
    Location
    in
    Posts
    31

    Question is this infinite recursion?

    I tried this and was expecting it to recurse infinitely (until stack fault).
    But it did not.
    Code:
    int (*foo) (int, char**);
    
    int main(int argc, char** argv)
    {
            foo = main;
            foo(argc, argv);
            return 0;
    }
    I used gcc.

  2. #2
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    See this topic: http://cboard.cprogramming.com/showthread.php?t=55914

    I believe calling main() recursively is allowed, however, due to complications of calling conventions or other such things under the hood, the behavior is undefined, although the standard makes no statement.

  3. #3
    Registered User msp's Avatar
    Join Date
    Jul 2007
    Location
    in
    Posts
    31
    Oh so may be there are some problems related to recursion of the main method in C.
    Not a problem I will try the above with a different function.
    Thanks.

  4. #4
    Registered User msp's Avatar
    Join Date
    Jul 2007
    Location
    in
    Posts
    31
    Damn!
    Even this did not work
    Code:
    int (*foo) (int, char**);
    
    int bar(int c, char** a)
    {
            foo = bar;
            foo(c, a);
    }
    
    int main(int argc, char** argv)
    {
            bar(argc, argv);
            return 0;
    }

  5. #5
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Define "does not work"...

    --
    Mats

  6. #6
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    This works for me:

    Code:
    #include <stdio.h>
    
    int mymain(int, char**);
    
    int mymain(int argc, char**argv)
    {
    	printf("Entering mymain......\n");
    	mymain(argc, argv);
    	return 0;
    }
    
    int main(int argc, char** argv)
    {
            mymain(argc, argv);
            return 0;
    }
    Yours compiles with the following errors:

    recurmain.c: In function `bar':
    recurmain.c:24: warning: no return statement in function returning non-void
    recurmain.c:24: warning: control reaches end of non-void function
    If I fix that with a return to 0 and run it, it ends up finishing without recursing. If I add a printf() statement, then it ends up recursing properly. Perhaps it's recognizing and optomizing the endless recursion to never occur.

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by MacGyver View Post
    This works for me:

    Code:
    #include <stdio.h>
    
    int mymain(int, char**);
    
    int mymain(int argc, char**argv)
    {
    	printf("Entering mymain......\n");
    	mymain(argc, argv);
    	return 0;
    }
    
    int main(int argc, char** argv)
    {
            mymain(argc, argv);
            return 0;
    }
    Yours compiles with the following errors:



    If I fix that with a return to 0 and run it, it ends up finishing without recursing. If I add a printf() statement, then it ends up recursing properly. Perhaps it's recognizing and optomizing the endless recursion to never occur.

    That's an invalid optimization, but I guess that it may decide that the call is just a call to itself, and since the function doesn't change anything, it will just skip the call anyways (a function that doesn't change anything, and that doesn't call anything else don't have to be called - since there's no way to detect the difference).

    --
    Mats

  8. #8
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    Yeah, I didn't expect GCC to do that, but I suppose it makes sense from their perspective. If nothing happens, especially endless recursion, why bother? lol.

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by MacGyver View Post
    Yeah, I didn't expect GCC to do that, but I suppose it makes sense from their perspective. If nothing happens, especially endless recursion, why bother? lol.
    I don't expect that they recognize infinite recursion - but they probably realizes the scall does nothing, and removes it based on that.

    --
    Mats

  10. #10
    Registered User msp's Avatar
    Join Date
    Jul 2007
    Location
    in
    Posts
    31
    Quote Originally Posted by matsp View Post
    Define "does not work"...

    --
    Mats
    Even this did not fell into an infinite recursion!

  11. #11
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > Even this did not fell into an infinite recursion!
    Look up tail recursion elimination. Such cases are handled as a jump rather than a call, and as such do not cause stack overflow.
    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.

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    As described by MacGyver, the problem is that the compiler believes that this function is a "no-operation" and eliminates the call to it. If you make the function "do something", such as increment argc, print something, return random() or something else that cause the function to actually have at least some side-effect, then you will be able to do it.

    Or try with "no optimization" in the compiler, that should make the compiler not remove the call - verify by looking at the assembler output from the compiler.

    --
    Mats

  13. #13
    Registered User msp's Avatar
    Join Date
    Jul 2007
    Location
    in
    Posts
    31
    matsp, i tried with gcc -O0 fptr.c
    but this also did not help.
    i am making an indirect recursion, through a function ptr, i thought it would work, but ...

  14. #14
    Registered User ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,732
    Quote Originally Posted by msp View Post
    matsp, i tried with gcc -O0 fptr.c
    but this also did not help.
    i am making an indirect recursion, through a function ptr, i thought it would work, but ...
    As Salem said there no way the stack can grow in this case. Since there is no code below your call to mymain. Which in case is just a jump to the mymain. Since no data is copied on to the stack. It just a infinite loop forever. If you really wanted to see the stack grows exe this simple code

    Code:
    #include <stdio.h>
    int foo()
    {
        foo();
        printf("Let the stack grow\n");
    }
    int main()
    {
        foo();
        
        getchar();   
        return 0;
    }
    You get seg fault

    ssharish2005

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by Salem View Post
    > Even this did not fell into an infinite recursion!
    Look up tail recursion elimination. Such cases are handled as a jump rather than a call, and as such do not cause stack overflow.
    My thoughts exactly.
    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"

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. convert Recursion to linear can it be done
    By umen242 in forum C++ Programming
    Replies: 2
    Last Post: 10-15-2008, 02:58 AM
  3. a simple recursion question
    By tetra in forum C++ Programming
    Replies: 6
    Last Post: 10-27-2002, 10:56 AM
  4. stack and recursion help needed!
    By LouB in forum C++ Programming
    Replies: 3
    Last Post: 07-01-2002, 02:19 PM
  5. 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