Понимание рекурсии [закрыто]

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

Я пытался разгадать Ханойские башни всю ночь и полностью взорвал мой разум. Мой учебник содержит около 30 страниц рекурсии, поэтому он не слишком полезен. Кто-нибудь знает книги или ресурсы, которые могут помочь прояснить эту тему?

Как вы опорожняете вазу с пятью цветами?

Ответ: если ваза не пуста, вы вынимаете один цветок, а затем вы опорожняете вазу с четырьмя цветами.

Как вы опорожняете вазу с четырьмя цветами?

Ответ: если ваза не пуста, вы вынимаете один цветок, а затем вы опорожняете вазу с тремя цветами.

Как вы опорожняете вазу с тремя цветами?

Ответ: если ваза не пуста, вы вынимаете один цветок, а затем вы опорожняете вазу с двумя цветами.

Как вы опорожняете вазу с двумя цветами?

Ответ: если ваза не пуста, вы вынимаете один цветок, а затем вы опорожняете вазу с одним цветком.

Как вы опорожняете вазу с одним цветком?

Ответ: если ваза не пуста, вы вынимаете один цветок, а затем вы опорожняете вазу без цветов.

Как вы опорожняете вазу без цветов?

Ответ: если ваза не пуста, вы вынимаете один цветок, но ваза пуста, так что все готово.

Это повторяется. Давайте обобщим это:

Как вы опорожняете вазу, содержащую N цветами?

Ответ: если ваза не пуста, вы вынимаете один цветок, а затем вы опорожняете вазу, содержащую N-1 цветами .

Хм, мы можем увидеть это в коде?

void emptyVase( int flowersInVase ) {
  if( flowersInVase > 0 ) {
   // take one flower and
    emptyVase( flowersInVase - 1 ) ;

  } else {
   // the vase is empty, nothing to do
  }
}

Хм, разве мы не могли сделать это в цикле?

Почему, да, рекурсию можно заменить итерацией, но часто рекурсия более элегантна.

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

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

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

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

Таким образом, чтобы суммировать значение левого дочернего элемента левого потомка, мы добавили бы значение самого дочернего узла к значению его левого дочернего элемента, если он есть, и значению его правого дочернего элемента, если он есть.

Возможно, вы предвидели, куда я пойду с этим, и хотели бы увидеть какой-нибудь код? ХОРОШО:

struct node {
  node* left;
  node* right;
  int value;
} ;

int sumNode( node* root ) {
  // if there is no tree, its sum is zero
  if( root == null ) {
    return 0 ;

  } else { // there is a tree
    return root->value + sumNode( root->left ) + sumNode( root->right ) ;
  }
}

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

Допустим, у нас есть дерево, которое выглядит следующим образом (числа являются значениями, косая черта указывает на дочерние элементы, а @ означает, что указатель указывает на ноль):

     5
    / \
   4   3
  /\   /\
 2  1 @  @
/\  /\
@@  @@

Если мы вызовем sumNode для корня (узел со значением 5), мы вернем:

return root->value + sumNode( root->left ) + sumNode( root->right ) ;
return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;

Давайте расширим это на месте. Везде, где мы видим sumNode, мы заменяем его расширением оператора return:

sumNode( node-with-value-5);
return root->value + sumNode( root->left ) + sumNode( root->right ) ;
return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;

return 5 + 4 + sumNode( node-with-value-2 ) + sumNode( node-with-value-1 ) 
 + sumNode( node-with-value-3 ) ;  

return 5 + 4 
 + 2 + sumNode(null ) + sumNode( null )
 + sumNode( node-with-value-1 ) 
 + sumNode( node-with-value-3 ) ;  

