Вектор in discuse

[amarao]

Я правильно понимаю, что любой рекурсивный алгоритм неявно использует стек, который, в свою очередь, всего лишь модная версия Vec? То есть когда кто-то изящно решает задачу на списках с помощью рекурсии, то он просто показывает как с помощью синтакстического сахара языка переложить список в вектор?

Comments

[juan_gandhi]

Ну почему, есть же хвостовая рекурсия, там стек не нужен.

[aklepatc]

А чем принципиально отличается хвостовая? Если не трудно и возможно "в двух словах"...
Спасибо!

UPD: нагуглил. Вроде стэк всё равно нужен? Просто можно сэкономить один frame?

[permeakra]

https://en.wikipedia.org/wiki/Tail_call#In_assembly

[aklepatc]

Кажется понял. Ещё раз спасибо!
То есть у нас, при хорошем раскладе, будет задействован всего один stack frame на всю цепочку рекурсивных вызовов, так?

[permeakra]

Да.

Задание на дом - взять классическое двоичное дерево* и модифицировать его так, чтобы рекурсивный обход можно было выполнить в одном стек фрейме.

* Узел дерева
struct Tree
{ int payload; Tree* left; Tree* right;}

[juan_gandhi]

Стек не нужен. Вместо call - фактически goto. Как цикл.

[aklepatc]

Разумно. Спасибо!

[straktor]

> стек, который, в свою очередь, всего лишь модная версия Vec

доступа по индексу в стеке (высокоуровневого языка) нету например

> как с помощью синтакстического сахара языка переложить список в вектор

я писал на бейсике поиск пути в графе, естественно без функций-параметров и даже gosub
с сахаром код намного понятней

разумеется любой рекурсивный алгоритм можно перевести на явный стек с goto, которые возможно моделировать структурным кодом со switch
чаще всего будет лапша