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

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

Не уверенный эта метафора является эффективной... :-)

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

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

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

Как Вы освобождаете вазу, содержащую пять цветов?

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

Как Вы освобождаете вазу, содержащую четыре цветка?

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

Как Вы освобождаете вазу, содержащую три цветка?

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

Как Вы освобождаете вазу, содержащую два цветка?

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

Как Вы освобождаете вазу, содержащую один цветок?

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

Как Вы освобождаете вазу, содержащую цветы?

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

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

Как Вы освобождаете вазу, содержащую 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, мы заменим его расширением оператора возврата:

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, мы имели дело только с единственным узлом, с помощью сингла, если/затем ответвление и два простых оператора возврата, которые почти записали себя, непосредственно от нашей спецификации?

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

Это - питание рекурсии.

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

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

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

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

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

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

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

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

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", который является действительно в алфавитном порядке.

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

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

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

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

Luc M комментарии:

ТАК должен создать значок для этого вида ответа.Поздравляю!

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

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

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

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

• Установите основной случай сначала т.е. когда n = 1 в решении факториала
• Попытайтесь придумать общее правило для любого случая

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

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

Для ссылок я настоятельно рекомендую Алгоритмы Robert Sedgewick.

Надежда, которая помогает.Удачи.

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

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

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

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

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

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

Этот пример вызывает функцию ГРЕХА на каждом числе в списке (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)

Действительно математический способ посмотреть на создание рекурсивной функции был бы следующие:

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

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

Теперь для "простого" примера. Создайте функцию, которая может определить, возможно ли иметь комбинацию монеты 5 центов и 7 центов для создания x центов. Например, возможно иметь 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 планшетов от до b (для любого a/b), пытаясь переместить n таблицы от до b.

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

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

Для цикла:

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

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

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, что мы имеем если оператор. ЕСЛИ наше условие было достигнуто, мы выйдем из рекурсии и возвратимся к предыдущему методу, который возвращается к предыдущему методу, и т.д. Если я отправил в printBar (8), я получаю ********. Я надеюсь, что с примером простой функции, которая делает то же самое как для цикла, которому, возможно, это поможет. Можно практиковать это больше в Летучей мыши Java все же.

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

Вы знаете что n! средства? Если нет: 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)

n 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 не будет звонить и выходить, но это - рекурсия, потому что что-то называет себя.

Пример рекурсии, где я хочу распечатать каждое имя папки на жестком диске: (в 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...
    }
}

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

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

То, какой bassicly происходит, - то, что writeNumbers (10) запишет 10 и затем назовет writeNumbers (9), который запишет 9 и затем назовет writeNumber (8) и т.д. До writeNumbers (1) записи 1 и затем называют writeNumbers (0), который запишет, что 0 торцов не назовут writeNumbers (-1);

Этот код является по существу тем же как:

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

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

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 уровни, в то время как Вы пишущий для цикла затем потребуете, чтобы Вы вложили ее 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

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

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

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

Разговор об умножении, думайте об этом.

Вопрос:

Что такое a*b?

Ответ:

Если b равняется 1, это - a. Иначе это - a+a* (b-1).

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

Если Вы хотите книгу, которая делает хорошее задание объяснения рекурсии простыми словами, смотрит на Gödel, Escher, Холостяка: Вечная Золотая Оплетка Douglas Hofstadter, конкретно Глава 5. В дополнение к рекурсии это делает хорошее задание объяснения многих сложных понятий в информатике и математики понятным способом с одним объяснением, основывающимся на другом. Если у Вас не было большого количества воздействия этим видам понятий прежде, это может быть довольно сногсшибательная книга.

Для понимания рекурсии все, что необходимо сделать, считать маркировку бутылки шампуня:

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

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

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

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

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

a) Read a Google's result page for "recursion"
b) Once you've read it, follow the first link on it and...
a.1)Read that new page about recursion 
b.1)Once you've read it, follow the first link on it and...
a.2)Read that new page about recursion 
b.2)Once you've read it, follow the first link on it and...

Как Вы видите, Вы делали рекурсивный материал в течение долгого времени без любых проблем.

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

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

Компьютер не может вывести разъем, таким образом, необходимо включать явное окончание: "узнайте больше о рекурсии в сети, ПОКА Вы не понимаете это, или Вы считали максимум 10 страниц".

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

"узнайте больше о рекурсии в сети, ПОКА Вы не понимаете это, или Вы считали максимум 10 страниц и запускающийся по www.google.com/search?q=recursion"

К grok все это я предлагаю, чтобы Вы попробовали любую из этих книг:

• Язык Common LISP: Нежное Введение в Символьное Вычисление. Это - самое милое нематематическое объяснение рекурсии.
• Маленький интриган.

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

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

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

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