2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Python, неожиданное поведение рекурсивной функции
Сообщение08.01.2022, 10:52 


30/03/20
363
Добрый вечер. Я написал функцию возвращающую список чисел Фибоначчи. До того как написать всё правильно, я надолго завис над неправильным вариантом кода и так и не понял почему он не работает как надо
Используется синтаксис Python
def fib_rec(n, f=None):
    if f is None:
        f = [1]
    if len(f) < n:
        f.append(f[-1] + f[-2] if len(f) > 1 else f[-1])
        fib_rec(n, f)
    else:
        print(f)  # отладочная строка для вывода значения переменной f в данном блоке кода
        return f  # строка которая реально не выполнялась
    return f  # строка которая реально выполняется и делает ненужной три строки выше


print(fib_rec(int(input())))
 


Строка print(f) в блоке else: работает как надо и исправно выводит на экран список чисел, а вот ровно следующая строка return f в том же блоке кода уже не работала, вместо неё функция возвращала None пока я не додумался ещё один return прикрутить. Как такое вообще может быть что одна строка в блоке кода работает, а вторая нет?

 Профиль  
                  
 
 Re: Python, неожиданное поведение рекурсивной функции
Сообщение08.01.2022, 11:16 
Аватара пользователя


28/10/21
99
На так а как по вашему должен был происходить возврат значения из тех уровней рекурсии, в которых управление попадало в истинную ветку

Код:
if len(f) < n:


?

Вот из них и возвращалось None. В том числе и самый верхний уровень рекурсии возвращал None.

 Профиль  
                  
 
 Re: Python, неожиданное поведение рекурсивной функции
Сообщение08.01.2022, 11:23 


30/03/20
363
TheRuinedMap в сообщении #1545485 писал(а):
самый верхний уровень рекурсии возвращал None

Почему тогда этот самый верхний уровень рекурсии успешно распечатывает правильный список, но не возвращает его?

 Профиль  
                  
 
 Re: Python, неожиданное поведение рекурсивной функции
Сообщение08.01.2022, 12:10 
Аватара пользователя


28/10/21
99
Cuprum2020 в сообщении #1545486 писал(а):
TheRuinedMap в сообщении #1545485 писал(а):
самый верхний уровень рекурсии возвращал None

Почему тогда этот самый верхний уровень рекурсии успешно распечатывает правильный список, но не возвращает его?


Вы о чем?

"Успешно распечатывает правильный список" у вас, как вы сами правильно заметили выше, именно этот внутренний printf в ветке else. А это самый глубокий, самый нижний (!) уровень рекурсии. И именно и ветке else возврат результата на один уровень наверх делается правильно, ибо в эту ветку вы return таки вписали.

А вот дальше наверх никакого явного возврата уже не делается, то есть дальше наверх идет None. И на самый верх выходит None. И распечатывается на самом верху именно None. Никакого "успешно распечатывает правильный список" на самом верхнем уровне у вас не получилось.

Вот результат выполнения вашего кода без того замыкающего return на входе 5:

Код:
[1, 1, 2, 3, 5]
None


Успешный вывод [1, 1, 2, 3, 5] сделан с самого нижнего уровня рекурсии. А самый верхний уровень тупо вернул и распечатал None.

-- 08.01.2022, 01:26 --

Отдельный вопрос: какова ваша задумка по поводу способа получения результата? Вы хотели получать его как возвращаемое значение функции? Или как модифицированный аргумент, передаваемый в функцию по ссылке?

У вас в коде наблюдается какая-то беспорядочная каша из этих двух вариантов.

 Профиль  
                  
 
 Re: Python, неожиданное поведение рекурсивной функции
Сообщение09.01.2022, 04:39 
Аватара пользователя


28/10/21
99
Другими словами, имя в виду второй вариант ("как модифицированный аргумент, передаваемый в функцию по ссылке"), вы можете поступить так