return 5 + 4 
 + 2 + 0 + 0
 + sumNode( node-with-value-1 ) 
 + sumNode( node-with-value-3 ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + sumNode(null ) + sumNode( null )
 + sumNode( node-with-value-3 ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + sumNode( node-with-value-3 ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + 3 + sumNode(null ) + sumNode( null ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + 3 + 0 + 0 ;

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + 3 ;

return 5 + 4 
 + 2 + 0 + 0
 + 1 
 + 3  ;

return 5 + 4 
 + 2 
 + 1 
 + 3  ;

return 5 + 4 
 + 3
 + 3  ;

return 5 + 7
 + 3  ;

return 5 + 10 ;

return 15 ;

Теперь посмотрим, как мы покорили структуру произвольной глубины и «ветвистости», рассматривая ее как повторное применение составного шаблона? каждый раз с помощью нашей функции sumNode мы имели дело только с одним узлом, используя одну ветвь if / then и два простых оператора возврата, которые почти писали сами, непосредственно из нашей спецификации?

How to sum a node:
 If a node is null 
   its sum is zero
 otherwise 
   its sum is its value 
   plus the sum of its left child node
   plus the sum of its right child node

Это сила рекурсии.

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

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

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

Теперь давайте посмотрим на операцию, где порядок имеет значение. Мы будем использовать двоичное дерево узлов, но на этот раз значение будет символом, а не числом.

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

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

Мы не просто хотим печатать волей-неволей, поэтому мы передадим нашей функции что-то для печати. Это будет объект с функцией print (char); нам не нужно беспокоиться о том, как это работает, просто когда вызывается print, он что-то печатает где-то.

Давайте посмотрим, что в коде:

struct node {
  node* left;
  node* right;
  char value;
} ;

// don't worry about this code
class Printer {
  private ostream& out;
  Printer( ostream& o ) :out(o) {}
  void print( char c ) { out << c; }
}

// worry about this code
int printNode( node* root, Printer& printer ) {
  // if there is no tree, do nothing
  if( root == null ) {
    return ;

  } else { // there is a tree
    printNode( root->left, printer );
    printer.print( value );
    printNode( root->right, printer );
}

Printer printer( std::cout ) ;
node* root = makeTree() ; // this function returns a tree, somehow
printNode( root, printer );

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

Теперь, если наше дерево выглядит так:

         k
        / \
       h   n
      /\   /\
     a  j @  @
    /\ /\
    @@ i@
       /\
       @@

Что мы будем печатать?

From k, we go left to
  h, where we go left to
    a, where we go left to 
      null, where we do nothing and so
    we return to a, where we print 'a' and then go right to
      null, where we do nothing and so
    we return to a and are done, so
  we return to h, where we print 'h' and then go right to
    j, where we go left to
      i, where we go left to 
        null, where we do nothing and so
      we return to i, where we print 'i' and then go right to
        null, where we do nothing and so
      we return to i and are done, so
    we return to j, where we print 'j' and then go right to
      null, where we do nothing and so
    we return to j and are done, so
  we return to h and are done, so
we return to k, where we print 'k' and then go right to
  n where we go left to 
    null, where we do nothing and so
  we return to n, where we print 'n' and then go right to
    null, where we do nothing and so
  we return to n and are done, so 
we return to k and are done, so we return to the caller

Так что, если мы просто посмотрим на строки, мы напечатали:

    we return to a, where we print 'a' and then go right to
  we return to h, where we print 'h' and then go right to
      we return to i, where we print 'i' and then go right to
    we return to j, where we print 'j' and then go right to
we return to k, where we print 'k' and then go right to
  we return to n, where we print 'n' and then go right to

Мы видим, что мы напечатали «ahijkn», который действительно в алфавитном порядке.

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

И это сила рекурсии: способность делать целые вещи, зная только, как сделать часть целого (и зная, когда прекратить повторение).

Напоминая, что в большинстве языков оператор || ("или") при коротком замыкании, когда его первый операнд равен true, общая рекурсивная функция:

void recurse() { doWeStop() || recurse(); } 

Люк М комментирует:

ТАК следует создать значок для такого рода ответа. Поздравляем!

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

Смотрите мой комментарий здесь: /programming/128434/what-are-community-wiki-posts-in-stackoverflow/718699#718699

Ваш мозг взорвался, потому что он попал в бесконечную рекурсию. Это распространенная ошибка новичка.

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

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

а) Прочитайте страницу результатов Google для «рекурсии»
б) прочитав его, перейдите по первой ссылке на него и ...
а.1) Прочитайте эту новую страницу о рекурсии 
б.1) После прочтения перейдите по первой ссылке и ...
а.2) Прочитайте эту новую страницу о рекурсии 
б.2) После прочтения перейдите по первой ссылке на него и ...

