Вектор in discuse
Dec. 13th, 2022 06:48 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
amaraoЯ правильно понимаю, что любой рекурсивный алгоритм неявно использует стек, который, в свою очередь, всего лишь модная версия Vec? То есть когда кто-то изящно решает задачу на списках с помощью рекурсии, то он просто показывает как с помощью синтакстического сахара языка переложить список в вектор?
no subject
Date: 2022-12-13 04:53 pm (UTC)Ну почему, есть же хвостовая рекурсия, там стек не нужен.
no subject
Date: 2022-12-13 08:17 pm (UTC)Спасибо!
UPD: нагуглил. Вроде стэк всё равно нужен? Просто можно сэкономить один frame?
no subject
Date: 2022-12-13 08:33 pm (UTC)no subject
Date: 2022-12-13 08:55 pm (UTC)То есть у нас, при хорошем раскладе, будет задействован всего один stack frame на всю цепочку рекурсивных вызовов, так?
no subject
Date: 2022-12-13 08:59 pm (UTC)Задание на дом - взять классическое двоичное дерево* и модифицировать его так, чтобы рекурсивный обход можно было выполнить в одном стек фрейме.
* Узел дерева
struct Tree
{ int payload; Tree* left; Tree* right;}
no subject
Date: 2022-12-13 09:21 pm (UTC)Стек не нужен. Вместо call - фактически goto. Как цикл.
no subject
Date: 2022-12-13 09:28 pm (UTC)no subject
Date: 2022-12-13 10:01 pm (UTC)доступа по индексу в стеке (высокоуровневого языка) нету например
> как с помощью синтакстического сахара языка переложить список в вектор
я писал на бейсике поиск пути в графе, естественно без функций-параметров и даже gosub
с сахаром код намного понятней
разумеется любой рекурсивный алгоритм можно перевести на явный стек с goto, которые возможно моделировать структурным кодом со switch
чаще всего будет лапша