Растет ли стек, если рекурсивный вызов функции — последняя операция?

Question

[JustFailer]

Прошу прощения, если вопрос некорректен.
Например, имеется функция вида:

void doSomething() {
    // [...]
    if (a==0) {
        doSomething();
    }
}

В тэгах и C++, и Java т.к. интересны отличия.

Answer 1

[Сергей Горностаев]

В Java нет оптимизации хвостовой рекурсии.

Answer 2

[maaGames]

(С++)Сохраняется адрес возврата, так что растёт. Про Java не знаю, как ВМ реализована.
Всегда можно запустить бесконечную рекурсию и посмотреть, растёт ли память.)

Comments

[Денис Загаевский]

А вот тут говорят, что некоторые компиляторы С++ вполне себе поддерживают оптимизацию хвостовой рекурсии.

[maaGames]

Денис Загаевский: А ещё некоторые компиляторы разворачивают циклы и вообще подставляют результат, вместо формул. В любом случае, глубина инлайна рекурсии ограничена довольно маленьким числом (точно не помню, чуть ли ни 8 подстановок всего). Раз был вопрос про использование памяти, то рекурсия имеет глубину тысячи вызовов... Или чисто теоретический вопрос был.

[Денис Загаевский]

maaGames: смысл хвостовой рекурсии в том, что вызов выполняется в том же фрейме. И нужно это именно для того, чтобы избежать переполнения стека.

[maaGames]

Денис Загаевский: Да, я уже погуглил. Не правильно понял что за хвостовая рекурсия. Даже и не знал, что компиляторы уже умеют заменять рекурсию на циклы. Прикольненько.

[Андрей]

Денис Загаевский: если выполняется на том же стеке, то может есть смысл в цикл развернуть ?

[Максим Мосейчук]

Денис Загаевский: оптимизацию поддерживают, но не гарантируют. Из-за этого использовать не рекомендуется.

В scala, например, функцию можно объявить с аннотацией tailrec. Если такая функция не может быть оптимизирована, то будет ошибка времени компиляции.

[Денис Загаевский]

Андрей: Может и есть. Примерно это и происходит при оптимизации хвостовой рекурсии.
fshp: То, что не гарантируется - это уже другой разговор. Наверное, можно почитать доки по компилятору и узнать, в каких случаях он это делать будет %)