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

Как следует из названия, у меня есть очень фундаментальный вопрос программирования, который я еще не смог разобрать. Отфильтровываем все (очень умно) «Чтобы понять рекурсию, вы должны сначала понять рекурсию». ответы из различных онлайн-тем, я все еще не совсем понимаю.

Понимая, что, когда мы сталкиваемся с незнанием того, чего мы не знаем, мы можем задавать неправильные вопросы или неправильно задавать правильные вопросы, я поделюсь тем, что я «думаю», мой вопрос в надежде, что кто-то с аналогичным мировоззрением может поделиться некоторыми немного знаний, которые помогут мне включить рекурсивную лампочку!

Вот функция (синтаксис написан на Swift):

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

Мы будем использовать 2 и 5 в качестве аргументов:

println(sumInts(a: 2, b: 5))

Очевидно, ответ - 14. Но я не понимаю, как это значение достигается.

Это мои 2 зависания:

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

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

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

var answer = a;
answer += a+1 until a > b;
return answer;   

Так что исключая магию, я просто чего-то не понимаю. Я хотел бы понять, что происходит, больше, чем просто косвенно.

Если бы кто-нибудь мог любезно объяснить, что технически происходит во время такого рода функций и почему результат не равен 0 и как, в конечном итоге a + sumInts(a: a + 1, b: b) = 14, я был бы навсегда в вашем долгу.

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

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

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

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

как «вернуть значение« а »плюс (возвращаемое значение другой копии функции, которое является значением копии« а »плюс (возвращаемое значение другой копии функции, которое является значением второй копии из ' a 'plus (... ", при этом каждая копия функции порождает новую копию самой себя с увеличенным на 1, пока не будет выполнено условие a> b.

К тому времени, когда вы достигнете истинности условия a> b, у вас будет (потенциально произвольно) длинный стек копий функции, все в середине выполнения, все ожидают результата следующей копии, чтобы узнать, что они следует добавить к «а».

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

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и значения, возвращаемого рекурсивным вызовом.

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

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

Позвольте мне показать вам шаги:

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 (a: 6, b: 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 до 5 включительно. Один из способов упростить это - заметить, что указанную выше сумму можно переписать как

2 + (3 + 4 + 5)

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

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

3 + 4 + 5

который можно рассматривать как

3 + (4 + 5)

Здесь (4 + 5) - это сумма всех целых чисел от 4 до 5 включительно. Итак, если вы хотите вычислить сумму всех чисел от 3 до 5 включительно, вы должны вычислить сумму всех целых чисел от 4 до 5, а затем добавить 3.

Здесь есть шаблон! Если вы хотите вычислить сумму целых чисел от 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 включительно (это рекурсивный вызов sumInts), а затем добавьте a.

Конечно, сам по себе такой подход не работает. Например, как бы вы вычислили сумму всех целых чисел от 5 до 5 включительно? Итак, используя нашу текущую логику, вы бы вычислили сумму всех целых чисел от 6 до 5 включительно, а затем прибавили бы 5. Итак, как вы вычислите сумму всех целых чисел от 6 до 5 включительно? Итак, используя нашу текущую логику, вы должны вычислить сумму всех целых чисел от 7 до 5 включительно, а затем добавить 6. Вы заметите здесь проблему - это просто продолжается и продолжается!

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

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

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

Теперь сравните этот псевдокод с вашим реальным кодом:

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). Вызов to, 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(4, 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/

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

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

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

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);
    }
}

И этого должно быть достаточно, чтобы угнетать кого угодно, лол. ;-П

Рекурсия. В информатике рекурсия подробно рассматривается в разделе «Конечные автоматы».

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

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

Фактическое замещение - это правило производства. Учитывая, что оператор представлен буквой S и эта машина является переменной, которая может быть «бентли», это утверждение можно рекурсивно реконструировать.

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

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

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

"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 для е заканчивает производство) и мы рекурсивно построили наше утверждение «мой Бентли синий».

Думайте о рекурсии как об этих продуктах и ​​заменах. Каждый шаг в процессе заменяет своего предшественника для получения конечного результата. В точном примере с рекурсивной суммой от 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 = Succesor (ноль), 2 = Succesor (Succesor (Zero)) и так далее.

Если у вас есть рекурсивная структура данных, у вас есть шаблон для функции. Для каждого нерекурсивного случая вы можете вычислить значение напрямую. Для рекурсивных случаев вы предполагаете, что рекурсивная функция уже работает, и используете ее для вычисления случая, но деконструируете аргумент. В случае Natural это означает, что вместо 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

Непосредственно перед returnвходом в 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

Теперь давайте «раскрутим» нашу рекурсию. return0 и перейти к строке 15 и вперед.

271:  5
272:  0

Строка 16: add

271:  5

Строка 17: return5 и переход к строке 15 и вперед.

267:  4
268:  5

Строка 16: add

267:  9

Строка 17: return9 и переход к строке 15 и вперед.

263:  3
264:  9

Строка 16: add

263:  12

Строка 17: return12 и переход к строке 15 и вперед.

259:  2
260:  12

Строка 16: add

259:  14

Строка return17:14 и переход к строке 21 и вперед.

256:  14

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

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

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

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

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

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

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

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

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

Рекурсия

См. Рекурсия

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

Рекурсия

Возможно, вы имели в виду: Рекурсия

Другой ответ см. В этом ответе .

Думайте о рекурсии как о нескольких клонах, делающих одно и то же ...

Вы просите клонировать [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

и вуаля !!

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

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)

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

Позвольте мне рассказать вам на примере ряда Фибоначчи, Фибоначчи - это

t (n) = t (n - 1) + n;

если n = 0, то 1

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

т (п-1) = т (п - 2) + п + 1;

т (п-1) = т (п - 3) + п + 1 + п;

т (п-1) = т (п - 4) + п + 1 + п + 2 + п;

,

,

,

t (n) = t (nk) + ... + (nk-3) + (nk-2) + (nk-1) + n;

мы знаем, t(0)=(n-k)равно ли 1тогда, n-k=0поэтому n=kзаменяем kна n:

т (п) = т (пп) + ... + (п-п + 3) + (п-п + 2) + (п-п + 1) + п;

если опустить, n-nто:

т (п) = т (0) + ... + 3 + 2 + 1 + (п-1) + п;

так 3+2+1+(n-1)+nнатуральное число. он рассчитывается какΣ3+2+1+(n-1)+n = n(n+1)/2 => n²+n/2

результат для fib: O(1 + n²) = O(n²)

Это лучший способ понять рекурсивное отношение