разбитые мысли

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

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

Почему это самый простой? Мы знаем, что инфикс выражения дружелюбны к людям, и их можно оценить после изучения четырех арифметических операций. Однако для компьютеров, хотя они также могут найти способы рассчитать, они не дружелюбны; наоборот, постфиксные выражения, в то время как недружественный Люди, понравились компьютерами.

(Другими словами, важность постфиксных выражений в принципе компиляции также может быть на первом плане.)

куча

Приступая к изучению языка C, мы перейдемрекурсияпришел спроситьПоследовательность ФибоначчиОчень простой:

int fibonacci(int n) {
	if (n==0 || n==1) return 1;
	return fibonacci(n-1) + fibonacci(n-2);
}

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

Что такое рекурсия? рекурсияфункция вызывает сама себя.

reverse(know) {	// 1. go on
	if (you know) return you know; // 2. look 4
	else back to see the 1; // 3. go back to 1.
} // 4. you know what is recurision now.

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

Обычно мы выбираем переписать рекурсивную программу в нерекурсивную программу, так называемуюУстранить рекурсию, но когда программа после перезаписи и до перезаписи не будет иметь большого прироста производительности, нам не нужно ее переписывать, например:cout << fibonacci(5);, нужно ли устранять рекурсию для такого вызова?

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

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

оптимизация

Для оптимизации рекурсивных программ мы обычно выбираем стек как вспомогательный, почему? Мы знаем, что в операционной системе есть термин "стек вызовов функций". Общее объяснение таково: когда функция A вызывает другую функцию B, мы сохраняем содержимое A после сохранения, помещаем его в системный стек (вы можно сказать, что это создание точки восстановления, а можно сказать, что это защита на месте, просто радуйтесь.), затем выполните содержимое функции B, когда выполнение функции B закончится, удалите A из системного стека Pop, продолжите выполнение с точки останова и уничтожьте ранее запрошенное пространство стека.

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

Поступковая функция Фибоначчи n = 6 При этом рекурсивное дерево вызовов

При n=3 статус приложения стека
При n=6 статус приложения стека

В java исключение java.lang.StackOverflowError является ошибкой переполнения стека, однако пространство стека виртуальной машины можно увеличить, изменив параметры JVM, такие как -vm args-Xss128k; .

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

int main() {
	int n, i=j=1, tmp=0;
	cin >> n;
	while (n--) {
		tmp = i+j;
		i = j;
		j = tmp;
	}
}

Пока так, а что касается последнего, о нем поговорим позже, ведь это всего лишь (1).