Уведомления

Группа в Telegram: @pythonsu

#1 Дек. 6, 2012 22:36:19

Lerby
Зарегистрирован: 2012-12-06
Сообщения: 2
Репутация: +  0  -
Профиль   Отправить e-mail  

Проблема с возвратом из рекурсии

Python 2.7.2

def rec(N,f1,f2):
    f=f1+f2
    if N>0:
        N=N-1
        f1=f2
        f2=f
        rec(N,f1,f2)
    else:
        print f2
        return f2
n=input('Введите n: ')
if n<=2:
    print 'n должно быть строго больше 2'
else:    
    n=n-2
    F1=1
    F2=1
    x=rec(n,F1,F2)
    print x

Если смотреть в рекурсии на
    else:
        print f2
        return f2
, то по идее должно вывести f2 и вернуть f2, но этого не происходит. Выводить то выводит, но вот возвращает “None”.
Кто может сказать, почему?

Задание - написать рекурсивную функцию вычисления n-ого числа Фибоначчи.

Отредактировано Lerby (Дек. 6, 2012 22:37:55)

Офлайн

#2 Дек. 6, 2012 22:52:19

4kpt
От: Харьков
Зарегистрирован: 2010-11-03
Сообщения: 998
Репутация: +  63  -
Профиль   Отправить e-mail  

Проблема с возвратом из рекурсии

На додумывание…

def rec(N,f1,f2):
    f=f1+f2
    if N>0:
        N=N-1
        f1=f2
        f2=f
        rec(N,f1,f2)
        return f2 #!!!!!!!!!!!!!!!!!!!!
    else:
        print f2
        return f2
n=input(u'Введите n: ')
if n<=2:
    print u'n должно быть строго больше 2'
else:
    n=n-2
    F1=1
    F2=1
    x=rec(n,F1,F2)
    print x
Обратите внимание на результат, который возвращается. Подумайте, что такое переменная в Pyton и на что она ссылается…

P.S. Считает, кстати, тоже неправильно. Результат - левачек :).



Отредактировано 4kpt (Дек. 6, 2012 23:02:32)

Офлайн

#3 Дек. 6, 2012 23:13:46

Lerby
Зарегистрирован: 2012-12-06
Сообщения: 2
Репутация: +  0  -
Профиль   Отправить e-mail  

Проблема с возвратом из рекурсии

4kpt
P.S. Считает, кстати, тоже неправильно. Результат - левачек .
Считается правильно
Для примера, сотое число Фибоначчи - 354224848179261915075

До 977 числа
678327652996327247779165248550766470831037490502555950658956568576707887540426543340885860756645125827972888077357233723647620612838774164351083221391085478586558455287774853825925814085355698767729652157

Вы, наверное, запускаете с возвратом перед else. Там да - не верное значение. А вот после else - верное.

4kpt
Обратите внимание на результат, который возвращается. Подумайте, что такое переменная в Pyton и на что она ссылается…
Даже если вместо
    x=rec(n,F1,F2)
    print x
сделать
     print rec(n,F1,F2)
то выведет None

Отредактировано Lerby (Дек. 6, 2012 23:21:27)

Офлайн

#4 Дек. 7, 2012 00:11:02

dimy44
От: Евпатория
Зарегистрирован: 2012-04-21
Сообщения: 463
Репутация: +  42  -
Профиль  

Проблема с возвратом из рекурсии

def rec(N,f1,f2):
    ...
    if N > 0:
        ...
#        rec(N, f1, f2) # неверно, rec возвратит None ;
        return rec(N, f1, f2) # верно.

Отредактировано dimy44 (Дек. 7, 2012 00:15:30)

Офлайн

#5 Дек. 7, 2012 02:42:35

4kpt
От: Харьков
Зарегистрирован: 2010-11-03
Сообщения: 998
Репутация: +  63  -
Профиль   Отправить e-mail  

Проблема с возвратом из рекурсии

Lerby
Вы правы. Не туда глянул…
Но Вы меня не поняли. Что такое переменная. Фактически это ссылка на объект.
На что ссылается х? На один объект функции, который возвращает… А ничего он не возвращает, так как это только первый шаг, в котором нет return. Я Вам это и указал.
Либо вводите дополнительную глобальную переменную, в которую сбрасывайте значение (все мое естество против этого). Либо разработайте класс и переменную для хранения временного значения необходимо сформировать как атрибут класса. Либо делайте, как указал dimy44. Его предложение самое надежное и понятное.



Отредактировано 4kpt (Дек. 7, 2012 10:38:16)

Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version