← Сtrl

Djony1987 · Янв. 23, 2009 07:44:25

PooH
Djony1987
Главное более сложные примеры понять
Дык прелесть рекурсии именно в том что тебе не надо понимать все целиком, тебе надо понять:
1. Как выполняется единичный вызов
2. Условие выхода
и все ;)

С первым вроде понятно в этом примере, а условие выхода в этом случае какое? ) Посчитанный факториал?

ZAN · Янв. 23, 2009 10:36:51

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

Djony1987 · Янв. 23, 2009 20:14:36

ZAN
Условие выхода - n == 0. Когда это условие выполнится, вместо того чтобы очередной раз вызвать функцию, будет просто возвращена единица.

Ясно. Спасибо!

grand · Сен. 19, 2013 12:28:48

Я сам сначала не мог понять, как работает рекурсия, ни на одном сайте не нашел развернутого примера.
Начал писать цепочку на листе бумаги для наглядности вот так:
Здесь вычисляется рекурсия (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

Вроде так. Факториал высчитывается ‘ умножением(*) ’, все тоже самое.

Вот кстати пример из Лутца “Изучаем Python(4 издание)”:

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)

Euler · Сен. 19, 2013 16:36:11

Djony1987, когда речь идёт об изучении рекурсии, вспоминают факториал, функцию Аккермана и “Ханойские башни” . Советую прочесть книгу Кнута, Грэхема и Паташника “Конкретная математика. Основание информатики.”. Там про рекуррентные соотношения очень доходчиво описано, да и вообще про всё .

А большинство там просто писать без ошибок не в состоянии, какое там программирование.

Ну грамматика в ЯП проще чем в натуральных языках

.

Отредактировано Euler (Сен. 19, 2013 16:37:04)

Python-сообщество

Уведомления

#1 Янв. 23, 2009 07:44:25

Рекурсия в Python

#2 Янв. 23, 2009 10:36:51

Рекурсия в Python

#3 Янв. 23, 2009 20:14:36

Рекурсия в Python

#4 Сен. 19, 2013 12:28:48

Рекурсия в Python

#5 Сен. 19, 2013 16:36:11

Рекурсия в Python

Board footer