Как вы можете видеть, вы долго работали над рекурсивными вещами без проблем.

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

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

Компьютер не может определить домкрат, поэтому вы должны включить явное окончание: «узнайте больше о рекурсии в сети, пока вы ее не поймете или не прочитали максимум 10 страниц ».

Вы также пришли к выводу, что вы должны начать со страницы результатов Google для «рекурсии», и опять же это то, что компьютер не может сделать. Полное описание нашей рекурсивной задачи также должно включать явную отправную точку:

«узнать больше о рекурсии в сети, пока вы не понимаете, или вы должны прочитать максимум 10 страниц и , начиная с www.google.com/search?q=recursion »

Чтобы все это попробовать, я предлагаю вам попробовать любую из этих книг:

• Common Lisp: Нежное введение в символические вычисления. Это самое симпатичное нематематическое объяснение рекурсии.
• Маленький интриган

Чтобы понять рекурсию, все, что вам нужно сделать, это посмотреть на этикетке бутылки с шампунем:

function repeat()
{
   rinse();
   lather();
   repeat();
}

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

Если вам нужна книга, которая хорошо объясняет рекурсию в простых терминах, взгляните на Гёделя, Эшера, Баха: Вечная золотая коса Дугласа Хофштадтера, в частности, главу 5. В дополнение к рекурсии она хорошо объясняет ряд сложных понятий в информатике и математике понятным образом, одно объяснение опирается на другое. Если вы раньше не сталкивались с подобными понятиями, это может быть довольно умопомрачительная книга.

Это скорее жалоба, чем вопрос. У вас есть более конкретный вопрос по рекурсии? Как и умножение, люди не много пишут об этом.

Говоря о умножении, подумайте об этом.

Вопрос:

Что за * б?

Ответ:

Если b равно 1, это а. В противном случае, это + + * (б-1).

Что такое * (б-1)? Посмотрите вышеупомянутый вопрос для способа решить это.

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

function writeNumbers( aNumber ){
 write(aNumber);
 if( aNumber > 0 ){
  writeNumbers( aNumber - 1 );
 }
 else{
  return;
 }
}

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

writeNumbers( 10 );
//This wil write: 10 9 8 7 6 5 4 3 2 1 0
//and then stop because aNumber is no longer larger then 0

Что происходит в основном, так это то, что writeNumbers (10) напишет 10, а затем вызовет writeNumbers (9), который запишет 9, а затем вызовет writeNumber (8) и т. Д. приклад не будет вызывать writeNumbers (-1);

Этот код по сути такой же как:

for(i=10; i>0; i--){
 write(i);
}

Тогда зачем использовать рекурсию, вы можете спросить, если цикл for делает то же самое. Ну, вы в основном используете рекурсию, когда вам нужно вложить в петли, но вы не будете знать, насколько они глубоки. Например, при распечатке элементов из вложенных массивов:

var nestedArray = Array('Im a string', 
                        Array('Im a string nested in an array', 'me too!'),
                        'Im a string again',
                        Array('More nesting!',
                              Array('nested even more!')
                              ),
                        'Im the last string');
