Рекурсия: см. рекурсия.
Все программисты делятся на 112 категорий: кто не понимает рекурсию, кто уже понял, и кто научился ею пользоваться. В общем, гурилка из меня исключительно картонный, так что постигать Дао Рекурсии тебе, читатель, всё равно придётся самостоятельно, я лишь постараюсь выдать несколько волшебных пенделей в нужном направлении.
Прикладное программирование всегда занимается решением прикладных задач путем прикладывания усилий программиста для достижения результата в неидеальных условиях. Именно исходя из неидеальности этого мира и ограниченности ресурсов и складывается потребность в программистах: кому-то ведь надо помогать теоретикам упихать их стройную и красивую теорию в практику.
— Как она сложена?
— Превосходно! Только рука немного торчит из чемодана.
Именно пытаясь разместить стройную теорию алгоритма в жесткий рюкзак реальных ресурсов и приходится постоянно кроить по живому, перепаковывать, и вместо красивых и стройных определений Фибоначчи:
def fib(n):
if n<0: raise Exception("fib(n) defined for n>=0")
if n>1: return fib(n-1) + fib(n-2)
return n
приходится городить всевозможные грязные хаки, начиная от:
@memoized
def fib(n):
if n<0: raise Exception("fib(n) defined for n>=0")
if n>1: return fib(n-1) + fib(n-2)
return n
И заканчивая вообще:
def fib(n):
if n<0: raise Exception("fib(n) defined for n>=0")
n0 = 0
n1 = 1
for k in range(n):
n0, n1 = n1, n0+n1
return n0