Results 1 to 8 of 8
  1. #1
    tim's Avatar
    tim
    tim is offline Senior Member
    Join Date
    Dec 2007
    Posts
    435
    Rep Power
    8

    Default Looping and Recurring

    Hi everyone. :)

    I've got a question about looping and recurring in Java. Take a look at the two programs below:
    Application A
    Java Code:
    public class Main {
        public static void main(String[] args) {
            while (true) {
                System.out.println(": p");
            }
        }
    }
    Application B
    Java Code:
    public class Main {
        public static void main(String[] args) {
            go();
        }
        public static void go() {
            System.out.println(": p");
            go();
        }
    }
    Now, the first one runs fine. Fairly basic. But the second one is a problem, as I expected. The Stack Overflow exception is thrown after some time of execution. The same thing happens in C++.
    Application C
    Java Code:
    #include "stdafx.h"
    #include <iostream>
    
    using namespace std;
    
    void go();
    
    void main(int argumentCount, char **aguments)
    {
        go();
        cin.get();
    }
    
    void go() {
        cout << ": p\n";
        go();
    }
    Is this just something that machines can't handle? Never ending recursion?

    Just something that caught my attention.
    Thank you. ;)
    Eyes dwelling into the past are blind to what lies in the future. Step carefully.

  2. #2
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default

    Recursion uses the System stack. Every call puts another entry into the stack. Eventually, the stack gets full and then you have a stack overflow error. Recursion is not the same as looping, rather, its a means of keeping a placeholder and calling a method from itself. In order to be useful, recursive methods must have a Base Case as well as a recursive call.

  3. #3
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default

    Oh yeah, FYI, the 'Base Case' is the termination condition to prevent infinite calls. For example:
    Java Code:
    public class Main {
        public static void main(String[] args) {
            go(10);
        }
        public static void go(int n) {
            //Base case
            if(n == 0)
                  return;
            System.out.println(": p");
            go(n-1);
        }
    }

  4. #4
    tim's Avatar
    tim
    tim is offline Senior Member
    Join Date
    Dec 2007
    Posts
    435
    Rep Power
    8

    Default

    Thank you quad64bit for your comment. I've learned that our machines are implementations of finite state machines and because of this they cannot "see into the future" and prevent stack overflows like these. So there's no way to prevent this except by reducing the problem to a finite one. I mean, what if the problem is a near-infinite problem, like traversing a really big tree? Then, do we just get a bigger computer? ;)
    Eyes dwelling into the past are blind to what lies in the future. Step carefully.

  5. #5
    quad64bit's Avatar
    quad64bit is offline Moderator
    Join Date
    Jul 2009
    Location
    VA
    Posts
    1,323
    Rep Power
    7

    Default

    "Then, do we just get a bigger computer?" Yes :D In the case of java, just add more ram to the JVM.

  6. #6
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,783
    Blog Entries
    7
    Rep Power
    21

    Default

    Most (if not all) functional languages remove tail recursion, i.e. if the last statement of a function is a call to (another?) function no 'subroutine' call is made but a simple 'jump' after erasing its own stack frame. Java isn't one of them so the stack will grow forever with this scenario.

    kind regards,

    Jos

  7. #7
    tim's Avatar
    tim
    tim is offline Senior Member
    Join Date
    Dec 2007
    Posts
    435
    Rep Power
    8

    Default

    Quote Originally Posted by JosAH View Post
    Most (if not all) functional languages remove tail recursion, i.e. if the last statement of a function is a call to (another?) function no 'subroutine' call is made but a simple 'jump' after erasing its own stack frame. Java isn't one of them so the stack will grow forever with this scenario.

    kind regards,

    Jos
    Thanks Jos! That answers my question then. :D Can you name an example of such a language, for interest's sake. ;)
    Eyes dwelling into the past are blind to what lies in the future. Step carefully.

  8. #8
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,783
    Blog Entries
    7
    Rep Power
    21

    Default

    Quote Originally Posted by tim View Post
    Thanks Jos! That answers my question then. :D Can you name an example of such a language, for interest's sake. ;)
    From experience I know that a lot of Lisp dialects do this, including Haskell, Hope and ML and my own little language RPL does it too (on demand); none of C, C++ or Java eliminate tail recursion.

    kind regards,

    Jos

Similar Threads

  1. looping and filtering
    By javafanatic in forum New To Java
    Replies: 14
    Last Post: 02-09-2010, 10:48 AM
  2. looping problems
    By Blakester in forum New To Java
    Replies: 4
    Last Post: 10-05-2009, 09:26 PM
  3. Looping problem
    By Tanilo in forum New To Java
    Replies: 1
    Last Post: 08-01-2008, 07:34 AM
  4. Looping ArrayList
    By hai789 in forum Web Frameworks
    Replies: 5
    Last Post: 05-07-2008, 04:55 AM
  5. looping a function
    By Username in forum New To Java
    Replies: 2
    Last Post: 07-30-2007, 06:37 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •