Хвостовая рекурсия

Рекурсивные операции с пересборкой дерева

При рекурсивной пересборке дерева мы не нуждаемся в указателе на родителя. Родитель «при нас», это текущий элемент, так что мы можем контролировать дельнейшие действия.

Определение узла и функции, которая возвращает новый узел.

typedef int T;

#define CMP_EQ(a, b) ((a) == (b))
#define CMP_LT(a, b) ((a) < (b))
#define CMP_GT(a, b) ((a) > (b))

typedef struct Node {
	T data;
	struct Node *left;
	struct Node *right;
} Node;

Node *getNode(T value) {
	Node* tmp = (Node*) malloc(sizeof(Node));
	tmp->left = tmp->right = NULL;
	tmp->data = value;
	return tmp;
}

Функция вставки нового элемента возвращает новое дерево. Это дерево построено из старого, в которое добавлен новый узел. Причём процесс пересборки в тоже время производит поиск места, в которое нужно произвести вставку.

Если функция получает NULL в качестве аргумента, то она возвращает новый узел. Если узел больше значения, которое мы хотим вставить, то левой ветви присваиваем значение, которое возвращает наша же функция insert, то есть она «дособирает» левую ветвь. Аналогично, если значение узла меньше, то мы «дособираем» правую ветвь и возвращаем узел.

Node* insert(Node* root, T value) {
	if (root == NULL) {
		return getNode(value);
	}
	if (CMP_GT(root->data, value)) {
		root->left = insert(root->left, value);
		return root;
	} else if (CMP_LT(root->data, value)) {
		root->right = insert(root->right, value);
		return root;
	} else {
		exit(3);
	}
}

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

Когда мы доходим до конца дерева, то логично закончить работу и вернуть NULL.

if (root == NULL) {
	return NULL;
}

Теперь проверяем, если текущий узел не равен удаляемому значению, то продолжаем сборку левой и правой ветвей.

if (CMP_GT(root->data, value)) {
		root->left = deleteNode(root->left, value);
		return root;
	} else if (CMP_LT(root->data, value)) {
		root->right = deleteNode(root->right, value);
		return root;
	} else {
		//Магия здесь
	}
}

Если же мы наткнулись на узел, который хотим удалить, то есть несколько ситуаций.

if (root->left && root->right) {
	//Заменить значение текущего узла на максимум левой подветви
	//Удалить максимум левой подветви
	//Вернуть собранное значение
} else if (root->left) {
	//Удалить узел и вернуть его левую подветвь
} else if (root->right) {
	//Удалить узел и вернуть его правую подветвь		
} else {
	//Удалить узел и вернуть NULL		
}

Полный код

Node* deleteNode(Node* root, T value) {
	if (root == NULL) {
		return NULL;
	}
	if (CMP_GT(root->data, value)) {
		root->left = deleteNode(root->left, value);
		return root;
	} else if (CMP_LT(root->data, value)) {
		root->right = deleteNode(root->right, value);
		return root;
	} else {
		if (root->left && root->right) {
			Node* locMax = findMaxNode(root->left);
			root->data = locMax->data;
			root->left = deleteNode(root->left, locMax->data);	
			return root;
		} else if (root->left) {
			Node *tmp = root->left;
			free(root);
			return tmp;
		} else if (root->right) {
			Node *tmp = root->right;
			free(root);
			return tmp;
		} else {
			free(root);
			return NULL;
		}
		
	}
}

Функции нахождения узла, максимум и минимума не изменятся.

Q&A

Всё ещё не понятно? – пиши вопросы на ящик

По языку [ править ]

