Понимание того, как работают рекурсивные функции

1.Функция вызывается рекурсивно до тех пор, пока не будет выполнено условие. Это условие a > b. При выполнении этого условия возвращает 0. На первый взгляд, я ожидал бы, что возвращаемое значение будет 0, что явно неверно.

вот что такое компьютерные вычисления sumInts(2,5) подумал бы, если бы он мог:

I want to compute sumInts(2, 5)
for this, I need to compute sumInts(3, 5)
and add 2 to the result.
  I want to compute sumInts(3, 5)
  for this, I need to compute sumInts(4, 5)
  and add 3 to the result.
    I want to compute sumInts(4, 5)
    for this, I need to compute sumInts(5, 5)
    and add 4 to the result.
      I want to compute sumInts(5, 5)
      for this, I need to compute sumInts(6, 5)
      and add 5 to the result.
        I want to compute sumInts(6, 5)
        since 6 > 5, this is zero.
      The computation yielded 0, therefore I shall return 5 = 5 + 0.
    The computation yielded 5, therefore I shall return 9 = 4 + 5.
  The computation yielded 9, therefore I shall return 12 = 3 + 9.
The computation yielded 12, therefore I shall return 14 = 2 + 12.

как видите, некоторые вызывают функцию sumInts на самом деле возвращает 0, однако это не окончательное значение, потому что компьютер по-прежнему имеет чтобы добавить 5 к этому 0, затем 4 к результату, затем 3, затем 2, как описано в четырех последних предложениях мыслей нашего компьютера. Обратите внимание, что в рекурсии компьютер должен не только вычислить рекурсивный вызов, но и запомнить, что делать со значением, возвращенным рекурсивным вызовом. Существует специальная область памяти компьютера под названием стек где этот вид информации сохраняется, это пространство ограничено и функции, которые являются слишком рекурсивными может исчерпать стек: это переполнение стека давая свое название нашему самому любимому сайту.

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

2.Распечатка значения 'a' на каждой итерации дает значение, которое я ожидал бы: 2, 3, 4, 5 (в этот момент 5+1 > b, который соответствует первому условие: a > b) но я все еще не вижу, как достигается значение 14.

это потому, что возвращаемое значение не является a сам но сумма значения a и значение, возвращаемое рекурсивным вызовом.

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

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

позвольте мне показать вам действия:

sumInts(a: 2, b: 5) will return: 2 + sumInts(a: 3, b: 5)
sumInts(a: 3, b: 5) will return: 3 + sumInts(a: 4, b: 5)
sumInts(a: 4, b: 5) will return: 4 + sumInts(a: 5, b: 5)
sumInts(a: 5, b: 5) will return: 5 + sumInts(a: 6, b: 5)
sumInts(a: 6, b: 5) will return: 0

после sumInts(гостей: 6, Б: 5) выполняется, то результаты могут быть получены, возвращаясь по цепочке с результатами, которые вы получаете:

 sumInts(a: 6, b: 5) = 0
 sumInts(a: 5, b: 5) = 5 + 0 = 5
 sumInts(a: 4, b: 5) = 4 + 5 = 9
 sumInts(a: 3, b: 5) = 3 + 9 = 12
 sumInts(a: 2, b: 5) = 2 + 12 = 14.

другой способ представления структуры рекурсия:

 sumInts(a: 2, b: 5) = 2 + sumInts(a: 3, b: 5)
 sumInts(a: 2, b: 5) = 2 + 3 + sumInts(a: 4, b: 5)  
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + sumInts(a: 5, b: 5)  
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + 5 + sumInts(a: 6, b: 5)
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + 5 + 0
 sumInts(a: 2, b: 5) = 14 

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

приведенный здесь код решает следующую проблему: вы хотите знать сумму всех целых чисел от a до b включительно. Для вашего примера вы хотите получить сумму чисел от 2 до 5 включительно, что составляет

2 + 3 + 4 + 5

2 + (3 + 4 + 5)

здесь, (3 + 4 + 5) бывает сумма всех целых чисел от 3 до 5 включительно. Другими словами, если вы хотите знать сумму всех целых чисел между 2 и 5, Начните с вычисления суммы всех целых чисел между 3 и 5, затем добавьте 2.

так как же вычислить сумму всех целых чисел от 3 до 5 включительно? Ну, эта сумма

3 + 4 + 5

что можно придумать вместо этого как

3 + (4 + 5)

