Java: проблемы с пониманием рекурсивного вызова метода

Question

Надеюсь, у вас всех хороший день.

Мой учитель сбил с меня штаны.Я прочитал мою книгу и исследовал, но я все еще в замешательстве.Я только сейчас изучаю методы, поэтому мне предстоит долгий путь.Я создал игру, похожую на «Oregon Trail», в которой используется метод «игра окончена», чтобы узнать, хочет ли пользователь снова играть.

Основная проблема: мой учитель упомянул что-то неопределенное о том, что если игра зациклится достаточно много раз, мы получим стек переполнением.Это имеет смысл для меня, потому что игра продолжает вкладывать методы друг в друга так, как я это делаю, добавляя в стек каждый раз, когда вызывается метод «новая игра», потому что внешние методы все еще там ожидают завершения.

Я привел пример того, что я имею в виду.Предполагая, что были какие-то паузы для пользовательского ввода и тому подобное, как я должен быть уверен, что использование памяти не будет расти, когда я вызываю методы внутри других методов?Я думаю, что слово для этого - «рекурсивный», таким образом, мой заголовок.

Пожалуйста, если кто-то мог бы порекомендовать хорошую форму для решения этой проблемы, я был бы очень благодарен.

public class Testing
{
    public static void main(String[] args) {
        System.out.println("main method");
        gameStart();
    }

    private static void gameStart()
    {
        System.out.println("some other method called");
        gameOver();
    }

    private static void gameOver()
    {
        System.out.println("game over called"); //I would ask the user if they want to play again.
        //keeping it concise to illustrate my point, instead of using an if statement
        gameStart();//starting the cycle I'm concerned about. Assume the user indicated they would like to play again.
    }
}

Answer 1

Чтобы избежать неограниченной рекурсии, вы можете переключиться на итерацию и ввести возвращаемые значения для тех методов, которые в настоящее время решают, как поступить (в настоящее время непосредственно вызывая соответствующие действия).Пусть эти методы возвращают знак того, что делать дальше, например, используя enum.Затем напишите цикл, который вызывает правильные методы в зависимости от возвращаемых значений.

Пример (сокращенно, я предполагаю, что вы знаете синтаксис Java):

enum Action { Start, ShowEnd, Quit }

main:

Action nextAction = Action.Start;
while (action != Action.Quit)
{
    switch (action)
    {
        case Start:
            nextAction = gameStart();
            break;
        case ShowEnd:
            nextAction = gameEnd();
            break;
        // ToDo: write more actions!
        default:
            break;
    }
}

Это предполагает, что каждый такой метод выполняется до тех пор, пока не будет принято решение о том, какое действие следует предпринять.

Таким образом, ваш стек вызовов всегда будет достаточно плоским, поскольку выполнение всегда возвращается к методу main, а затемразветвляется на другие методы.

Answer 2

Когда вы пишете рекурсивный код, вы должны убедиться, что у вас есть какое-то конечное условие, ЗАКРЫВАЮЩЕЕ вызов функции снова.Например, я добавил конечное условие для метода gameOver с помощью if(gamePlayedThisManyTimes <= 1) return;.При выполнении следующего кода значение, которое вы дадите методу gameStart, определит, сколько игр вы играете, и gameOver уменьшит значение, когда вызовет 'gameStart', чтобы в конечном итоге достичь этого конечного условия рекурсии.

public static void main(String[] args)
{
    System.out.println("main method");
    gameStart(10);
}

private static void gameStart(int playGameThisManyTimes)
{
    System.out.println("Game " + playGameThisManyTimes + " started...");
    System.out.println("some other method called");
    gameOver(playGameThisManyTimes);
}

private static void gameOver(int gamePlayedThisManyTimes)
{
    System.out.println("game over called for " + gamePlayedThisManyTimes); //I would ask the user if they want to play again.

    if(gamePlayedThisManyTimes <= 1)
        return;
    else
        gameStart(gamePlayedThisManyTimes - 1);
}

Выход

main method
Game 10 started...
some other method called
game over called for 10
Game 9 started...
some other method called
game over called for 9
Game 8 started...
some other method called
game over called for 8
Game 7 started...
some other method called
game over called for 7
Game 6 started...
some other method called
game over called for 6
Game 5 started...
some other method called
game over called for 5
Game 4 started...
some other method called
game over called for 4
Game 3 started...
some other method called
game over called for 3
Game 2 started...
some other method called
game over called for 2
Game 1 started...
some other method called
game over called for 1

Answer 3

Рекурсии необходимо условие, при котором она не продолжит вызывать.
Рекурсия чаще всего наблюдается там, где метод сам вызывает , например, для вычисления последовательности Фибоначчи, где

fib(n) == fib(n-1) + fib(n-2)

fib(0) определяется как 0, поэтому вам не нужно вычислять.
fib(1) определяется как 1, поэтому вам не нужно вычислять.
Любое другое числовычисляется методом fib(), вызывающим себя дважды , но он избегает выполнения рекурсивного вызова для двух определенных случаев, когда вычислять нечего.В псевдокоде

int fib(int n)
{
    if (n == 0) return 0; // doesnt have to recursively call
    if (n == 1) return 1; // same
    return fib(n-1) + fib(n-2);
}

В вашем случае у вас есть два метода, которые вызывают друг друга , но у вас нет условия, когда вызовы могут избежать этого.

Возможно, что gameOver() звонит gameStart() только тогда, когда игра заканчивается ничьей, что-то вроде

public class Testing
{
    public static void main(String[] args) {
        System.out.println("main method");
        gameStart();
    }

    private static void gameStart()
    {
        System.out.println("some other method called");
        gameOver();
    }

    private static void gameOver()
    {
        System.out.println("game over called");
        if (gameTied()) {
            gameStart();
        }
    }
}

Если вы просто спрашиваете "хотите ли вы играть снова?"- это было бы лучше сделать в main, в соответствии с

public static void main(String[] args) {
    System.out.println("main method");
    String playGame = "Yes";
    while (playGame.equalsIgnoreCase("Yes") {
        gameStart();
        playGame = ask("Play again?");
    }
}