• Haskell — Да
• Эрланг — Да
• Common Lisp — некоторые реализации выполняют оптимизацию хвостового вызова во время компиляции, если оптимизируются для скорости
• JavaScript — движки, совместимые с ECMAScript 6.0, должны иметь хвостовые вызовы , которые теперь реализованы в Safari / WebKit , но отклонены V8 и SpiderMonkey.
• Lua — рекурсия хвоста требуется по определению языка
• OCaml — Да
• Python — стандартные реализации Python не выполняют оптимизацию хвостового вызова, хотя для этого доступен сторонний модуль. Изобретатель языка Гвидо ван Россум утверждает, что трассировки стека изменяются путем исключения хвостового вызова, что усложняет отладку, и предпочитает, чтобы программисты использовали вместо этого явную итерацию
• Rust — оптимизация хвостового вызова может выполняться в ограниченных случаях, но не гарантируется
• Схема — Требуется определением языка
• Ракетка — Да
• Tcl — Начиная с Tcl 8.6, в Tcl есть команда хвостового вызова
• Kotlin — имеет модификатор tailrec для функций
• Эликсир — Эликсир реализует оптимизацию хвостового вызова . Как и все языки, в настоящее время нацеленные на виртуальную машину BEAM.
• Perl — явный вариант с вариантом оператора goto, который принимает имя функции:
• Scala — рекурсивные функции хвоста автоматически оптимизируются компилятором. Такие функции также могут быть помечены аннотацией, что делает ошибку компиляции, если функция не является хвостовой рекурсивной
• Objective-C — компилятор оптимизирует хвостовые вызовы, когда указана опция -O1 (или выше), но это легко нарушается вызовами, добавленными с помощью автоматического подсчета ссылок (ARC).
• F # — F # реализует TCO по умолчанию, где это возможно
• Clojure — Clojure имеет повторяющуюся специальную форму.
• Вперед — нет

Ссылки [ править ]

1. ^ Стивен Мучник; Muchnick and Associates (15 августа 1997 г.). Продвинутая реализация проекта компилятора . Морган Кауфманн. ISBN 978-1-55860-320-2.
2. ^ a b c Стил, Гай Льюис (1977). «Развенчание мифа о« дорогом вызове процедуры »или о реализациях вызова процедур, которые считаются вредными, или LAMBDA: The Ultimate GOTO». Материалы ежегодной конференции 1977 г. — ACM ’77 . С. 153–162. DOI10.1145 / 800179.810196 . ЛВП1721,1 / 5753 . ISBN 978-1-4503-2308-6.
3. ^ «LLVM Target-Independent Code Generator — документация LLVM 7» . llvm.org .
4. ^ «Рекурсия — Использование памяти стека для хвостовых вызовов — Теоретическая информатика» . Cstheory.stackexchange.com. 2011-07-29 . Проверено 21 марта 2013 .
5. ^ a b «Пересмотренный отчет ^ 6 по алгоритмической языковой схеме» . R6rs.org . Проверено 21 марта 2013 .
6. ^ «Пересмотренный отчет ^ 6 по алгоритмической языковой схеме — обоснование» . R6rs.org . Проверено 21 марта 2013 .
7. ^ «Пересмотренный отчет ^ 6 по алгоритмической языковой схеме» . R6rs.org . Проверено 21 марта 2013 .
8. ^ а б Сассман, ГДж; Абельсон, Хэл (1984). Структура и интерпретация компьютерных программ . Кембридж, Массачусетс: MIT Press. ISBN 0-262-01077-1.
9. ^ DHD Уоррен, DAI Research Report 141 , Эдинбургский университет, 1980.
10. ^ Дэниел П. Фридман и Дэвид С. Уайз, Технический отчет TR19: Разворачивание структурированных рекурсий в итерациях , Университет Индианы, декабрь 1974 г.
11. ^ R5RS Разд. 3,5, Ричард Келси; Уильям Клингер; Джонатан Рис; и другие. (Август 1998 г.). «Пересмотренный отчет 5 по алгоритмической языковой схеме» . Вычисление высшего порядка и символическое вычисление . 11 (1): 7–105. DOI10,1023 / A: 1010051815785 .
12. ^ Контактные данные. «перейти» . perldoc.perl.org . Проверено 21 марта 2013 .
13. ^ «В чем разница между хвостовыми вызовами и хвостовой рекурсией? », Stack Overflow
14. ^ » Какие ограничения JVM налагает на оптимизацию хвостового вызова «, Programmers Stack Exchange
15. ^ Латтнер, Крис. «Справочное руководство по языку LLVM, раздел: Независимый от цели генератор кода LLVM, подраздел: Оптимизация хвостового вызова» . Инфраструктура компилятора LLVM . Проект LLVM . Проверено 24 июня 2018 .
16. ^ «Использование коллекции компиляторов GNU (GCC): параметры оптимизации» . gcc.gnu.org .
17. ^ «foptimize-sibling-calls» . software.intel.com .
18. ^ «Решение хвостовых вызовов C ++» .
19. ↑ Пробст, Марк (20 июля 2000). «правильная хвостовая рекурсия для gcc» . Проект GCC . Проверено 10 марта 2015 года .
20. ^ Сэмюэл Джек, подпрыгивая на хвосте . Функциональное развлечение . 9 апреля 2008 г.
21. ^ a b Генри Бейкер, «Минусы не должны ПРОТИВ его аргументов, Часть II: Чейни на MTA»
22. ^ «Хвостовая рекурсия — HaskellWiki» . wiki.haskell.org . Проверено 8 июня 2019 .
23. ^ Береш-Деак, Адам. «Стоит посмотреть: Дуглас Крокфорд говорит о новых хороших частях JavaScript в 2014 году» . bdadam.com .
24. ^ «ECMAScript 6 в WebKit» . 13 октября 2015 г.
25. ^ «Справочное руководство по Lua 5.3» . www.lua.org .
26. ^ «baruchel / tco» . GitHub .
27. ↑ Россум, Гвидо Ван (22 апреля 2009 г.). «Неопифоник: устранение рекурсии хвоста» .
28. ^ «Часто задаваемые вопросы о ржавчине» . prev.rust-lang.org .
29. ^ «Пересмотренный отчет ^ 5 по алгоритмической языковой схеме» . www.schemers.org .
30. ^ «Пересмотренный отчет ^ 6 по алгоритмической языковой схеме» . www.r6rs.org .
31. ^ «Ракетка Ссылка» . docs.racket-lang.org .
32. ^ «Страница руководства по вызову — встроенные команды Tcl» . www.tcl.tk .
33. ^ «Функции: infix, vararg, tailrec — язык программирования Kotlin» . Котлин .
34. ^ «Рекурсия» . elixir-lang.github.com .
35. ^ «goto — perldoc.perl.org» . perldoc.perl.org .
36. ^ «Стандартная библиотека Scala 2.13.0 — scala.annotation.tailrec» . www.scala-lang.org . Проверено 20 июня 2019 .
37. ^ «Хвостовые вызовы в F #» . msdn . Microsoft.
38. ^ «(повторное выражение *)» . clojure.org .
39. ^ «предложение: Перейти 2: добавить оператор стал для поддержки хвостовых вызовов» . github.com .