здесь! Если вы хотите вычислить сумму целых чисел между a и b включительно, вы можете сделать следующее. Во-первых, вычислить сумму целых чисел между a + 1 и B включительно. Затем добавьте к этой сумме. Вы заметите, что" вычислить сумму целых чисел между a + 1 и b, включительно", оказывается, в значительной степени той же проблемой, которую мы уже пытаемся решить, но с немного другими параметрами. Вместо вычисления от a до b включительно, мы вычисляем от A + 1 до b включительно. Это рекурсивный шаг-чтобы решить большую проблему ("сумма от a до b, включительно"), мы сводим проблему к меньшей версии самой себя ("сумма от a + От 1 до b включительно.").

если вы посмотрите на код выше, вы заметите, что этот шаг в это:

return a + sumInts(a + 1, b: b)

этот код является просто переводом приведенной выше логики - если вы хотите суммировать от a до b, включительно, начните с суммирования a + 1 до b, включительно (это рекурсивный вызов sumInt s), затем добавить a.

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

Итак, каков базовый случай в этой конкретной проблеме? Когда вы суммируете целые числа от a до b включительно, если a больше b, то ответ 0-там нет никаких чисел в диапазоне! Поэтому мы структурируем наше решение следующим образом:

1. если a > b, то ответ-0.
2. в противном случае (a ≤ b), получить ответ следующим образом:
   1. вычислить сумму целых чисел между a + 1 и b.
   2. добавьте a, чтобы получить ответ.

теперь сравните этот псевдокод с вашим фактическим кодом:

func sumInts(a: Int, b: Int) -> Int {
    if (a > b) {
        return 0
    } else {
        return a + sumInts(a + 1, b: b)
    }
}

обратите внимание, что есть почти точно взаимно однозначное отображение между решением, описанным в псевдокоде, и этим фактическим кодом. Первый шаг-это базовый случай-в случае, если вы просите сумму пустого диапазона чисел, вы получаете 0. В противном случае вычислите сумму между a + 1 и b, а затем добавьте a.

до сих пор я дал только идею высокого уровня за кодом. Но у вас были еще два очень хороших вопроса. Во-первых, почему это не всегда возвращает 0, учитывая, что функция говорит, чтобы вернуть 0, если a > b? Во-вторых, где же 14 на самом деле пришли? Давайте посмотрим на них по очереди.

давайте попробуем очень простой случай. Что произойдет, если вы позвоните sumInts(6, 5)? В этом случае, прослеживая код, вы видите, что функция просто возвращает 0. Это правильно, что в диапазоне нет никаких чисел. А теперь попробуй что-нибудь получше. Что происходит, когда вы звоните sumInts(5, 5)? Ну, вот что происходит:

1. вы называете sumInts(5, 5). Мы попадаем в else ветвь, которая возвращает значение `a + sumInts(6, 5).
2. для того чтобы sumInts(5, 5) чтобы определить, какие sumInts(6, 5) это, нам нужно приостановить то, что мы делаем, и позвонить sumInts(6, 5).
3. sumInts(6, 5) вызывается. Он входит в if филиала и возвращает 0. Однако, этот экземпляр sumInts позвонила sumInts(5, 5), поэтому возвращаемое значение передается обратно в sumInts(5, 5), не для вызывающего абонента верхнего уровня.
4. sumInts(5, 5) теперь можем вычислить 5 + sumInts(6, 5) вернуться 5. Затем он возвращает его звонящий с верхнего уровня.

обратите внимание, как здесь было сформировано значение 5. Мы начали с одного активного вызова sumInts. Это вызвало еще один рекурсивный вызов, и значение, возвращенное этим вызовом, передало информацию обратно sumInts(5, 5). Звонок в sumInts(5, 5) затем, в свою очередь, сделал некоторые вычисления и возвращает значение в вызывающую программу.

если вы попробуете это с sumInts(4, 5), вот что произойдет:

• sumInts(4, 5) пытается вернуть 4 + sumInts(5, 5). Для этого он вызывает sumInts(5, 5).
  • sumInts(5, 5) пытается вернуть 5 + sumInts(6, 5). Для этого он вызывает sumInts(6, 5).
  • sumInts(6, 5) возвращает 0 обратно в sumInts(5, 5).</li> <li>sumInts(5, 5)now has a value forsumInts(6, 5), namely 0. It then returns5 + 0 = 5`.
• имеет значение sumInts(5, 5), а именно 5. Затем он возвращает 4 + 5 = 9.

