2014 dxdy logo

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

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




 
 Python, неожиданное поведение рекурсивной функции
Сообщение08.01.2022, 10:52 
Добрый вечер. Я написал функцию возвращающую список чисел Фибоначчи. До того как написать всё правильно, я надолго завис над неправильным вариантом кода и так и не понял почему он не работает как надо
Используется синтаксис 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 
Аватара пользователя
На так а как по вашему должен был происходить возврат значения из тех уровней рекурсии, в которых управление попадало в истинную ветку

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


?

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

 
 
 
 Re: Python, неожиданное поведение рекурсивной функции
Сообщение08.01.2022, 11:23 
TheRuinedMap в сообщении #1545485 писал(а):
самый верхний уровень рекурсии возвращал None

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

 
 
 
 Re: Python, неожиданное поведение рекурсивной функции
Сообщение08.01.2022, 12:10 
Аватара пользователя
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 
Аватара пользователя
Другими словами, имя в виду второй вариант ("как модифицированный аргумент, передаваемый в функцию по ссылке"), вы можете поступить так

Используется синтаксис 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 
TheRuinedMap в сообщении #1545573 писал(а):
return вам не понадобится вообще

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

 
 
 
 Re: Python, неожиданное поведение рекурсивной функции
Сообщение09.01.2022, 21:35 
Аватара пользователя
Cuprum2020 в сообщении #1545644 писал(а):
Вот такой код понятнее. Вообще я вроде понял в чём была проблем, print сразу все уровни рекурсии пробивает и выводит текст на экран,


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

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


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

 
 
 
 Re: Python, неожиданное поведение рекурсивной функции
Сообщение11.01.2022, 01:41 
Cuprum2020 в сообщении #1545644 писал(а):
Вообще я вроде понял в чём была проблем, print сразу все уровни рекурсии пробивает и выводит текст на экран, а вот такой внутренний return возвращает список лишь на следующий уровень рекурсии

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

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

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

 
 
 
 Re: Python, неожиданное поведение рекурсивной функции
Сообщение19.02.2022, 23:43 
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 
Посчитайте этим способом fib_rec(50), например.

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group