Эта статья основана на материалах, взятых из Free On-line Dictionary of Computing до 1 ноября 2008 г. и включенных в соответствии с условиями «перелицензирования» GFDL версии 1.3 или новее.

Хвостовая рекурсия — концепция

Если все рекурсивные вызовы функции происходят в конце функции, мы вызываем рекурсивную функцию tail-recursive. Когда рекурсивный вызов является последним оператором, выполняемым во всем теле функции, и его возвращаемое значение не является частью выражения, рекурсивный вызов является хвостовым рекурсивным. Особенность хвостовой рекурсивной функции заключается в том, что ей не нужно выполнять никаких операций во время процесса регрессии.Эта функция важна, поскольку большинство современных компиляторов используют эту функцию для автоматической генерации оптимизированного кода.

примеров

Чтобы понять, как работает хвостовая рекурсия, давайте снова вычислим факториал в рекурсивной форме. Во-первых, легко понять, почему ранее определенная рекурсия не является хвостовой рекурсией. Вспомните предыдущее определение вычисления n!: Рассчитайте n раз (n-1)! В каждом активном периоде пусть n = n-1 и продолжайте этот процесс, пока n = 1. Это определение не является хвостово-рекурсивным, поскольку возвращаемое значение каждого активного периода зависит от умножения возвращаемого значения следующего активного периода на n, поэтому кадр стека, сгенерированный каждым вызовом, должен быть сохранен в стеке до следующего под-вызова Возвращаемое значение ОК. Теперь рассмотрим определение процесса вычисления n! В виде хвостовой рекурсии. Это определение также должно принимать второй параметр a, но нет большой разницы. a (инициализированный в 1) поддерживает глубину уровня рекурсии. Это избавляет нас от необходимости каждый раз умножать возвращаемое значение на n. Однако в каждом рекурсивном вызове пусть a = na и n = n-1. Продолжайте рекурсивный вызов до n = 1, что удовлетворяет условию завершения, а затем просто возвращайте напрямую. В примере кода 3-2 показан факт-код функции C, который принимает целое число n и вычисляет факториал n в хвостовой рекурсивной форме. Эта функция также принимает параметр a, начальное значение a равно 1. Facttail использует a для поддержания глубины уровня рекурсии, за исключением того, что он похож на факт. Читатель может заметить сходство между конкретной реализацией функции и определением хвостовой рекурсии. Пример 3-2: реализация функции для вычисления факториалов в хвостовой рекурсии