другими словами, значение, возвращаемое формируется путем суммирования значений по одному за раз, каждый раз принимая одно значение возвращается определенным рекурсивным вызовом sumInts и добавление текущего значения a. Когда рекурсия заканчивается, самый глубокий вызов возвращает 0. Однако это значение не сразу выходит из рекурсивной цепочки вызовов; вместо этого оно просто возвращает значение рекурсивному вызову на один слой выше него. Таким образом, каждый рекурсивный вызов просто добавляет еще одно число и возвращает его выше в цепочке, завершаясь общим суммированием. В качестве упражнения попробуйте проследить за этим sumInts(2, 5), С чего вы и хотели начать.

надеюсь, что это помогает!

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

во-первых, я написал много статей о простых рекурсивных алгоритмах, которые вы можете найти интересными; см.

http://ericlippert.com/tag/recursion/

http://blogs.msdn.com/b/ericlippert/archive/tags/recursion/

те в самом новом-на-верхнем заказе, поэтому начните от дно.

активация функции. Что каждый, каждый вызов делает новый активация, и рекурсивный вызов выполняется в контексте этой активации. Это хороший способ думать об этом, но есть и другой, эквивалентный способ:smart text seach-and-replace.

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

s = (a, b) => a > b ? 0 : a + s(a + 1, b)

я надеюсь, что имеет смысл. Если вы не знакомы с условным оператором, он имеет вид condition ? consequence : alternative и это значение станет ясным.

теперь мы хотим оценить s(2,5) мы делаем это, делая текстовую замену вызова с телом функции, а затем заменить a С 2 и b С 5:

s(2, 5) 
---> 2 > 5 ? 0 : 2 + s(2 + 1, 5)

теперь оцените условное. Мы текстуально заменяем 2 > 5 С false.

---> false ? 0 : 2 + s(2 + 1, 5)

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

---> 2 + s(2 + 1, 5)

теперь, чтобы спасти меня все + знаки, текстуально заменяют постоянную арифметику на ее значение. (Это немного чит, но я не хочу, чтобы отслеживать все круглые скобки!)

---> 2 + s(3, 5)

теперь поиск и замену, на этот раз с телом для вызова 3 на a и 5 для b. мы поставим замену для вызова в скобках:

---> 2 + (3 > 5 ? 0 : 3 + s(3 + 1, 5))

и теперь мы просто продолжаем делать те же самые шаги текстовой замены:

---> 2 + (false ? 0 : 3 + s(3 + 1, 5))  
---> 2 + (3 + s(3 + 1, 5))                
---> 2 + (3 + s(4, 5))                     
---> 2 + (3 + (4 > 5 ? 0 : 4 + s(4 + 1, 5)))
---> 2 + (3 + (false ? 0 : 4 + s(4 + 1, 5)))
---> 2 + (3 + (4 + s(4 + 1, 5)))
---> 2 + (3 + (4 + s(5, 5)))
---> 2 + (3 + (4 + (5 > 5 ? 0 : 5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (false ? 0 : 5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (5 + s(6, 5))))
---> 2 + (3 + (4 + (5 + (6 > 5 ? 0 : s(6 + 1, 5)))))
---> 2 + (3 + (4 + (5 + (true ? 0 : s(6 + 1, 5)))))
---> 2 + (3 + (4 + (5 + 0)))
---> 2 + (3 + (4 + 5))
---> 2 + (3 + 9)
---> 2 + 12
---> 14

все, что мы сделали здесь, было просто простой текстовой заменой. На самом деле я не должен был заменять "3" на "2+1" и так далее, пока мне не пришлось, но с педагогической точки зрения это было бы трудно читать.

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

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

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

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

первый базовый вариант:

sumInts(6, 5) = 0

тогда вызов чуть выше этого в стек вызовов:

sumInts(5, 5) == 5 + sumInts(6, 5)
sumInts(5, 5) == 5 + 0
sumInts(5, 5) == 5

затем вызов чуть выше этого в стеке вызовов:

sumInts(4, 5) == 4 + sumInts(5, 5)
sumInts(4, 5) == 4 + 5
sumInts(4, 5) == 9

и так:

sumInts(3, 5) == 3 + sumInts(4, 5)
sumInts(3, 5) == 3 + 9
sumInts(3, 5) == 12

и так:

sumInts(2, 5) == 2 + sumInts(3, 5)
sumInts(4, 5) == 2 + 12
sumInts(4, 5) == 14

уведомления это мы пришли к нашему первоначальному вызову функцииsumInts(2, 5) == 14

порядок, в котором выполняются эти вызовы:

sumInts(2, 5)
sumInts(3, 5)
sumInts(4, 5)
sumInts(5, 5)
sumInts(6, 5)

порядок, в котором эти вызовы возвращают:

sumInts(6, 5)
sumInts(5, 5)
sumInts(4, 5)
sumInts(3, 5)
sumInts(2, 5)

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

Я дам ему идти.

выполняя уравнение a + sumInts (a+1, b), я покажу, как окончательный ответ равен 14.

//the sumInts function definition
func sumInts(a: Int, b: Int) -> Int {
    if (a > b) {
        return 0
    } else {
        return a + sumInts(a + 1, b)
    }
}

Given: a = 2 and b = 5

1) 2 + sumInts(2+1, 5)

2) sumInts(3, 5) = 12
   i) 3 + sumInts(3+1, 5)
   ii) 4 + sumInts(4+1, 5)
   iii) 5 + sumInts(5+1, 5)
   iv) return 0
   v) return 5 + 0
   vi) return 4 + 5
   vii) return 3 + 9