function printArrayItems( stringOrArray ){
 if(typeof stringOrArray === 'Array'){
   for(i=0; i<stringOrArray.length; i++){ 
     printArrayItems( stringOrArray[i] );
   }
 }
 else{
   write( stringOrArray );
 }
}

printArrayItems( stringOrArray );
//this will write:
//'Im a string' 'Im a string nested in an array' 'me too' 'Im a string again'
//'More nesting' 'Nested even more' 'Im the last string'

Эта функция может принимать массив, который может быть вложен в 100 уровней, тогда как при написании цикла for вам потребуется вложить его 100 раз:

for(i=0; i<nestedArray.length; i++){
 if(typeof nestedArray[i] == 'Array'){
  for(a=0; i<nestedArray[i].length; a++){
   if(typeof nestedArray[i][a] == 'Array'){
    for(b=0; b<nestedArray[i][a].length; b++){
     //This would be enough for the nestedAaray we have now, but you would have
     //to nest the for loops even more if you would nest the array another level
     write( nestedArray[i][a][b] );
    }//end for b
   }//endif typeod nestedArray[i][a] == 'Array'
   else{ write( nestedArray[i][a] ); }
  }//end for a
 }//endif typeod nestedArray[i] == 'Array'
 else{ write( nestedArray[i] ); }
}//end for i

Как видите, рекурсивный метод намного лучше.

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

Я постараюсь объяснить это на примере.

Вы знаете что! средства? Если нет: http://en.wikipedia.org/wiki/Factorial

3! = 1 * 2 * 3 = 6

здесь идет некоторый псевдокод

function factorial(n) {
  if (n==0) return 1
  else return (n * factorial(n-1))
}

Итак, давайте попробуем это:

factorial(3)

это н 0?

нет!

поэтому мы копаем глубже с нашей рекурсией:

3 * factorial(3-1)

3-1 = 2

2 == 0?

нет!

поэтому мы идем глубже! 3 * 2 * факториал (2-1) 2-1 = 1

1 == 0?

нет!

поэтому мы идем глубже! 3 * 2 * 1 * факториал (1-1) 1-1 = 0

0 == 0?

да!

у нас тривиальный случай

таким образом, мы имеем 3 * 2 * 1 * 1 = 6

я надеюсь, что помог вам

Рекурсия

Метод A, вызывает метод A, вызывает метод A. В конце концов, один из этих методов A не будет вызывать и выходить, но это рекурсия, потому что что-то вызывает само себя.

Пример рекурсии, где я хочу распечатать каждое имя папки на жестком диске: (в c #)

public void PrintFolderNames(DirectoryInfo directory)
{
    Console.WriteLine(directory.Name);

    DirectoryInfo[] children = directory.GetDirectories();

    foreach(var child in children)
    {
        PrintFolderNames(child); // See we call ourself here...
    }
}

Какую книгу вы используете?

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

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

Кроме того, 30 страниц в целом это много, 30 страниц на одном языке программирования сбивает с толку. Не пытайтесь изучать рекурсию в C или Java, прежде чем вы поймете рекурсию вообще из общей книги.

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

http://javabat.com - это веселое и захватывающее место для практики рекурсии. Их примеры начинаются довольно легко и проходят через обширные (если вы хотите пойти дальше). Примечание: их подход - учиться на практике. Вот рекурсивная функция, которую я написал, чтобы просто заменить цикл for.

Цикл для:

public printBar(length)
{
  String holder = "";
  for (int index = 0; i < length; i++)
  {
    holder += "*"
  }
  return holder;
}

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

public String printBar(int Length) // Method, to call the recursive function
{
  printBar(length, 0);
}

public String printBar(int length, int index) //Overloaded recursive method
{
  // To get a better idea of how this works without a for loop
  // you can also replace this if/else with the for loop and
  // operationally, it should do the same thing.
  if (index >= length)
    return "";
  else
    return "*" + printBar(length, index + 1); // Make recursive call
}

Короче говоря, рекурсия - это хороший способ написать меньше кода. В последнем printBar обратите внимание, что у нас есть оператор if. Если наше условие достигнуто, мы выйдем из рекурсии и вернемся к предыдущему методу, который вернется к предыдущему методу и т. Д. Если я отправлю в printBar (8), я получу ********. Я надеюсь, что на примере простой функции, которая делает то же самое, что и цикл for, возможно, это поможет. Вы можете практиковать это больше в Java Bat, хотя.

Истинно математический взгляд на построение рекурсивной функции заключается в следующем:

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

Вот как вы можете доказать, что функция математически верна и называется индукционной. . Это эквивалентно иметь разные базовые случаи или более сложные функции для нескольких переменных). Также эквивалентно представить, что f (x) является правильным для всех x

