DjangoBB LoFi version

Полная версия: Объясните пожалуйста, как работает эта функция

Начало » Центр помощи » Объясните пожалуйста, как работает эта функция

Mr.Geekman

Май 1, 2016 11:07:24

a_factaral = lambda n:(n>0 and ((n==0 and 1)+n)*a_factaral(n-1))+(n==0 and 1)

распишите пожалуйста алгоритм работы

JOHN_16

Май 1, 2016 12:07:50

Это рекурсия, построенная на анонимной функции ( лямбда ).

def a_factral(n):
    return (n > 0 and ((n == 0 and 1) + n) * a_factaral(n - 1)) + (n == 0 and 1)

Mr.Geekman

Май 1, 2016 13:05:02

Мне хотелось бы узнать суть алгоритма и значение оператора and здесь

old_monty

Май 1, 2016 18:47:09

Mr.Geekman
Мне хотелось бы узнать суть алгоритма и значение оператора and здесь

1. Суть алгоритма - реализация функции для вычисления факториала от целого числа n.
2. Самое лучшее объяснение действия логических операций (в том числе and) приведено в документации на сайте docs.python.org
3. Из приведенной выше ссылки очень важно понять (и всегда помнить), что действие оператора and не ограничивается возвратом True или False. Он может возвращать и другие (например, численные) значения:

>>> False and 10
False
>>> True and 10
10

4. В Python (по крайней мере, в версии 3.x) допускается производить арифметические действия, смешивая тип bool и тип int:

>>> b = False
>>> b + 5
5
>>> b = True
>>> b + 5
6

5. Как только это станет ясно, так сразу станет очень простой и понятной работа вашей функции a_factaral(n). (Хотя такая реализация факториала, имхо, плохой стиль программирования.)

Vlad_Ki

Май 1, 2016 19:14:40

Я вот не могу понять до какого момента вычисляется возвращаемое значение. Ведь тут на лицо рекурсия. Буду рад, если кто то объяснит. Вообще удивился когда эта функция мне вернула значение.

old_monty

Май 1, 2016 19:28:26

Vlad_Ki
Я вот не могу понять до какого момента вычисляется возвращаемое значение. Ведь тут на лицо рекурсия.

Что здесь рекурсия, об этом я даже говорить не стал, настолько это очевидно. Ведь вычисление a_factaral(n) выполняется через вызов a_factaral(n-1) и т.д., пока не дойдет до вычисления a_factaral(1) или a_factaral(0), если n == 0, а потом идет обратная раскрутка стека. Основную трудность у ТС, как я понял, вызывают неочевидные логические операции - их действительно трудно понять, если ошибочно думать, что результат операции and может быть только True или False.

py.user.next

Май 2, 2016 02:35:32

Vlad_Ki
Я вот не могу понять до какого момента вычисляется возвращаемое значение. Ведь тут на лицо рекурсия. Буду рад, если кто то объяснит. Вообще удивился когда эта функция мне вернула значение.

Оно всегда вычисляется, на каждом шаге. Не может быть такого, что функция не вернёт число, где бы она не была вызвана.

Чтобы понять рекурсию, представляй, что функция вызывает не саму себя, а вызывает совершенно другую функцию, которая просто на неё очень сильно похожа. Представь, что у тебя записаны 100 функций и все они похожи друг на друга так, что выглядят одинаково. Тогда первая функция вызывает вторую, вторая вызывает третью, третья вызывает четвёртую и так далее. Каждая функция что-то вычисляет и передаёт этот результат функции, вызывающей её.

Vlad_Ki
Я вот не могу понять до какого момента вычисляется возвращаемое значение.

Есть такой приём при работе с рекурсией: задайся вопросом “Что делает функция на максимальной глубине?”

Берём вариант от JOHN_16 и пытаемся его понять через наш метод: сначала мы ищем, что происходит на самом глубоком уровне; затем мы ищем, что происходит на уровне, который находится на один выше самого глубокого уровня; далее мы эти уровни связываем между собой через возвращаемое значение, которое возвращается с самого глубокого уровня на уровень, который на один выше самого глубокого уровня. Так мы поймём весь рекурсивный процесс, какая бы глубина у него ни была.

