Как полностью выйти из функции с рекурсией и циклом бесконечной вложенности?
Есть функция, которая с использованием рекурсии перебирает элементы массива неограниченной вложенности на соответствие определённому критерию. Обнаружив первый попавшийся элемент, соответствующий критерию, функция должна тут же вернуть 1.
Проблема в том, что из-за рекурсии, если я пишу return 1, значение возвращается в «родительскую» копию функции, и цикл продолжается. Если я пишу break 1/2/3/4 и т. д.- я завершаю лишь конкретный цикл, по вложенности относительно текущего, а у меня их может быть хоть миллион. Есть какая-то возможность скомандовать остановку всех циклов и возвращение значения 1?
Пока нашел только проверку значения возвращаемого вызванной копией — если 1, то все вложенные копии возвращают родителю 1, пока не дойдёт до самой первой.
Есть ли какое-то универсальное решение, которое останавливает самый первый цикл (break) или команда остановки самой первой копии функции (return)?
PHP 5.6, процедурный стиль.
- Вопрос задан более трёх лет назад
- 6683 просмотра
Как выйти из рекурсии c
Рекурсивные функции — это функции, которые вызывают сами себя. Такие функции довольно часто используются для обхода различных представлений. Например, если нам надо найти определенный файл в папке, то мы сначала смотрим все файлы в этой папке, затем смотрим все ее подпак
Например, определим вычисление факториала в виде рекурсивной функции:
#include unsigned long long factorial(unsigned); int main() < unsigned n ; auto result < factorial(n)>; std::cout unsigned long long factorial(unsigned n) < if(n >1) return n * factorial(n-1); return 1; >
В функции factorial задано условие, что если число n больше 1, то это число умножается на результат этой же функции, в которую в качестве параметра передается число n-1. То есть происходит рекурсивный спуск. И так далее, пока не дойдем того момента, когда значение параметра не будет равно 1. В этом случае функция возвратит 1.
Рекурсивная функция обязательно должна иметь некоторый базовый вариант, который использует оператор return и к которому сходится выполнение остальных вызовов этой функции. В случае с факториалом базовый вариант представлен ситуацией, при которой n = 1. В этом случае сработает инструкция return 1; .
Например, при вызове factorial(5) получится следующая цепь вызовов:
- 5 * factorial(4)
- 5 * 4 * factorial(3)
- 5 * 4 * 3 * factorial(2)
- 5 * 4 * 3 * 2 * factorial(1)
- 5 * 4 * 3 * 2 * 1
Другим распространенным показательным примером рекурсивной функции служит функция, вычисляющая числа Фиббоначчи. n-й член последовательности чисел Фибоначчи определяется по формуле: f(n)=f(n-1) + f(n-2), причем f(0)=0, а f(1)=1. Значения f(0)=0 и f(1)=1, таким образом, определяют базовые варианты для данной функции:
#include unsigned long long fib(unsigned); int main() < for(unsigned i<>; i < 10; i++) < auto n = fib(i); std::cout std::cout unsigned long long fib(unsigned n)
Результат работы программы — вывод 10 чисел из последовательности Фиббоначчи на консоль:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34
В примерах выше функция напрямую вызывала саму себя. Но рекурсивный вызов функции также может быть косвенным. Например, функция fun1() вызывает другую функцию fun2(), которая, в свою очередь, вызывает fun1(). В этом случае функции fun1() и fun2() также называются взаимно рекурсивными функциями.
Стоит отметить, что нередко рекурсивные функции можно представить в виде циклов. Например, для вычисления факториала вместо рекурсии используем цикл:
#include unsigned long long factorial(unsigned); int main() < unsigned n ; std::cout unsigned long long factorial(unsigned n) < unsigned long long result; for(unsigned i; i return result; >
И нередко циклические конструкции более эффективны, чем рексурсия. Например, если функция вызывает себя тысячи раз, потребуется большой объем стековой памяти для хранения копий значений аргументов и адреса возврата для каждого вызова, что может привести к тому, что программа быстро исчерпает выделенную для нее память стека, поскольку объем памяти стека обычно фиксирован и ограничен. что может привести к аварийному завершению программы. Поэтому в таких случаях, как правило, лучше использовать альтернативные подходы, например цикл. Однако, несмотря на накладные расходы, использование рекурсии часто может значительно упростить написание программы.
- Глава 1. Введение в С++
- Язык программирования С++
- Первая программа на Windows. Компилятор g++
- Первая программа на Windows. Компилятор Clang
- Первая программа на Windows. Компилятор Microsoft Visual C++
- Первая программа на Linux. Компилятор g++
- Первая программа на MacOS. Компилятор Clang
- Настройка параметров компиляции
- Локализация и кириллица в консоли
- Структура программы
- Переменные
- Типы данных
- Константы
- Ввод и вывод в консоли
- using. Подключение пространств имен и определение псевдонимов
- Арифметические операции
- Статическая типизация и преобразования типов
- Поразрядные операции
- Операции присваивания
- Условные выражения
- Конструкция if-else и тернарный оператор
- Конструкция switch-case
- Циклы
- Ссылки
- Массивы
- Многомерные массивы
- Массивы символов
- Введение в строки
- Что такое указатели
- Операции с указателями
- Арифметика указателей
- Константы и указатели
- Указатели и массивы
- Определение и объявление функций
- Область видимости объектов
- Параметры функции
- Передача аргументов по значению и по ссылке
- Константные параметры
- Оператор return и возвращение результата
- Указатели в параметрах функции
- Массивы в параметрах функции
- Параметры функции main
- Возвращение указателей и ссылок
- Перегрузка функций
- Рекурсивные функции
- Рекурсия на примере быстрой сортировки
- Указатели на функции
- Указатели на функции как параметры
- Тип функции
- Указатель на функцию как возвращаемое значение
- Разделение программы на файлы
- Внешние объекты
- Динамические объекты
- Динамические массивы
- unique_ptr
- shared_ptr
- Определение классов
- Конструкторы и инициализация объектов
- Управление доступом. Инкапсуляция
- Объявление и определение функций класса
- Конструктор копирования
- Константные объекты и функции
- Ключевое слово this
- Дружественные функции и классы
- Статические члены класса
- Деструктор
- Структуры
- Перечисления
- Наследование
- Управление доступом в базовых и производных классах
- Скрытие функционала базового класса
- Множественное наследование
- Виртуальные функции и их переопределение
- Преобразование типов
- Динамическое преобразование
- Особенности динамического связывания
- Чистые виртуальные функции и абстрактные классы
- Перегрузка операторов
- Операторы преобразования типов
- Оператор индексирования
- Переопределение оператора присваивания
- Пространства имен
- Вложенные классы
- Обработка исключений
- Вложенные try-catch
- Создание своих типов исключений
- Тип exception
- Типы исключений
- Шаблоны функций
- Шаблон класса
- Специализация шаблона класса
- Наследование и шаблоны классов
- Типы контейнеров
- Вектор
- Итераторы
- Операции с векторами
- Array
- List
- Forward_list
- Deque
- Стек std::stack
- Очередь std::queue
- Очередь приоритетов std::priority_queue
- Множества
- Словарь std::map
- Span
- Определение строк
- Строки с поддержкой Unicode
- Преобразование типов и строки
- Сравнение строк
- Получение подстроки и проверка начала и конца строки
- Поиск подстроки
- Изменение строки
- Операции с символами
- Программа подсчета слов
- Тип std:string_view
- rvalue
- Конструктор перемещения
- Оператор присваивания с перемещением
- Роль noexcept при перемещении
- Объекты функций
- Лямбда-выражения
- Захват внешних значений в лямбда-выражениях
- Шаблон std::function<>
- Минимальный и максимальный элементы
- Поиск элементов
- Копирование элементов
- Удаление элементов и идиома Remove-Erase Idiom
- Сортировка
- Представления. Фильтрация
- Проекция данных
- Пропуск элементов. drop_view и drop_while_view
- Извлечение диапазона элементов. take_view и take_while_view
- Цепочки представлений
- Оператор requires
- Концепты
- Выражение requires
- Ограничения типа для auto
- Базовые типы для работы с потоками
- Файловые потоки. Открытие и закрытие
- Чтение и запись текстовых файлов
- Переопределение операторов ввода и вывода
- Математические константы и операции
- Форматирование строк и функция format
- std::optional
- Управление ресурсами. Идиома RAII
- Идиома копирования и замены
- Идиома Move-and-Swap
- Первая программа в Visual Studio
- Первая программа в Qt Creator
Как выйти из рекурсии c
Собственно возврат стоит в самом начале а она один хер пробегает все дерево ваще недогоняю почему отладчиком статус все функции бывает истина
Процедура ЗаписатьЗначениеВ_ТЗБ(ТабПараметров,Стр,Ветка,ЭтоПлан=Ложь,Ключ=»»,СтатусВсейФункции=Ложь)
Если СтатусВсейФункции Тогда
Возврат;
КонецЕсли;
СтатусФункции =Ложь;
Для Каждого Узел Из Ветка.Строки Цикл
ИдентификаторУзла= Узел.N;
НаименованиеУзла = Узел.Наименование;
ЭтоНоваяСтрока=НаименованиеУзла = «Структура бюжета ООО ‘Интерполис'»;
Если ЭтоНоваяСтрока Тогда
Попытка
Если СтатусПроверкиТекущихДанных=0 Тогда
ЗаписатьТзВотстойник(ПредИдущаяТаблица);
КонецЕсли;
Исключение
КонецПопытки;
СтатусПроверкиТекущихДанных=0;
КонецЕсли;
ПредИдущаяТаблица=ТабПараметров;
Если ИдентификаторУзла<>Неопределено ТОгда
УровеньУзла= Узел.Уровень();
ЗначениеВетки= Узел.Значение;
НаименованиеВетки=СокрЛП(Узел.Наименование);
Если не ЭтоПлан или Ключ=ИдентификаторУзла Тогда
СтатусФункции = ПроверитьЗначениеВТЗБ(Узел,УровеньУзла,ЗначениеВетки,НаименованиеВетки,ТабПараметров,Стр,ИдентификаторУзла,ЭтоПлан);
Если СтатусФункции Тогда
СтатусПроверкиТекущихДанных=СтатусПроверкиТекущихДанных+1;
КонецЕсли;
КонецЕсли;
КонецЕсли;
ЗаписатьЗначениеВ_ТЗБ(ТабПараметров,Стр,Узел,ЭтоПлан,Ключ,СтатусФункции)
КонецЦикла;
КонецПроцедурыа возврат происходит в первом вызове? раскрутка стэка
Рекурсия и стек
Если вы не новичок в программировании, то, возможно, уже знакомы с рекурсией и можете пропустить эту главу.
Рекурсия – это приём программирования, полезный в ситуациях, когда задача может быть естественно разделена на несколько аналогичных, но более простых задач. Или когда задача может быть упрощена до несложных действий плюс простой вариант той же задачи. Или, как мы скоро увидим, для работы с определёнными структурами данных.
В процессе выполнения задачи в теле функции могут быть вызваны другие функции для выполнения подзадач. Частный случай подвызова – когда функция вызывает сама себя. Это как раз и называется рекурсией.
Два способа мышления
В качестве первого примера напишем функцию pow(x, n) , которая возводит x в натуральную степень n . Иначе говоря, умножает x на само себя n раз.
pow(2, 2) = 4 pow(2, 3) = 8 pow(2, 4) = 16Рассмотрим два способа её реализации.
-
Итеративный способ: цикл for :
function pow(x, n) < let result = 1; // умножаем result на x n раз в цикле for (let i = 0; i < n; i++) < result *= x; >return result; > alert( pow(2, 3) ); // 8function pow(x, n) < if (n == 1) < return x; >else < return x * pow(x, n - 1); >> alert( pow(2, 3) ); // 8Обратите внимание, что рекурсивный вариант отличается принципиально.
Когда функция pow(x, n) вызывается, исполнение делится на две ветви:
if n==1 = x / pow(x, n) = \ else = x * pow(x, n - 1)- Если n == 1 , тогда всё просто. Эта ветвь называется базой рекурсии, потому что сразу же приводит к очевидному результату: pow(x, 1) равно x .
- Мы можем представить pow(x, n) в виде: x * pow(x, n — 1) . Что в математике записывается как: x n = x * x n-1 . Эта ветвь – шаг рекурсии: мы сводим задачу к более простому действию (умножение на x ) и более простой аналогичной задаче ( pow с меньшим n ). Последующие шаги упрощают задачу всё больше и больше, пока n не достигает 1 .
Говорят, что функция pow рекурсивно вызывает саму себя до n == 1 .
Например, рекурсивный вариант вычисления pow(2, 4) состоит из шагов:
- pow(2, 4) = 2 * pow(2, 3)
- pow(2, 3) = 2 * pow(2, 2)
- pow(2, 2) = 2 * pow(2, 1)
- pow(2, 1) = 2
Итак, рекурсию используют, когда вычисление функции можно свести к её более простому вызову, а его – к ещё более простому и так далее, пока значение не станет очевидно.
Рекурсивное решение обычно короче
Рекурсивное решение задачи обычно короче, чем итеративное.
Используя условный оператор ? вместо if , мы можем переписать pow(x, n) , делая код функции более лаконичным, но всё ещё легко читаемым:
function pow(x, n)
Общее количество вложенных вызовов (включая первый) называют глубиной рекурсии. В нашем случае она будет равна n .
Максимальная глубина рекурсии ограничена движком JavaScript. Точно можно рассчитывать на 10000 вложенных вызовов, некоторые интерпретаторы допускают и больше, но для большинства из них 100000 вызовов – за пределами возможностей. Существуют автоматические оптимизации, помогающие избежать переполнения стека вызовов («оптимизация хвостовой рекурсии»), но они ещё не поддерживаются везде и работают только для простых случаев.
Это ограничивает применение рекурсии, но она всё равно широко распространена: для решения большого числа задач рекурсивный способ решения даёт более простой код, который легче поддерживать.
Контекст выполнения, стек
Теперь мы посмотрим, как работают рекурсивные вызовы. Для этого заглянем «под капот» функций.
Информация о процессе выполнения запущенной функции хранится в её контексте выполнения (execution context).
Контекст выполнения – специальная внутренняя структура данных, которая содержит информацию о вызове функции. Она включает в себя конкретное место в коде, на котором находится интерпретатор, локальные переменные функции, значение this (мы не используем его в данном примере) и прочую служебную информацию.
Один вызов функции имеет ровно один контекст выполнения, связанный с ним.
Когда функция производит вложенный вызов, происходит следующее:
- Выполнение текущей функции приостанавливается.
- Контекст выполнения, связанный с ней, запоминается в специальной структуре данных – стеке контекстов выполнения.
- Выполняются вложенные вызовы, для каждого из которых создаётся свой контекст выполнения.
- После их завершения старый контекст достаётся из стека, и выполнение внешней функции возобновляется с того места, где она была остановлена.
Разберёмся с контекстами более подробно на примере вызова функции pow(2, 3) .
pow(2, 3)
В начале вызова pow(2, 3) контекст выполнения будет хранить переменные: x = 2, n = 3 , выполнение находится на первой строке функции.
Можно схематически изобразить это так:
Это только начало выполнения функции. Условие n == 1 ложно, поэтому выполнение идёт во вторую ветку if :
function pow(x, n) < if (n == 1) < return x; >else < return x * pow(x, n - 1); >> alert( pow(2, 3) );Значения переменных те же самые, но выполнение функции перешло к другой строке, актуальный контекст:
Чтобы вычислить выражение x * pow(x, n — 1) , требуется произвести запуск pow с новыми аргументами pow(2, 2) .
pow(2, 2)
Для выполнения вложенного вызова JavaScript запоминает текущий контекст выполнения в стеке контекстов выполнения.
Здесь мы вызываем ту же функцию pow , однако это абсолютно неважно. Для любых функций процесс одинаков:
- Текущий контекст «запоминается» на вершине стека.
- Создаётся новый контекст для вложенного вызова.
- Когда выполнение вложенного вызова заканчивается – контекст предыдущего вызова восстанавливается, и выполнение соответствующей функции продолжается.
Вид контекста в начале выполнения вложенного вызова pow(2, 2) :
Новый контекст выполнения находится на вершине стека (и выделен жирным), а предыдущие запомненные контексты – под ним.
Когда выполнение подвызова закончится, можно будет легко вернуться назад, потому что контекст сохраняет как переменные, так и точное место кода, в котором он остановился. Слово «строка» на рисунках условно, на самом деле запоминается более точное место в цепочке команд.
pow(2, 1)
Процесс повторяется: производится новый вызов в строке 5 , теперь с аргументами x=2 , n=1 .
Создаётся новый контекст выполнения, предыдущий контекст добавляется в стек:
Теперь в стеке два старых контекста и один текущий для pow(2, 1) .
Выход
При выполнении pow(2, 1) , в отличие от предыдущих запусков, условие n == 1 истинно, поэтому выполняется первая ветка условия if :
function pow(x, n) < if (n == 1) < return x; >else < return x * pow(x, n - 1); >>Вложенных вызовов больше нет, поэтому функция завершается, возвращая 2 .
Когда функция заканчивается, контекст её выполнения больше не нужен, поэтому он удаляется из памяти, а из стека восстанавливается предыдущий:
Возобновляется обработка вызова pow(2, 2) . Имея результат pow(2, 1) , он может закончить свою работу x * pow(x, n — 1) , вернув 4 .
Восстанавливается контекст предыдущего вызова:
Самый внешний вызов заканчивает свою работу, его результат: pow(2, 3) = 8 .
Глубина рекурсии в данном случае составила 3.
Как видно из иллюстраций выше, глубина рекурсии равна максимальному числу контекстов, одновременно хранимых в стеке.
Обратим внимание на требования к памяти. Рекурсия приводит к хранению всех данных для неоконченных внешних вызовов в стеке, и в данном случае это приводит к тому, что возведение в степень n хранит в памяти n различных контекстов.
Реализация возведения в степень через цикл гораздо более экономна:
function pow(x, n) < let result = 1; for (let i = 0; i < n; i++) < result *= x; >return result; >Итеративный вариант функции pow использует один контекст, в котором будут последовательно меняться значения i и result . При этом объём затрачиваемой памяти небольшой, фиксированный и не зависит от n .
Любая рекурсия может быть переделана в цикл. Как правило, вариант с циклом будет эффективнее.
Но переделка рекурсии в цикл может быть нетривиальной, особенно когда в функции в зависимости от условий используются различные рекурсивные подвызовы, результаты которых объединяются, или когда ветвление более сложное. Оптимизация может быть ненужной и совершенно нестоящей усилий.
Часто код с использованием рекурсии более короткий, лёгкий для понимания и поддержки. Оптимизация требуется не везде, как правило, нам важен хороший код, поэтому она и используется.
Рекурсивные обходы
Другим отличным применением рекурсии является рекурсивный обход.
Представьте, у нас есть компания. Структура персонала может быть представлена как объект:
let company = < sales: [< name: 'John', salary: 1000 >, < name: 'Alice', salary: 600 >], development: < sites: [< name: 'Peter', salary: 2000 >, < name: 'Alex', salary: 1800 >], internals: [< name: 'Jack', salary: 1300 >] > >;Другими словами, в компании есть отделы.
- Отдел может состоять из массива работников. Например, в отделе sales работают 2 сотрудника: Джон и Алиса.
- Или отдел может быть разделён на подотделы, например, отдел development состоит из подотделов: sites и internals . В каждом подотделе есть свой персонал.
- Также возможно, что при росте подотдела он делится на подразделения (или команды). Например, подотдел sites в будущем может быть разделён на команды siteA и siteB . И потенциально они могут быть разделены ещё. Этого нет на картинке, просто нужно иметь это в виду.
Теперь, допустим, нам нужна функция для получения суммы всех зарплат. Как мы можем это сделать?
Итеративный подход не прост, потому что структура довольно сложная. Первая идея заключается в том, чтобы сделать цикл for поверх объекта company с вложенным циклом над отделами 1-го уровня вложенности. Но затем нам нужно больше вложенных циклов для итераций над сотрудниками отделов второго уровня, таких как sites … А затем ещё один цикл по отделам 3-го уровня, которые могут появиться в будущем? Если мы поместим в код 3-4 вложенных цикла для обхода одного объекта, то это будет довольно некрасиво.
Давайте попробуем рекурсию.
Как мы видим, когда наша функция получает отдел для подсчёта суммы зарплат, есть два возможных случая:
- Либо это «простой» отдел с массивом – тогда мы сможем суммировать зарплаты в простом цикле.
- Или это объект с N подотделами – тогда мы можем сделать N рекурсивных вызовов, чтобы получить сумму для каждого из подотделов, и объединить результаты.
Случай (1), когда мы получили массив, является базой рекурсии, тривиальным случаем.
Случай (2), при получении объекта, является шагом рекурсии. Сложная задача разделяется на подзадачи для подотделов. Они могут, в свою очередь, снова разделиться на подотделы, но рано или поздно это разделение закончится, и решение сведётся к случаю (1).
Алгоритм даже проще читается в виде кода:
let company = < // тот же самый объект, сжатый для краткости sales: [, ], development: < sites: [, ], internals: [] > >; // Функция для подсчёта суммы зарплат function sumSalaries(department) < if (Array.isArray(department)) < // случай (1) return department.reduce((prev, current) =>prev + current.salary, 0); // сумма элементов массива > else < // случай (2) let sum = 0; for (let subdep of Object.values(department)) < sum += sumSalaries(subdep); // рекурсивно вызывается для подотделов, суммируя результаты >return sum; > > alert(sumSalaries(company)); // 6700Код краток и прост для понимания (надеюсь?). В этом сила рекурсии. Она работает на любом уровне вложенности отделов.
Принцип прост: для объекта <. >используются рекурсивные вызовы, а массивы [. ] являются «листьями» дерева рекурсии, они сразу дают результат.
Обратите внимание, что в коде используются возможности, о которых мы говорили ранее:
- Метод arr.reduce из главы Методы массивов для получения суммы элементов массива.
- Цикл for(val of Object.values(obj)) для итерации по значениям объекта: Object.values возвращает массив значений.
Рекурсивные структуры
Рекурсивная (рекурсивно определяемая) структура данных – это структура, которая повторяет саму себя в своих частях.
Мы только что видели это на примере структуры компании выше.
Отдел компании – это:
- Либо массив людей.
- Либо объект с отделами.
Для веб-разработчиков существуют гораздо более известные примеры: HTML- и XML-документы.
В HTML-документе HTML-тег может содержать:
- Фрагменты текста.
- HTML-комментарии.
- Другие HTML-теги (которые, в свою очередь, могут содержать фрагменты текста/комментарии или другие теги и т.д.).
Это снова рекурсивное определение.
Для лучшего понимания мы рассмотрим ещё одну рекурсивную структуру под названием «связанный список», которая в некоторых случаях может использоваться в качестве альтернативы массиву.
Связанный список
Представьте себе, что мы хотим хранить упорядоченный список объектов.
Естественным выбором будет массив:
let arr = [obj1, obj2, obj3];…Но у массивов есть недостатки. Операции «удалить элемент» и «вставить элемент» являются дорогостоящими. Например, операция arr.unshift(obj) должна переиндексировать все элементы, чтобы освободить место для нового obj , и, если массив большой, на это потребуется время. То же самое с arr.shift() .
Единственные структурные изменения, не требующие массовой переиндексации – это изменения, которые выполняются с конца массива: arr.push/pop . Таким образом, массив может быть довольно медленным для больших очередей, когда нам приходится работать с его началом.
Или же, если нам действительно нужны быстрые вставка/удаление, мы можем выбрать другую структуру данных, называемую связанный список.
Элемент связанного списка определяется рекурсивно как объект с:
- value ,
- next – свойство, ссылающееся на следующий элемент связанного списка или null , если это последний элемент.
let list = < value: 1, next: < value: 2, next: < value: 3, next: < value: 4, next: null >> > >;Графическое представление списка:
Альтернативный код для создания:
let list = < value: 1 >; list.next = < value: 2 >; list.next.next = < value: 3 >; list.next.next.next = < value: 4 >; list.next.next.next.next = null;Здесь мы можем ещё лучше увидеть, что есть несколько объектов, каждый из которых имеет value и next , указывающий на соседа. Переменная list является первым объектом в цепочке, поэтому, следуя по указателям next из неё, мы можем попасть в любой элемент.
Список можно легко разделить на несколько частей и впоследствии объединить обратно:
let secondList = list.next.next; list.next.next = null;list.next.next = secondList;И, конечно, мы можем вставить или удалить элементы из любого места.
Например, для добавления нового элемента нам нужно обновить первый элемент списка:
let list = < value: 1 >; list.next = < value: 2 >; list.next.next = < value: 3 >; list.next.next.next = < value: 4 >; list.next.next.next.next = null; // добавление нового элемента в список list = < value: "new item", next: list >;Чтобы удалить элемент из середины списка, нужно изменить значение next предыдущего элемента:
list.next = list.next.next;list.next перепрыгнуло с 1 на значение 2 . Значение 1 теперь исключено из цепочки. Если оно не хранится где-нибудь ещё, оно будет автоматически удалено из памяти.
В отличие от массивов, нет перенумерации, элементы легко переставляются.
Естественно, списки не всегда лучше массивов. В противном случае все пользовались бы только списками.
Главным недостатком является то, что мы не можем легко получить доступ к элементу по его индексу. В простом массиве: arr[n] является прямой ссылкой. Но в списке мы должны начать с первого элемента и перейти в next N раз, чтобы получить N-й элемент.
…Но нам не всегда нужны такие операции. Например, нам может быть нужна очередь или даже двухсторонняя очередь – это упорядоченная структура, которая позволяет очень быстро добавлять/удалять элементы с обоих концов, но там не нужен доступ в середину.
Списки могут быть улучшены:
- Можно добавить свойство prev в дополнение к next для ссылки на предыдущий элемент, чтобы легко двигаться по списку назад.
- Можно также добавить переменную tail , которая будет ссылаться на последний элемент списка (и обновлять её при добавлении/удалении элементов с конца).
- …Возможны другие изменения: главное, чтобы структура данных соответствовала нашим задачам с точки зрения производительности и удобства.
Итого
- Рекурсия – это термин в программировании, означающий вызов функцией самой себя. Рекурсивные функции могут быть использованы для элегантного решения определённых задач. Когда функция вызывает саму себя, это называется шагом рекурсии. База рекурсии – это такие аргументы функции, которые делают задачу настолько простой, что решение не требует дальнейших вложенных вызовов.
- Рекурсивно определяемая структура данных – это структура данных, которая может быть определена с использованием самой себя. Например, связанный список может быть определён как структура данных, состоящая из объекта, содержащего ссылку на список (или null).
list = < value, next ->list >Любая рекурсивная функция может быть переписана в итеративную. И это иногда требуется для оптимизации работы. Но для многих задач рекурсивное решение достаточно быстрое и простое в написании и поддержке.