Looping and Recurring

[tim]

Hi everyone. :)

I've got a question about looping and recurring in Java. Take a look at the two programs below:
Application A

public class Main {
    public static void main(String[] args) {
        while (true) {
            System.out.println(": p");
        }
    }
}

Application B

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

#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. ;)

[quad64bit]

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.

[quad64bit]

Oh yeah, FYI, the 'Base Case' is the termination condition to prevent infinite calls. For example:

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);
    }
}

[tim]

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? ;)

[quad64bit]

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

[JosAH]

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

[tim]

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. ;)

[JosAH]

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