3) 2 + 12 = 14.

дайте нам знать, если у вас возникли дополнительные вопросы.

вот еще один пример рекурсивных функций в следующем примере.

человек только что закончили колледж.

t-это количество времени в годах.

общее фактическое количество лет, отработанных до выхода на пенсию, можно рассчитать как следует:

public class DoIReallyWantToKnow 
{
    public int howLongDoIHaveToWork(int currentAge)
    {
      const int DESIRED_RETIREMENT_AGE = 65;
      double collectedMoney = 0.00; //remember, you just graduated college
      double neededMoneyToRetire = 1000000.00

      t = 0;
      return work(t+1);
    }

    public int work(int time)
    {
      collectedMoney = getCollectedMoney();

      if(currentAge >= DESIRED_RETIREMENT_AGE 
          && collectedMoney == neededMoneyToRetire
      {
        return time;
      }

      return work(time + 1);
    }
}

и этого должно быть достаточно, чтобы подавить любого, лол. ;- P

рекурсия. В информатике рекурсия подробно рассматривается в рамках темы конечных автоматов.

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

это могло бы быть по-другому, если бы заявление было "моя машина-bentley. моя машина синяя."В этом случае замена во второй ситуации для автомобиля может быть "bentley", в результате чего "мой bentley синий". Эти типы подстановок математически объясняются в информатике через Контекстно-Свободные Грамматики.

фактическая замена является производственным правилом. Учитывая, что заявление представлено и автомобиль переменная, которая может быть "Бентли" этот оператор может быть рекурсивно реконструирован.

S -> "my"S | " "S | CS | "is"S | "blue"S | ε
C -> "bentley"

это может быть построено несколькими способами, так как каждый | значит есть выбор. S может быть заменен любым из этих вариантов, и S всегда начинается пустым. Элемент ε означает прекращение производства. Так же, как S может быть заменен, так же как и другие переменные (есть только один, и это C который будет представлять "Бентли").

Итак, начнем с S будучи пустым, и заменив его на первый выбор "my"SS становится

"my"S

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

"my "S

далее позволяет выбрать C

"my "CS

и C имеет только один выбор для замены

"my bentley"S

и пространство снова для S

"my bentley "S

и так далее "my bentley is"S,"my bentley is "S,"my bentley is blue"S,"my bentley is blue" (замена S на ε завершает производство), и мы рекурсивно построили наше утверждение "мой bentley синий".

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

S -> 2 + A
A -> 3 + B
B -> 4 + C
C -> 5 + D
D -> 0

этот становится

2 + A
2 + 3 + B
2 + 3 + 4 + C
2 + 3 + 4 + 5 + D
2 + 3 + 4 + 5 + 0
14

я думаю, что лучший способ понять рекурсивные функции-это понять, что они сделаны для обработки рекурсивных структур данных. Но в вашей оригинальной функции sumInts(a: Int, b: Int) который вычисляет рекурсивно сумму чисел из a до b, это, кажется, не рекурсивная структура данных... Давайте попробуем немного измененную версию sumInts(a: Int, n: Int) здесь n сколько чисел вы добавите.

теперь, sumInts является рекурсивным за n, натуральное число. Все еще не рекурсивные данные, верно? Ну, натуральное число можно считать рекурсивной структурой данных, используя аксиомы Пеано:

enum Natural = {
    case Zero
    case Successor(Natural)
}

Итак, 0 = ноль, 1 = правопреемником(ноль), 2 = правопреемником(правопреемником(ноль)), и так далее.

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

// sums n numbers beginning from a
func sumInts(a: Int, n: Int) -> Int {
    if (n == 0) {
        // non recursive case
    } else {
        // recursive case. We use sumInts(..., n - 1)
    }
}

теперь рекурсивную функцию проще запрограммировать. Во-первых, базовый случай, n=0. Что мы должны вернуть, если мы не хотим добавлять числа? Ответ, конечно, 0.

как насчет рекурсивного случая? Если мы хотим добавить n числа, начиная с a и у нас уже есть работает sumInts функция, которая работает для n-1? Ну, нам нужно добавить a и затем вызвать sumInts С a + 1, поэтому мы заканчиваем:

// sums n numbers beginning from a
func sumInts(a: Int, n: Int) -> Int {
    if (n == 0) {
        return 0
    } else {
        return a + sumInts(a + 1, n - 1)
    }
}

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

• для базовых случаев рекурсивных данных он вычисляет ответ без использования рекурсии.
• для рекурсивных случаев рекурсивных данных он вычисляет ответ использование рекурсии над деструктурированными данными.

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

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

если Swift скомпилирован на этом языке виртуальной машины, то следующий блок кода Swift:

mult(a: 2, b: 3) - 4

будет составлять до

push constant 2  // Line 1
push constant 3  // Line 2
call mult        // Line 3
push constant 4  // Line 4
sub              // Line 5

язык виртуальных машин разработан вокруг глобальный стек. push constant n помещает целое число в этот глобальный стек.

после выполнения строк 1 и 2 стек выглядит следующим образом:

256:  2  // Argument 0
257:  3  // Argument 1

256 и 257 являются адресами памяти.

call mult помещает номер строки возврата (3) в стек и выделяет пространство для локальных переменных функции.

256:  2  // argument 0
257:  3  // argument 1
258:  3  // return line number
259:  0  // local 0

...и он идет-к этикетке function mult. Код внутри mult выполняется. В результате выполнения этого кода мы вычисляем произведение 2 и 3, которое хранится в 0-й локальной переменной функции.

256:  2  // argument 0
257:  3  // argument 1
258:  3  // return line number
259:  6  // local 0

перед returning от mult, вы заметите линия:

push local 0  // push result

мы будем толкать продукт на стек.

256:  2  // argument 0
257:  3  // argument 1
258:  3  // return line number
259:  6  // local 0
260:  6  // product

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

• поместите последнее значение в стеке в адрес памяти 0-го аргумента (в данном случае 256). Это самое удобное место, чтобы положить его.
• отбросить все в стеке до адреса 0-го аргумента.
• перейти-к номеру строки возврата (3 в данном случае), а затем продвижение.

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

256:  6  // product that we just returned

теперь мы нажимаем 4 на стек.

256:  6
257:  4

sub является примитивной функцией языка виртуальных машин. Он принимает два аргумента и возвращает свой результат в обычном адресе: адрес 0-го аргумента.

теперь у нас есть

256:  2  // 6 - 4 = 2

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

я реализовал свой sumInts функция на этом языке виртуальной машины:

function sumInts 0     // `0` means it has no local variables.
  label IF
    push argument 0
    push argument 1
    lte              
    if-goto ELSE_CASE
    push constant 0
    return
  label ELSE_CASE
    push constant 2
    push argument 0
    push constant 1
    add
    push argument 1
    call sumInts       // Line 15
    add                // Line 16
    return             // Line 17
// End of function

теперь я назову его:

push constant 2
push constant 5
call sumInts           // Line 21

код выполняется, и мы добираемся до точки остановки, где lte возвращает false. Вот как выглядит стек в этот момент:

// First invocation
256:  2   // argument 0
257:  5   // argument 1
258:  21  // return line number
259:  2   // augend
// Second
260:  3   // argument 0
261:  5   // argument 1
262:  15  // return line number
263:  3   // augend
// Third
264:  4   // argument 0
265:  5   // argument 1
266:  15  // return line number
267:  4   // augend
// Fourth
268:  5   // argument 0
269:  5   // argument 1
270:  15  // return line number
271:  5   // augend
// Fifth
272:  6   // argument 0
273:  5   // argument 1
274:  15  // return line number
275:  0   // return value

теперь давайте "раскрутим" нашу рекурсию. return 0 и Гото линия 15 и продвижение.

271:  5
272:  0

строка 16: add

271:  5

строка 17: return 5 и Гото линия 15 и заранее.

267:  4
268:  5

строка 16: add

267:  9

строка 17: return 9 и Гото линия 15 и заранее.

263:  3
264:  9

строка 16: add

263:  12

строка 17: return 12 и Гото линия 15 и заранее.

259:  2
260:  12

строка 16: add

259:  14

строка 17: return 14 и перейти линию 21 и вперед.

256:  14

вот оно. Рекурсия: Прославленные goto.

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

Я последовал http://www.htdp.org/ который, помимо того, что является учебником по схеме, также является отличным введением о том, как проектировать программы с точки зрения архитектуры и дизайн.

но в основном, вам нужно инвестировать некоторое время. Без "твердого" понимания рекурсии некоторые алгоритмы, такие как обратный путь, всегда будут казаться вам "трудными" или даже "волшебными". Итак, упорствуйте. :- D

Я надеюсь, что это помогает и удачи!

подумайте о рекурсии как несколько клонов делаешь то же самое...

вы просите клонировать[1]:"сумма чисел между 2 и 5"

+ clone[1]               knows that: result is 2 + "sum numbers between 3 and 5". so he asks to clone[2] to return: "sum numbers between 3 and 5"
|   + clone[2]           knows that: result is 3 + "sum numbers between 4 and 5". so he asks to clone[3] to return: "sum numbers between 4 and 5"
|   |   + clone[3]       knows that: result is 4 + "sum numbers between 5 and 5". so he asks to clone[4] to return: "sum numbers between 5 and 5"
|   |   |   + clone[4]   knows that: result is 5 + "sum numbers between 6 and 5". so he asks to clone[5] to return: "sum numbers between 6 and 5"
|   |   |   |   clone[5] knows that: he can't sum, because 6 is larger than 5. so he returns 0 as result.
|   |   |   + clone[4]   gets the result from clone[5] (=0)  and sums: 5 + 0,  returning 5
|   |   + clone[3]       gets the result from clone[4] (=5)  and sums: 4 + 5,  returning 9
|   + clone[2]           gets the result from clone[3] (=9)  and sums: 3 + 9,  returning 12
+ clone[1]               gets the result from clone[2] (=12) and sums: 2 + 12, returning 14

и вуаля!!

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

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

немного не по теме, я знаю, но... попробуйте посмотреть вверх рекурсия в Google... Вы увидите на примере, что это значит :-)