Теперь для «простого» примера. Создайте функцию, которая может определить, можно ли получить комбинацию монет 5 центов и 7 центов, чтобы получить х центов. Например, можно иметь 17 центов на 2x5 + 1x7, но невозможно получить 16 центов.

Теперь представьте, что у вас есть функция, которая сообщает вам, возможно ли создать x центов, если x <n. Вызовите эту функцию can_create_coins_small. Должно быть довольно просто представить, как сделать функцию для n. Теперь создайте свою функцию:

bool can_create_coins(int n)
{
    if (n >= 7 && can_create_coins_small(n-7))
        return true;
    else if (n >= 5 && can_create_coins_small(n-5))
        return true;
    else
        return false;
}

Хитрость заключается в том, чтобы понять, что тот факт, что can_create_coins работает для n, означает, что вы можете заменить can_create_coins на can_create_coins_small, давая:

bool can_create_coins(int n)
{
    if (n >= 7 && can_create_coins(n-7))
        return true;
    else if (n >= 5 && can_create_coins(n-5))
        return true;
    else
        return false;
}

Последнее, что нужно сделать, - это иметь базовый вариант, чтобы остановить бесконечную рекурсию. Обратите внимание, что если вы пытаетесь создать 0 центов, то это возможно, если у вас нет монет. Добавление этого условия дает:

bool can_create_coins(int n)
{
    if (n == 0)
        return true;
    else if (n >= 7 && can_create_coins(n-7))
        return true;
    else if (n >= 5 && can_create_coins(n-5))
        return true;
    else
        return false;
}

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

Чтобы использовать эту информацию для решения вашей проблемы в Ханойской башне, я думаю, уловка состоит в том, чтобы предположить, что у вас есть функция для перемещения n-1 таблеток с a на b (для любого a / b), пытаясь переместить n таблиц с a на b ,

Простой рекурсивный пример в Common Lisp :

MYMAP применяет функцию к каждому элементу в списке.

1) пустой список не имеет элемента, поэтому мы возвращаем пустой список - () и NIL оба являются пустым списком.

2) применить функцию к первому списку, вызвать MYMAP для остальной части списка (рекурсивный вызов) и объединить оба результата в новый список.

(DEFUN MYMAP (FUNCTION LIST)
  (IF (NULL LIST)
      ()
      (CONS (FUNCALL FUNCTION (FIRST LIST))
            (MYMAP FUNCTION (REST LIST)))))

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

В этом примере вызывается функция SIN для каждого номера в списке (1 2 3 4).

Command: (mymap 'sin '(1 2 3 4))

1 Enter MYMAP SIN (1 2 3 4)
| 2 Enter MYMAP SIN (2 3 4)
|   3 Enter MYMAP SIN (3 4)
|   | 4 Enter MYMAP SIN (4)
|   |   5 Enter MYMAP SIN NIL
|   |   5 Exit MYMAP NIL
|   | 4 Exit MYMAP (-0.75680256)
|   3 Exit MYMAP (0.14112002 -0.75680256)
| 2 Exit MYMAP (0.9092975 0.14112002 -0.75680256)
1 Exit MYMAP (0.841471 0.9092975 0.14112002 -0.75680256)