(Слово factaral неправильное, нужно использовать слово factorial, но мы его не будем менять, оставив как есть, для сохранения условий более близкими к условиям дикого мира. В диком мире программ ещё и не такое увидишь. Это просто один из индикаторов плохого знания английского языка, которое выливается в кучу таких ошибок в коде, которые его затуманивают для чтения и понимания другими участниками разработки.)

 def a_factaral(n):
    return (n > 0 and ((n == 0 and 1) + n) * a_factaral(n - 1)) + (n == 0 and 1)

Ищем вызов функции в функции и видим, что n уменьшается на единицу

 a_factaral(n - 1)

Если мы подадим 10, то на максимальной глубине n будет равно нулю.
(Мы видим, что при всех значениях выше нуля поведение функции будет одно и то же, а при нуле оно станет каким-то другим, поменяется.)
Так мы понимаем, что ноль - это, скорее всего, самый глубокий уровень данной рекурсии.

Подставляем везде ноль вместо n

 def a_factaral(0):
    return (0 > 0 and ((0 == 0 and 1) + 0) * a_factaral(0 - 1)) + (0 == 0 and 1)

На максимальной глубине получится

 return False + 1

Дальше 0 > 0 оно не пройдёт в левой части операции +, а результат сравнения 0 > 0 равен False. Поэтому возвращаемое значение функции на максимальной глубине равно единице. Вызова a_factaral(-1) не произойдёт, поэтому мы его не считаем уровнем, который глубже нулевого. Следовательно, самый глубокий уровень данной рекурсии находится на нулевом аргументе функции. И значение функции на этом уровне равно единице, так как False + 1 = 1.

Теперь возьмём на один уровень выше уровня максимальной глубины
На нём n равно единице, заменяем все n на единицы

 def a_factaral(1):
    return (1 > 0 and ((1 == 0 and 1) + 1) * a_factaral(1 - 1)) + (1 == 0 and 1)

Мы видим, что можем заменить вызов функции на число, так как знаем значение функции на максимальной глубине, где n равно нулю, так как вычислили его только что до этого

 def a_factaral(1):
    return (1 > 0 and ((1 == 0 and 1) + 1) * 1) + (1 == 0 and 1)

На этом уровне (на один выше самого глубокого) получится

 return ((False + 1) * 1) + False

Поэтому возвращаемое значение функции на этой глубине тоже равно единице.
То есть a_factoral(0) = 1 и a_factoral(1) = 1

Для понимания данного процесса рекурсии этого достаточно - рассмотрения двух уровней глубины (самого глубокого и на один выше самого глубокого).

Просто для того, чтобы убедиться в своей правоте, мы можем рассмотреть ещё один уровень выше.
Если мы рассмотрим всё то же самое для двойки, то мы получим a_factoral(2) = 2

 def a_factaral(2):
    return (2 > 0 and ((2 == 0 and 1) + 2) * a_factaral(2 - 1)) + (2 == 0 and 1)

Заменив вызов функции a_factoral(2 - 1), который равен a_factora(1), который равен 1, мы получим возвращаемое значение для двойки

     return (2 > 0 and ((2 == 0 and 1) + 2) * 1) + (2 == 0 and 1)

Упростим его

     return ((False + 2) * 1) + False

То есть a_factoral(2) = 2

Так мы убедились ещё раз, что значение меняется аналогично в результате рекурсивного процесса. Обычно всё изучение рекурсивной функции (которая уже есть или которую нужно сделать) заканчивается на двух уровнях глубины. Третий уровень глубины можно не рассматривать, так как он ничего нового не даёт в плане знаний; он просто повторяет то же самое, что уже известно.

Вот обычно при составлении (или анализе) рекурсивной функции достаточно рассмотреть два уровня: самый глубокий и на один уровень выше от самого глубокого. На самом глубоком уровне можно вычислить значение функции без каких-либо допольнительных вызовов. А на уровне на один выше от самого глубокого можно отследить передачу значения из внутреннего вызова во внешний по отношению к нему вызов и понять, правильно ли это возвращаемое значение используется в вычислениях.

tags: recursion

Vlad_Ki

Май 5, 2016 20:45:23

py.user.next
Спасибо большое за развернутый ответ!