Функция в примере 3-2 является хвостовой рекурсивной, потому что единственный рекурсивный вызов facttail является последним оператором, выполненным перед возвращением функции. Бывает, что последнее утверждение в фактическом хвосте также является призывом к фактическому хвосту, но это не обязательно. Другими словами, могут быть другие операторы, выполняемые после рекурсивного вызова, но они могут выполняться только тогда, когда рекурсивный вызов не выполняется. Хвостовая рекурсия чрезвычайно важна. Без хвостовой рекурсии потребление стека функции неисчислимо, и необходимо сохранить стек многих промежуточных функций. Например, f (n, sum) = f (n-1) + value (n) + sum, сохранит n стеков вызовов функций и будет использовать хвостовую рекурсию f (n, sum) = f (n-1, sum + value (n)); Таким образом, можно сохранить только последний стек функций, а предыдущую оптимизацию можно удалить. В языке C может быть много особых случаев, но языком программирования является не только C. В функциональном языке Erlang (также в языке стека), если вы хотите поддерживать высокий параллелизм языка , Вы должны заменить традиционную рекурсию хвостовой рекурсией. Сравнение хвостовой рекурсии и традиционной рекурсии Ниже приведены конкретные примеры: Линейная рекурсия:

Хвостовая рекурсия:

Когда n = 5 Для традиционной линейной рекурсии его рекурсивный процесс выглядит следующим образом:

Для рекурсии хвоста его процесс рекурсии выглядит следующим образом:

Описание:Эффект хвостовой рекурсии заключается в устранении недостатка, заключающегося в том, чтобы снова возвращать результаты нижнего уровня на верхний уровень. Верхнему уровню необходимо продолжить вычисления, чтобы получить результаты. Если вы внимательно посмотрите на пример, вы увидите, что на самом деле каждый рекурсивный результат сохраняется во втором параметре a. Средний, когда выполняется последний расчет, будет возвращено только значение a, но, поскольку это рекурсивный принцип, хотя его все равно нужно возвращать на верхний уровень, результаты передаются на верхний уровень один за другим, но вычислять больше нет необходимости. Преимущество состоит в том, что память, выделяемая каждый раз, не расширяется из-за рекурсии.

С точки зрения эффективности, эти два действительно похожи.

Хвостовая рекурсия и цикл

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

После вызова управление передается другой функции. Для передачи управления достаточно изменить значение регистра программного счетчика, в котором процессор хранит номер текущей выполняемой команды — аналогичным образом передается управление ветвям алгоритма, например, при использовании условного оператора. Однако, вызов — это не только передача управления, ведь после того, как вызванная функция завершит вычисления, она должна вернуть управление в точку, и которой осуществлялся вызов, а также восстановить значения локальных переменных, которые существовали там до вызова.

Для реализации такого поведения используется стек (стек вызовов, call stack) — в него помещаются номер команды для возврата и информация о локальных переменных. Стек не является бесконечным, поэтому рекурсивные алгоритмы могут приводить к его переполнению, в любом случае на работу с ним может уходить значительная часть времени.

В ряде случаев рекурсивную функцию достаточно легко заменить циклом, например, рассмотренные выше алгоритмы поиска и бинарного поиска . В некоторых случаях требуется более творческий подход, но чаще всего такая замена оказывается возможной. Кроме того, существует особый вид рекурсии, когда рекурсивный вызов является последней операцией, выполняемой функцией. Очевидно, что в таком случае вызывающая функция не будет каким-либо образом изменять результат, а значит ей нет смысла возвращать управление. Такая рекурсия называется хвостовой — компиляторы автоматически заменяют ее циклом.