Используется синтаксис Python
def fib_rec(n, f):
    if f == []:
        f.append(1)
    if len(f) < n:
        f.append(f[-1] + f[-2] if len(f) > 1 else f[-1])
        fib_rec(n, f)

f = []
fib_rec(int(input()), f)
print(f)


Тогда никакого return вам не понадобится вообще. Но это, насколько я знаю, не считается правильным подходом в Питоне.

 Профиль  
                  
 
 Re: Python, неожиданное поведение рекурсивной функции
Сообщение09.01.2022, 17:47 


30/03/20
363
TheRuinedMap в сообщении #1545573 писал(а):
return вам не понадобится вообще

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

 Профиль  
                  
 
 Re: Python, неожиданное поведение рекурсивной функции
Сообщение09.01.2022, 21:35 
Аватара пользователя


28/10/21
99
Cuprum2020 в сообщении #1545644 писал(а):
Вот такой код понятнее. Вообще я вроде понял в чём была проблем, print сразу все уровни рекурсии пробивает и выводит текст на экран,


Мне не совсем понятно это утверждение. print не пробивает никакие уровни рекурсии. Он вообще ничего не знает ни о какой рекурсии. От просто выводит текст на экран.

Cuprum2020 в сообщении #1545644 писал(а):
а вот такой внутренний return возвращает список лишь на следующий уровень рекурсии


Да, именно так работает return - возвращает результат в вызывающий код, то есть на один уровень выше. А подхватить там этот результат и вернуть его еще на один уровень выше (и т.д. и т.п. до самого верха) - ваша задача. А у вас в истинной ветке if len(f) < n: возвращаемое значение fib_rec вообще просто игнорируется.

 Профиль  
                  
 
 Re: Python, неожиданное поведение рекурсивной функции
Сообщение11.01.2022, 01:41 


15/11/15
916
Cuprum2020 в сообщении #1545644 писал(а):
Вообще я вроде понял в чём была проблем, print сразу все уровни рекурсии пробивает и выводит текст на экран, а вот такой внутренний return возвращает список лишь на следующий уровень рекурсии

Вам говорят, что у вас ретурн стоял не там, где следует. Пытаясь исправить ситуацию, вы заварили кашу )

TheRuinedMap в сообщении #1545573 писал(а):
Тогда никакого return вам не понадобится вообще. Но это, насколько я знаю, не считается правильным подходом в Питоне.

Да, по сути , ТС создал процедуру, а не функцию. Классический подход, если он не устарел конечно - создать функцию (с одним аргументом - n), которая возвращает число n-ое Фиббоначи или уж массив из n чисел.

 Профиль  
                  
 
 Re: Python, неожиданное поведение рекурсивной функции
Сообщение19.02.2022, 23:43 


12/08/21

219
Cuprum2020
TheRuinedMap
А разве не так кошернее :roll:
Используется синтаксис Python
def fib_rec(n):
    if n < 3:
     
       return 1
    else:
       
       return  fib_rec(n-1)+ fib_rec(n-2)


f=fib_rec(int(input()))
print(f)


-- 20.02.2022, 01:54 --

Ну или если надо массив всех чисел, то
Используется синтаксис Python
def fib_rec(n):
    if n == 1:
      return [1]
    elif n == 2:
       return [1,1]
    else:
   
      return fib_rec(n-1).append(fib_rec(n-1)[-1]+ fib_rec(n-1)[-2])


f=fib_rec(input())
print(f)
 


-- 20.02.2022, 02:28 --

Что-то последний код не работает, так что можно так :mrgreen:
Используется синтаксис Python
def fib_rec(n):
    if n < 3:
     
       return 1
    else:
       
       return  fib_rec(n-1)+ fib_rec(n-2)


f=[fib_rec(i+1) for i in range (int(input()))]
print(f)
 

 Профиль  
                  
 
 Re: Python, неожиданное поведение рекурсивной функции
Сообщение20.02.2022, 22:54 
Заслуженный участник


31/12/05
1405
Посчитайте этим способом fib_rec(50), например.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group