Это наш результат :

(0.841471 0.9092975 0.14112002 -0.75680256)

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

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

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

Фактически это было рекурсивное определение того, как решить проблему с рекурсией.

Дети неявно используют рекурсию, например:

Поездка в Мир Диснея

Мы уже там? (Нет)

Мы уже там? (Скоро)

Мы уже там? (Почти ...)

Мы уже там? (Тссс)

Мы уже на месте?(!!!!!)

В этот момент ребенок засыпает ...

Эта функция обратного отсчета является простым примером:

function countdown()
      {
      return (arguments[0] > 0 ?
        (
        console.log(arguments[0]),countdown(arguments[0] - 1)) : 
        "done"
        );
      }
countdown(10);

Закон Хофштадтера, применяемый к программным проектам, также имеет значение.

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

Ссылки

• Рекурсия и человеческая мысль

Работая с рекурсивными решениями, я всегда стараюсь:

• Сначала установите базовый случай, т. Е. Когда n = 1 в решении факториала
• Попробуйте придумать общее правило для каждого другого случая

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

Также было бы полезно, если бы вы могли сначала поработать над более простыми проблемами, просто чтобы освоить их. Некоторые примеры решают для факториала и порождают n-е число Фибоначчи.

Для ссылок я настоятельно рекомендую Алгоритмы Роберта Седжвика.

Надеюсь, это поможет. Удачи.

Уч. Я пытался выяснить башни Ханоя в прошлом году. Хитрость TOH в том, что это не простой пример рекурсии - у вас есть вложенные рекурсии, которые также меняют роли башен при каждом вызове. Единственный способ, которым я мог придать этому смысл, - это буквально визуализировать движение колец в моем воображении и выразить словами то, что будет рекурсивным вызовом. Я бы начал с одного кольца, потом два, потом три. Я фактически заказал игру в интернете. Мне потребовалось два или три дня, чтобы сломать мои мозги, чтобы получить это.

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

Не уверен, что эта метафора эффективна ... :-)

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

Очень распространенным случаем является обход дерева (или графика, но деревья, как правило, более распространены).
Например, иерархия папок: чтобы составить список файлов, вы по ним итерируете. Если вы найдете подкаталог, функция, перечисляющая файлы, вызывает себя с новой папкой в ​​качестве аргумента. Когда вы возвращаетесь из списка этой новой папки (и ее подпапок!), Она возобновляет свой контекст к следующему файлу (или папке).
Другой конкретный случай - рисование иерархии компонентов графического интерфейса: обычно есть контейнеры, такие как панели, для хранения компонентов, которые также могут быть панелями, или составных компонентов и т. Д. Процедура рисования рекурсивно вызывает функцию рисования каждого компонента, которая вызывает функцию рисования всех компонентов, которые он содержит, и т. д.

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

Подумайте, рабочая пчела. Он пытается сделать мед. Это делает свою работу и ожидает, что другие рабочие пчелы сделают остаток меда. И когда соты заполнены, они останавливаются.

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

Например, мы хотим рассчитать длину списка. Давайте вызовем нашу функцию magical_length и наш магический помощник с magical_length. Мы знаем, что если мы передадим подсписок, у которого нет первого элемента, он даст нам длину подсписка по волшебству. Тогда нам нужно думать только о том, как интегрировать эту информацию с нашей работой. Длина первого элемента равна 1, и magic_counter дает нам длину подсписка n-1, поэтому общая длина равна (n-1) + 1 -> n

int magical_length( list )
  sublist = rest_of_the_list( list )
  sublist_length = magical_length( sublist ) // you can think this function as magical and given to you
  return 1 + sublist_length

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

int magical_length( list )
  if ( list is empty) then
    return 0
  else
    sublist_length = magical_length( sublist ) // you can think this function as magical and given to you
    return 1 + sublist_length