Форум сайта python.su
PooHС первым вроде понятно в этом примере, а условие выхода в этом случае какое? ) Посчитанный факториал?Djony1987Дык прелесть рекурсии именно в том что тебе не надо понимать все целиком, тебе надо понять:
Главное более сложные примеры понять
1. Как выполняется единичный вызов
2. Условие выхода
и все ;)
Офлайн
Условие выхода - n == 0. Когда это условие выполнится, вместо того чтобы очередной раз вызвать функцию, будет просто возвращена единица.
Офлайн
ZANЯсно. Спасибо!
Условие выхода - n == 0. Когда это условие выполнится, вместо того чтобы очередной раз вызвать функцию, будет просто возвращена единица.
Офлайн
Я сам сначала не мог понять, как работает рекурсия, ни на одном сайте не нашел развернутого примера.
Начал писать цепочку на листе бумаги для наглядности вот так:
Здесь вычисляется рекурсия (5)
f(n)=n+f(n-1)
f(5) = 5+f(n-1) = 5+f(4) = 15 --------------------f(4) = 4+f(n-1) = 4+f(3) = 10 ----------------------------------------f(3) = 3+f(n-1) = 3+f(2) = 6 ------------------------------------------------------------f(2) = 2+f(n-1) = 2+f(1) = 3 --------------------------------------------------------------------------------f(1) = 1+f(n-1) = 1+f(0) = 1 ------------------------------------------------------------------------------------------------(#Здесь f(n) становится =0) Вначале развертываем выражение пока (n) не станет равным нулю (f(1) = 1+f(n-1) = 1+f(0) = 1), значить f(1) = 1, начинаем подставлять в обратном порядке f(1) = 1 ------------------------------------------------------------f(2) = 2+f(1) = 2+1 = 3 ----------------------------------------f(3) = 3+f(2) = 3+3=6 -------------------f(4) = 4+f(3) = 4+6 = 10 f(5) = 5+f(4) = 5+10 = 15
def mysum(L): ... if not L: ... return 0 ... else: ... return L[0] + mysum(L[1:]) # Вызывает себя саму >>> mysum([1, 2, 3, 4, 5]) 15 mysum([1,2,3,4,5]) = 1+mysum([2,3,4,5]) -----------------------mysum([2,3,4,5]) = 2+mysum([3,4,5]) --------------------------------------------mysum([3,4,5]) = 3+mysum([4,5]) ---------------------------------------------------------------mysum([4,5]) = 4+mysum([5]) --------------------------------------------------------------------------------mysum([5]) = 5+mysume([]) ---В списке нет больше чисел, возвращается ноль(0) ----------------------------------------------------------------------------------------------------------------------------mysum([0]) = 0+mysum([0]) = 0 --------------------------------------------------------------------------------mysum([5]) = 5+mysum([]) = 5+0 = 5 ---------------------------------------------------------------mysum([4,5]) = 4+mysum([5]) = 4+5 = 9 --------------------------------------------mysum([3,4,5]) = 3+mysum([4,5]) = 3+9 = 12 -----------------------mysum([2,3,4,5]) = 2+mysum([3,4,5]) = 2+12 = 14 mysum([1,2,3,4,5]) = 1+mysum([2,3,4,5]) = 1+14 = 15
Отредактировано grand (Сен. 19, 2013 12:45:49)
Офлайн
Djony1987, когда речь идёт об изучении рекурсии, вспоминают факториал, функцию Аккермана и “Ханойские башни” . Советую прочесть книгу Кнута, Грэхема и Паташника “Конкретная математика. Основание информатики.”. Там про рекуррентные соотношения очень доходчиво описано, да и вообще про всё .
А большинство там просто писать без ошибок не в состоянии, какое там программирование.Ну грамматика в ЯП проще чем в натуральных языках .
Отредактировано Euler (Сен. 19, 2013 16:37:04)
Офлайн