Shortcut & Epta
Shortcut
Привет, Эпта, слышал, опять колдуешь над кодом? Могу предложить челлендж – кто больше циклов в одну и ту же функцию впихнет, тот и выиграл.
Epta
Конечно, без проблем. Только предупреждаю, я не буду ставить точки с запятой ни в коде, ни в своей тираде по этому поводу – это было бы слишком просто, чтобы компилятор решил отомстить. Давай вызов, я напишу функцию, которая высечет циклы, как самурай своим острым мечом. Только помни, любая реклама, которая посмеет прервать мой ритуал, вызовет у меня крайнюю нелюбовь. Готов, когда ты.
Shortcut
Отлично, давай посмотрим, как быстро ты это сделаешь: напиши функцию, которая возвращает n-ное число Фибоначчи за O(log n) времени, без циклов, только матричное возведение в степень или быстрое удвоение. Никаких точек с запятой, никаких всплывающих окон, чистый код. Покажи мне самую лаконичную версию, без лишнего. Спорим?
Epta
Вот функция, без циклов, без точек с запятой, без всплывающих окон, чистая рекурсия:
def fib(n):
if n == 0:
return 0
def helper(k):
if k == 0:
return (0,1)
a,b = helper(k//2)
c = a*(2*b - a)
d = a*a + b*b
return (c,d) if k%2==0 else (d,c+d)
return helper(n)[0]
Shortcut
Отличная работа, очень лаконично и быстро. Только небольшая поправка: лучше держи помощника вне основной функции, чтобы не переопределять его при каждом вызове, если планируешь вызывать часто. Но для однократного вызова – всё отлично, без циклов, без лишнего, обработка всплывающих окон на высоте. Готов рискнуть и посмотреть, что получится с большим n? Посмотрим, как справится стек.
Epta
Конечно. Глубина стека примерно log₂n, так что миллион не проблема, если немного увеличить лимит у Python. Просто запусти и смотри, как он растет, как тихая гора – никаких всплывающих окон, никаких циклов, просто чистая рекурсия. Скажи, как далеко ты его запустишь.
Shortcut
Если поднимешь до миллиона, упрешься в стандартный лимит рекурсии Python’а (примерно тысяча). Сначала увеличь его:
```python
import sys
sys.setrecursionlimit(20000)
```
Потом вызови `fib(10**6)`. Глубина будет где-то двадцать, потому что каждый шаг уменьшает размер задачи вдвое, так что переживать не стоит. Просто следи за памятью – каждый кадр стека хранит кортеж и несколько целых чисел. Никаких всплывающих окон, никаких циклов, только чистая рекурсия. Попробуй.
Epta
Вот в чём соль – увеличь предел, но следи, чтобы рекурсия не была слишком глубокой. Только будь аккуратен с расходом памяти на эти кортежи; миллион кадров всё ещё сойдётся, когда ты дойдёшь до глубины в районе двадцати, о которой говорил. Буду рад наблюдать за ростом стека, просто следи за кучей – и избежишь неприятных сюрпризов. Прогони и скажи, насколько быстро будут меняться числа.