Зачастую сделать рекурсию хвостовой помогает метод накапливающего параметра , который заключается в добавлении функции дополнительного аргумента-аккумулятора, в котором накапливается результат. Функция выполняет вычисления с аккумулятором до рекурсивного вызова. Хорошим примером использования такой техники служит функция вычисления факториала: \(fact_n = n \cdot fact(n-1) \\ fact_3 = 3 \cdot fact_2 = 3 \cdot (2 \cdot fact_1) = 3\cdot (2 \cdot (1 \cdot fact_0)) = 6 \\ fact_n = factTail_{n, 1} \\ \\ factTail_{n, accumulator} = factTail(n-1, accumulator \cdot n)\\ factTail_{3, 1} = factTail_{2, 3} = factTail_{1, 6} = factTail_{0, 6} = 6 \)

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

начало; fibonacci(number)
вернуть fibonacci(number, 1, 1, 0)
конец

начало; fibonacci(number, iterator, fib1, fib2)
  если iterator == number вернуть fib1
  вернуть fibonacci(number, iterator + 1, fib1 + fib2, fib1)
конец

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

Рекурсивные алгоритмы

Рекурсивные функции обычно решают задачу, сначала находя решение подмножества задачи (рекурсивно), а затем, изменяя это подрешение, чтобы перейти к решению. В приведенном выше алгоритме сначала решает , а затем добавляет значение переменной , чтобы найти решение для .

Во многих рекурсивных алгоритмах некоторые входные данные дают тривиальные результаты. Например, имеет тривиальный результат 1 (вы можете вычислить это в уме), и нет выигрыша от дальнейшей рекурсии. Входные данные, для которых алгоритм создает выходные данные тривиально, называются базовым случаем. Базовые случаи действуют как условия завершения работы алгоритма. Базовые случаи часто можно определить, рассматривая выходные данные для входных значений 0, 1, «», » или .

Плюсы:

Под этим подразумевается, что рекурсии, в сравнении с циклами, тратят меньше времени до завершения функции. Чем меньше строк кода у нас будет, тем быстрее функция будет обрабатывать вызовы внутри себя. Особенно хорошо это проявляется при буферизации данных, что позволяет оптимизировать и ускорить код.

В программировании мемоизация — это метод сохранения результатов выполнения функций для предотвращения повторных вычислений. Это один из способов оптимизации, применяемый для увеличения скорости выполнения программ. — Википедия

И всё же стоит отметить, что рекурсия не всегда выигрывает по скорости по сравнению с циклами.

Рекурсию легче отлаживать.

Многие согласятся, что эта причина очень важна. Рекурсия проста в отладке из-за того, что она не содержит сложных и длинных конструкций.

Примеры рекурсивных алгоритмов

Рекурсивный алгоритм всегда разбивает задачу на части, которые по своей структуре являются такими же как исходная задача, но более простыми. Для решения подзадач функция вызывается рекурсивно, а их результаты каким-либо образом объединяются. Разделение задачи происходит лишь тогда, когда ее не удается решить сразу (она является слишком сложной).

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

Поиск элемента массива

начало; search(array, begin, end, element)
      ; выполняет поиск элемента со значением element в массиве array между индексами begin и end
если begin > end
  результат := false; элемент не найден
иначе если array = element
  результат := true; элемент найден
иначе
  результат := search(array, begin+1, end, element)
конец; вернуть результат

Алгоритм делит исходный массив на две части — первый элемент и массив из остальных элементов. Выделяется два простых случая, когда разделение не требуется — обработаны все элементы или первый элемент является искомым.

В алгоритме поиска разделять массив можно было бы и иначе (например пополам), но это не сказалось бы на эффективности. Если массив отсортирован — то его деление пополам целесообразно, т.к. на каждом шаге количество обрабатываемых данных можно сократить на половину.

Двоичный поиск в массиве

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

начало; binary_search(array, begin, end, element)
      ; выполняет поиск элемента со значением element
      ; в массиве упорядоченном по возрастанию массиве array
      ; между индексами begin и end
если begin > end
  конец; вернуть false - элемент не найден
