предисловие
Перед проектом системы управления компанией необходимо сотрудничать с интерфейсомVUEДля реализации динамической маршрутизации возвращаемая структура данных представляет собой древовидную структуру, но параллельные элементы данных хранятся в базе данных. В это время вам нужно собрать структуру данных в коде. Я давно не думал об этих проблемах, и потребовалось много времени, чтобы их решить. Это включает в себя реализацию рекурсивного алгоритма.Я взял выходные, чтобы глубоко подумать о дизайне рекурсивного алгоритма, и записал немного своего скромного мнения, чтобы сделать заметку.
Что такое рекурсия?
за递归На самом деле, мы не незнакомы. Помнишь, когда я использовал его в старшей школе?数学归纳法? ,递归Эта концепция не является уникальной для информатики. Фактически数学归纳法Это теоретическая основа рекурсии.
Начнем с простого каштана: найдите n Здесь мы используем рекурсию для решения.
int foo(int n) {
if(n != 1) {
return n*foo(n-1);
}
return 1;
}
Смысл приведенного выше кода: когдаnне равно1когда. Продолжай звонитьfoo（n-1）и с входящимnУмножить. Объясните здесь принцип реализации рекурсивного вызова: мы знаем, что вызов функции в компьютере реализуется с использованием стековой структуры данных, такой как входящиеnза5, первое исполнениеfooметод, при выполнении которогоfoo(n-1),методfooбудет помещен в стек. Фактически рекурсивный метод ничем не отличается от обычного метода. Единственное отличие состоит в том, что рекурсивный вызов представляет собой собственный код. Здесь также можетfooКаждый вызов вызываетсяfoo1,foo2и Т. Д. Тогда легко понять, когдаfooметод выполняется дляn==1При , стек хранится по очередиfoo1,foo2,foo3,foo4,foo5。В настоящее времяfoo5В верхней части стека извлеките стек.foo5при исполненииn==1, как видно из кода,n==1, метод возвращает напрямую1. тогдаfoo4выскочил, входящийnза2, операция2*1,Потомfoo3,foo2,foo1Извлекайте стек по очереди, и операции следующие:3*2,4*6когда последний методfoo1 returnрасчет времени,5*24, операция заканчивается.
Из этого процесса нетрудно увидеть, что рекурсия является непрерывным нисходящим процессом. Слои вызывают сами себя, а затем оценка является восходящим процессом. Начиная с возвращаемого значения выхода в конце рекурсии, оно оценивается слой за слоем.
Из этого примера также можно увидеть две важные особенности рекурсивных алгоритмов, например:
- продолжайте называть себя
- Есть условие завершения, иначе получится бесконечный цикл
Вопрос, над которым следует подумать, заключается в том, как определяется условие завершения и как оно изменяется. В приведенной выше программе нужно сделать-1работать.
Когда следует рассмотреть возможность использования рекурсии?
когда определение рекурсивно
Это тот же тип, что и в приведенном выше примере для нахождения факториала.斐波那契数列Определение является рекурсивным. Посмотрите прямо на код:
int Fib(int n) {
if(n==1 || n==2) {
return 1;
}else {
Fib(n-1)+Fib(n-2)
}
}
斐波那契数列:1,1,2,3,5 ...
Когда сама структура данных рекурсивна
Самый распространенный пример — определение связанного списка (здесь речь идет о связанном списке без головного узла):
class Node {
private String data; //节点数据域
private Node next; //指向下一个节点
}
Когда вам нужно суммировать поля данных связанного списка, вы можете использовать рекурсивную реализацию:
int SUM(Node node){
if(node == null) {
return 0;
}else {
return node.getData()+SUM(node.getNext());
}
}
Когда проблему нужно решать рекурсивно
Реализация алгоритма Ханойской башни подробно обсуждается здесь.
Описание задачи о ханойской башне: есть три башни с именами X, Y и Z. На основании башни X расположены диски разного диаметра, которые пронумерованы от меньшего к большему: 1, 2, 3...n.Теперь требуется переместить диски на основании башни X на основание башни Z, в один и тот же порядок сложен. При перемещении необходимо соблюдать правила: 1. За один раз можно перемещать только одну тарелку. 2. Тарелку можно поставить на любую башню. 3. Большую тарелку нельзя ставить поверх меньшей.
Ханойские башни — типичная задача рекурсивного решения. Анализировать декомпозицию задачи по описанию непросто, лучше попытаться проанализировать решение, когда масштаб проблемы невелик.
Когда на башне X только одна тарелка:
X==>Z
Когда на башне X две тарелки:
X1==>Y,X2==>Z
Y1==>Z
Когда на башне X три тарелки:
X1==>Z,X2==>Y
Z==>Y,X==>Z
Y1==>X,Y2==>Z
X==>Z
Рекурсивный алгоритм дан первым, этот алгоритм распечатает шаги перемещения.
void Hanoi(int n,String X,String Y,String Z) {
if(n == 1) {
System.out.println("将第"+n+"个盘片从"+X+"移到"+Z); //X==>Z
}else {
Hanoi(n-1,X,Z,Y);
System.out.println("将第"+n+"个盘片从"+X+"移到"+Z); //X==>Z
Hanoi(n-1,Y,X,Z);
}
}
Основное требование к Ханойской башне — поместить самый большой внизу, поэтому, когдаXКогда количество тарелок на башне больше 1, мы сначала ставимXна башне,1至n-1блюдо наY, поэтому мы можем игнорироватьXнижняя тарелка, положитьYв видеZ,Zв видеY, поэтому проблема возвращается, когдаXимеютn-1тарелки, как перейти кZситуация. запомни это времяZдаY. Теперь мы сделалиXначальство1至n-1диск помещаетсяYначальство. не забудьтеXЕсть также одна из самых больших тарелок, которые мы упустили из виду.
Хорошо, теперь поставьXПоставьте самую большую тарелкуZ,В настоящее времяXбез тарелок,Yимеют1至n-1тарелки, пока игнорируемZсамая большая тарелка на . будетYв видеX,Xв видеY. Проблема вернуласьXТамn-1Как блюдо перемещается наZситуация.
Посмотрите еще раз на приведенный выше код. когда
n==1, напрямуюXперейти кZ, в противном случаеYв видеZ,Zв видеY,будет1至n-1блюдо перемещается вYначальство. Выньте это в это времяXПоставьте самую большую тарелкуZ. поставь это сноваXкогдаY,Yв видеX, продолжайте рекурсивно. до того какn==1, ход удался! В самом деле, нетрудно обнаружить, что при исполнении до второгоSystem.out.println("将第"+n+"个盘片从"+X+"移到"+Z);Время. завершилXСамая большая тарелка переехала вZЦель. Количество этажей в Ханойской башне уменьшено на один. Проблема возвращается к исходной ситуации, за исключением того, что тарелка находится вYна, неXначальство. Но это не мешает звонитьHanoiметод. На самом деле суть проблемы в том, чтоX，Y，ZТри башни одинаковы без каких-либо различий. После еще одного цикла операции просто установите нижний диск.Z, на этот раз масштаб проблемы уменьшен на единицу.
Как разработать рекурсивный алгоритм?
найти условие окончания рекурсии
Одна из рекурсивных функций, описанных выше, гласит, что рекурсия должна иметь условие завершения. Например, факториал, последовательность Фибоначчи и задача о Ханойской башне, которые представляют масштаб проблемы при рекурсивном вызове.nпродолжайте уменьшаться до тех пор, пока не будет достигнуто условие окончания рекурсииn==1. На самом деле рекурсивное условие не обязательно таково, что оценочное значение конечного условия достигается за счет уменьшения.Например, при построении древовидной структуры вы можете судить о значении элемента данных, оцениваяisLeafПолеtrueчтобы решить, выходить ли из рекурсии. Одно можно сказать наверняка: условие рекурсивного выхода должно быть скрыто в параметрах, передаваемых методу при первом вызове, и в любом состоянии, к которому можно получить доступ во время выполнения метода.
найти тело цикла
Это относительно сложная проблема.Для подобных задач с математическим определением телом цикла часто являются слова, которые определяют проблему, например, определение последовательности Фибоначчи:当0<n<3时，Fib=1，当n>2时，Fib(n)=Fib(n-1)+Fib(n-2). При разработке алгоритма для рекурсивной структуры данных тело цикла представляет собой инструкцию, которая обращается к рекурсивной структуре. Например, при обходе связанного списка:
void foo(node) {
if(node != null) {
foo(node.getNext());
}else {
return;
}
}
Однако для таких задач, как Ханойская башня, нет интуитивного способа непосредственно увидеть характеристики рекурсии. Личный опыт заключается в выполнении расчетов на меньших масштабах задачи. Откройте для себя рекурсивные функции.
резюме
Рекурсивное программирование само по себе относительно сложно понять и освоить. Его нельзя использовать умело с помощью простого теоретического обучения. Только постоянное решение проблем может привести к совершенству.