Объясните как работает рекурсия, на примере ЯП python

[DenisVASI]

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

Код: (python) [Выделить]

def factorial(n):
    if n <= 1: return 1
    else: return n * factorial(n - 1)

print(factorial(5))
Что происходит в пяти первых итерациях я представляю(5 умножается на 4 и.т.д)
после этого куда-то возвращается 1.
И 1 вопрос куда. И почему именно 1.
после того как 1 вернулось переменная(параметр) n начинает уменьшаться в обратном порядке. Что с ним тогда происходит. Это просто бесполезные пять итераций? Или существуют примеры когда их можно использовать, тогда подскажите когда и как.
Если у вас есть еще что казать про рекурсию(о чем я вопрос не задал в силу незнания), то пожалуйста просветите. Заранее всем спасибо.

[SkinnyJack]

И 1 вопрос куда.

в factorial(2), вестимо

И почему именно 1.

Потому что

Код: (python) [Выделить]

if n <= 1: return 1

n начинает уменьшаться в обратном порядке.

Увеличиваться? нет, ничего оно не уменьшается, у каждого вызова функции своя n.

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

(Нажмите, чтобы показать/скрыть)

(Для пяти мне расписывать лень, я напишу про три)
вызываем функцию и передаём в неё параметр
factorial(3)
проверяем условие, получается что нам надо вернуть n*factorial(n-1)
чтобы вернуть это значение вызываем функцию factorial(n-1) т.е. factorial(2)
опять проверяем условие, опять идём по ветке, возвращающей n*factorial(n-1)
вызываем функцию factorial(1)
проверяем условие идём по первой ветке возвращаем на предыдущий уровень единицу
выполнение предыдущей функции остановилось на вычислении значения которое надо вернуть, точнее n*factorial(1),
n  для этой функции равно двум, а значение факториала нам вернулось поэтому считаем 2*1 = 2, возвращаем это значение
самый первый вызов функции тоже остановился на вычислении значения для возврата и там мы считаем 3*2 = 6 что и возвращаем.

(Нажмите, чтобы показать/скрыть)

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

[Jack Sparrow]

https://forum.ubuntu.ru/index.php?topic=218329.msg1683282#msg1683282
Раздел в книге 5.8 о рекурсии.

[peregrine]

DenisVASI, тебе надо не про программирование читать, а про архитектуру ЭВМ. Любая рекурсивная функция просто вызывает сама себя, пока не выполнится какое-либо условие, из-за этого рекурсия кушает стек, т.к. старые вызовы туда записываются, а после выполнения условия функции выполняются из стека. Конечно, компиляторы стараются развернуть рекурсию, но от этого изменится только потребление стека, а результат останется прежним. У тебя вот что происходит:
Вызывается функция с n=5, идем в условие else, вызываем функцию (ничего пока не умножается), n как была 5, так и отправляется в стек, функция вызывается с аргументом 4, дальше по аналогии. Когда дойдет до return 1, всё пойдет разворачиваться из стека, 1*2*3*4*5.

Как-то так, хотя я давно теорию не смотрел, могу малость путать.

[alsoijw]

peregrine, хороших манов очень мало.
DenisVASI, рекурсия это когда функция вызывает саму себя. Это понятно? У любой рекурсии должно быть условие, когда дальнейший вызов себя прекращается. Иначе программа зациклится(зависнет). Это понятно? Вот примерно что происходит в твоём примере.

Код: [Выделить]

factorial(5)
5 * factorial(4)
5 * 4 * factorial(3)
5 * 4 * 3 * factorial(2)
5 * 4 * 3 * 2 * factorial(1)
5 * 4 * 3 * 2 * 1
5 * 4 * 3 * 2
5 * 4 * 6
5 * 24
120Понятно? Условие выхода должно быть. Любое. Можно было бы написать условие выхода ещё и для 2, 3... Но это заняло бы много текста.

[DenisVASI]

alsoijw, получается условием для выхода является

Код: (python) [Выделить]

if n <= 1:
    return 1
а для чего здесь возвращается именно 1?
И почему-то ваш пример как мне показалось не совсем согласуется с ответом peregrine, или что-то упустил?
Пользователь решил продолжить мысль 12 Июля 2015, 11:11:01:alsoijw, понимаю что долго, но приведите пожалуйста пример того, как можно написать условие выхода для 2,3,и.т.д, потому как я все еще не совсем хорошо понимаю как это сделать, спасибо всем.

[alsoijw]

а для чего здесь возвращается именно 1?

Ты понимаешь что такое факториал?

И почему-то ваш пример как мне показалось не совсем согласуется с ответом peregrine, или что-то упустил?

DenisVASI, какая часть моего ответа и ответа peregrine различаются?

Пользователь решил продолжить мысль [time]12 Июль 2015, 10:11:01[/time]:alsoijw, понимаю что долго, но приведите пожалуйста пример того, как можно написать условие выхода для 2,3,и.т.д, потому как я все еще не совсем хорошо понимаю как это сделать, спасибо всем.

Понимаешь if|elif|else или нет?

[DenisVASI]

1) да
2) разобрался уже
3) да
 
Пользователь решил продолжить мысль [time]12 Июль 2015, 14:40:07[/time]:в данном примере я не понимаю почему я должен возвращать 1, почему не 0 например?

[peregrine]

DenisVASI, факториал 5 по определению это 1*2*3*4*5 факториал 4-ёх это 1*2*3*4 Если ты 0 вернёшь, то у тебя будет 0*1*2*3*4*5=0 А это не факториал.

[alsoijw]

Пользователь решил продолжить мысль [time]12 Июль 2015, 10:11:01[/time]:alsoijw, понимаю что долго, но приведите пожалуйста пример того, как можно написать условие выхода для 2,3,и.т.д, потому как я все еще не совсем хорошо понимаю как это сделать, спасибо всем.

DenisVASI, добавь условие elif

[symon2014]

Берёте пистолет(задачу) и 5 патронов(аргумент), вставляете в обойму(стек) начиная с патрона №5. Передёргиваете затвор и начинаете срелять в обратном порядке(рекурсия). Выстрелы не складывать а умножать номера патронов. Получится 120. Где-то так.