mid := (end + begin) div 2; вычисление индекса элемента посередине рассматриваемой части массива
если array = element
  конец; вернуть true (элемент найден)
если array < element
  результат := binary_search(array, mid+1, end, element)
иначе
  результат := binary_search(array, begin, mid, element)
конец; вернуть результат

Вычисление чисел Фибоначчи

Числа Фибоначчи определяются рекуррентным выражением, т.е. таким, что вычисление элемента которого выражается из предыдущих элементов: \(F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}, n > 2\).

начало; fibonacci(number)
если number = 0
  конец; вернуть 0
если number = 1
  конец; вернуть 1
fib_1 := fibonacci(number-1)
fib_2 := fibonacci(number-2)
результат := fib_1 + fib_2
конец; вернуть результат

Быстрая сортировка (quick sort)

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

Блок-схема алгоритма быстрой сортировки

Сортировка слиянием (merge sort)

В основе алгоритма сортировки слиянием лежит возможность быстрого объединения упорядоченных массивов (или списков) так, чтобы результат оказался упорядоченным. Алгоритм разделяет исходный массив на две части произвольным образом (обычно пополам), рекурсивно сортирует их и объединяет результат. Разделение происходит до тех пор, пока размер массива больше единицы, т.к. пустой массив и массив из одного элемента всегда отсортированы.

Блок схема сортировки слиянием

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

начало; merge(Array1, Size1, Array2, Size2)
     ; исходные массивы упорядочены
     ; в результат формируется упорядоченный массив длины Size1+Size2
i := 0, j := 0
вечный_цикл
  если i >= Size1
    дописать элементы от j до Size2 массива Array2 в конец результата
    выход из цикла
  если j >= Size2
    дописать элементы от i до Size1 массива Array1 в конец результата
    выход из цикла
  если Array1 < Array2
    результат := Array1
    i := i + 1
  иначе (если Array1 >= Array2)
    результат := Array2
    j := j + 1
конец; вернуть результат

Проблемы, вызванные рекурсией

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

Мы знаем, что при вызове функции в памяти формируется «запись вызова», также известная как «кадр вызова», в которой сохраняется такая информация, как местоположение вызова и внутренние переменные. Последовательность вызовов вложенных функций, вызванная рекурсией, создаст серию кадров вызовов, и все кадры вызовов образуют «стек вызовов». Кадр вызова хранится в памяти. Когда кадров вызова достаточно, возникает ошибка переполнения стека.

Во-первых, давайте посмотрим на рекурсивную функцию факториала:

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

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

Таким образом, рекурсия может вызвать две основные проблемы:Проблемы с производительностью и ошибки переполнения стека。

Хвостовая рекурсия — как не надо делать

Хвостовая рекурсия — частный случай рекурсии, при котором любой рекурсивный вызов является последней операцией перед возвратом из функции.

Вот пример обратного отсчета, написанного с использованием хвостовой рекурсии:

Любое вычисление, которое может быть выполнено с использованием итерации, также может быть выполнено с использованием рекурсии. Вот версия find_max, написанная с использованием хвостовой рекурсии:

Хвостовую рекурсию лучше не использовать, поскольку компилятор Python не обрабатывает оптимизацию для хвостовых рекурсивных вызовов. В таких случаях рекурсивное решение использует больше системных ресурсов, чем итеративное.

Минусы:

Рекурсивные функции занимают значительный объём памяти во время своего выполнения. Это означает, что при каждом вызове функции в стек будет добавляться новый элемент, который будет занимать место до тех пор, пока функция не завершит работу, найдя ответ, либо пока не дойдёт до выполнения базового условия функции.

Рекурсивные функции замедляют программу.

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

Что такое «стек»?

Стек — это такая структура данных, которая работает по принципу «Last In, First Out» (последним пришёл — первым ушёл). Таким образом, элемент «проталкивается» в стек и добавляется в его конец, а затем «выталкивается» из стека при удалении.

Стеки замечательны тем, что они очень быстрые. Большое «О» этого алгоритма равно O(1). Такая результативность объясняется тем, что при рекурсиях не используются циклы, вместо них используются функции , и .

Визуализация стека

Стоит ли использовать рекурсии вместо обычных циклов?