---

более ранние версии Google нашел следующий текст (цитируется по памяти):

рекурсия

посмотреть рекурсия

10 сентября 2014 года шутка о рекурсии была обновлена:

рекурсия

ты значит:рекурсия

---

для другого ответа см. ответ.

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

2, 3, 4, 5  //adding these numbers would sum to 14

теперь обратите внимание, что эти строки сбивают с толку (не неправильно, но запутанно).

if (a > b) {
    return 0 
}

почему тест a>b? и почемуreturn 0

Давайте изменим код, чтобы отразить точнее то, что делает человек

func sumInts(a: Int, b: Int) -> Int {
  if (a == b) {
    return b // When 'a equals b' I'm at the most Right integer, return it
  }
  else {
    return a + sumInts(a: a + 1, b: b)
  }
}

можем ли мы сделать это еще более по-человечески? Да! Обычно мы подводим слева направо (2+3+...). Но выше рекурсия суммируется справа налево (...+4+5). Измените код, чтобы отразить его (- может быть немного пугающим, но не сильно)

func sumInts(a: Int, b: Int) -> Int {
  if (a == b) {
    return b // When I'm at the most Left integer, return it
  }
  else {
    return sumInts(a: a, b: b - 1) + b
  }
}

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

then now you will understand how recursion works now take a look of this post:понять рекурсию шаг шаг за шагом

его программы :

def hello(x):
    if x==1:
        return "op"
    else:
        u=1
        e=12
        s=hello(x-1)
        e+=1
        print(s)
        print(x)
        u+=1
    return e

hello(3)

рекурсия начала иметь смысл для меня, когда я перестал читать то, что другие говорят об этом или видеть это как то, чего я могу избежать, и просто написал код. Я нашел проблему с решением и попытался дублировать решение, не глядя. Я только посмотрел на решение, когда я беспомощно застрял. Затем я вернулся к попытке повторить его. Я сделал это снова по нескольким проблемам, пока не разработал свое собственное понимание и чувство того, как идентифицировать рекурсивную проблему и решить ее. Когда я получил до этого уровня я начал придумывать проблемы и решать их. Это помогло мне больше. Иногда вещи можно узнать, только попробовав его самостоятельно и изо всех сил; пока вы "не получите его".