Ния
Точно именно такое задание?
Может быть, имело ввиду: вызов рекурсии проходил один раз для каждого n?

Да, ваш вариант, я не совсем правильно перевела, думаю

Ния
Ну тогда создаем массив n чисел, забиваем нулями. При вычислении либо берем значение из массива, либо вычисляем и кладем в массив.
Т.е. по одному высилению каждого числа.

Не совсем поняла, можно поподробнее про либо берем значение из массива, либо вычисляем и кладем в массив.?

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

если уж рекурсия так нужна, то я бы сделал так:

def fib(arr, n): # print arr if n == 0: return arr[-1] else: arr.append(arr[-1]+arr[-2]) return fib(arr, n-1) for i in range(12): print fib([0, 1], i)

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

в википедии есть формула Бине для чисел фибоначчи, и можно рекурсию использовать чтобы фи^n вычислять, но это имхо уже извращение

Помнится, в какой-то книге по лиспу видел что-то подобное (в переложении на пайтон):

def _fibonacci(n,partfib): if n == 0 : return partfib else return _fibonacci(n-1,partfib+n) def fibonacci(n): return _fibonacci(n,0);

Наверное, будет правомочно переписать и так:
def fibonacci(n,__pfib=0): if n == 0 : return __pfib else return fibonacci(n-1,__pfib+n)

Ай, тьфу, блин, фигню написал...

Так. Дубль два. Вспомню те же рассуждения, что были в книге.
fibonacci(n) вызывает fibonacci(n-1) и fibonacci(n-2). Но fibonacci(n-1) также вызывает fibonacci(n-2). Непорядок. Надо, чтобы функция вызывалась только единожды с каждым аргументом. Что можно сделать?
Посмотрим... Пусть:

а(n) = fibonacci(n),
b(n) = fibonacci(n+1)

Тогда:

b(n)=a(n+1) <=> a(n)=b(n-1)
b(n)=fibonacci(n+1)=fibonacci(n)+fibonacci(n-1)=a(n)+a(n-1)=b(n-1)+a(n-1)

Т.е. видим, что:
a(n)=b(n-1)
b(n)=b(n-1)+a(n-1)
fibonacci(n)=a(n)
a(0)=fibonacci(0)=0
b(0)=fibonacci(0+1)=1

Получили зависимость a(n) и b(n) от значений a(n-1) и b(n-1). Причём, нигде n явно не фигурирует. Исключительно как счётчик итераций. А значит, нам в общем-то всё равно, будет ли n возрастать c 0 до заданного значения, или же убывать с заданного значения до 0 - общее число итераций там и там будет то же.

Значит, можно написать следующую функцию:
def fibonacci(n,__a=0,__b=1) if n == 0: return __a else return fibonacci(n-1, __b, __a+__b)

Вроде, должно работать.

P.s. а предыдущего бреда вы не видели, хорошо? =)

Всем спасибо больше