Оба этих метода одинаково эффективны для решения задач, однако выбор одного из них зависит от типа проблемы, поставленной перед вами.

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

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

• Как освоить алгоритмы?
• Алгоритмы машинного обучения простым языком. Часть 1
• 4 принципа успешной поисковой системы и не только

Читайте нас в Telegram, VK и

Рекурсия

Рекурсивная функция (или просто «рекурсия») в языке C++ — это функция, которая вызывает сама себя. Например:

#include <iostream>

void countOut(int count)
{
std::cout << «push » << count << ‘\n’;
countOut(count-1); // функция countOut() вызывает рекурсивно сама себя
}

int main()
{
countOut(4);

return 0;
}

1 2 3 4 5 6 7 8 9 10 11 12 13 14

#include <iostream> voidcountOut(intcount) { std::cout<<«push «<<count<<‘\n’; countOut(count-1);// функция countOut() вызывает рекурсивно сама себя } intmain() { countOut(4); return; }

При вызове функции countOut(4) на экран выведется , а затем вызывается countOut(3). countOut(3) выведет и вызывает countOut(2). Последовательность вызова countOut(n) других функций countOut(n-1) повторяется бесконечное количество раз (аналог бесконечного цикла). Попробуйте запустить у себя.

На уроке о стеке и куче в С++ мы узнали, что при каждом вызове функции, определенные данные помещаются в стек вызовов. Поскольку функция countOut() никогда ничего не возвращает (она просто снова вызывает countOut()), то данные этой функции никогда не вытягиваются из стека! Следовательно, в какой-то момент, память стека закончится и произойдет .

Случай с рекурсией

Тогда как в случае рекурсии рекурсивная функция снова вызывается с другими конкретными значениями. Это руководство будет включать в себя примеры, поясняющие работу функции рекурсии. Инструмент SPYDER используется для выполнения программ.

Пример 1

В этом примере рассматривается вычисление чисел таким образом, чтобы они отображались в обратном порядке. Функция принимает в качестве аргумента число при вызове функции. Это число затем передается через операторы if-else.

Это базовый вариант. Если число равно 0, это означает, что значение будет возвращено само без каких-либо операций, и функция будет завершена.

В то время как функция обратного отсчета является рекурсивной частью, в другой части тела if.

Вызов функции обеспечивается числом 4. Значит, это не ноль. Часть ’if’ будет игнорироваться, а часть else будет отсчитывать числа от 4 до нуля. И результаты будут отображены. Выполните код; мы получим результат.

Пример 2

Чтобы вычислить в качестве входных данных сумму последовательности от 1 до заданного числа, выбирается цикл for с функцией range ().

Результат возвращается; это простая функция без каких-либо условий непосредственного завершения. Ответ отображается в консоли вывода. Это сумма суммы от единицы до данного числа.

К этой простой функции мы теперь применяем процедуру рекурсии.

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

Ответ для обоих подходов одинаков. Разница только в случае использования функции рекурсии вместо цикла FOR.

Пример 3

Мы хотим вычислить ряд Фибоначчи с точностью до указанных чисел. Эти серии выглядят как 0,1,1,2,3,5,8 и так далее. Эти серии формируются путем добавления предыдущего числа к текущему значению. Мы используем рекурсивную функцию и оператор if-else для создания этой серии.

Внутри рекурсивной функции часть else будет иметь рекурсивный вызов. Вызов выполняется дважды, имея дело с оператором вычитания. Предоставленный здесь предел равен 9. Снова оператор if-else используется для обеспечения доступности положительного числа, потому что, если пользователь вводит отрицательное значение, отображается сообщение об ошибке. Причина в том, что ряд Фибоначчи применяется к положительным числам. В то время как для положительного значения функция продолжается. Для процесса печати здесь используется цикл for.

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

Пример 4

С помощью рекурсивной функции довольно легко вычислить факториал любого числа. Факториал — это число, кратное всем числам в последовательности, пока число не будет использовано в качестве входных данных в коде.

Оператор if-else будет работать вместе для завершения рекурсивной функции.

Допустимость ввода требуется, так как число, введенное для ввода, должно быть положительным, потому что факториал всегда является положительным числом, а не отрицательным. Результатом является целое число, поэтому мы не будем использовать цикл for для печати.

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