Только что написал такой код:

Прям до пробела соответствует тому, что приведен в Algorithms For Dummies. Написал он, ага. Учи пеп.

Вариант, что я изобрел велосипед в голову не приходил? И приведи мне это пример.

Интересно. Но я пока решил не вдаватся в функциональное программирование. Все-таки, это уже следующий этап, на мой взгляд.

Но я пока решил не вдаватся в функциональное программирование

Это не повод не использовать рекурсию.

А какие еще варианты функции, вычисляющей числа Фибоначчи приходят вам в голову?

$ clojure
Clojure 1.10.1
user=> (def fib (lazy-cat [0 1] (map + (rest fib) fib)))
#'user/fib
user=> (take 30 fib)
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368)

)))))))))))))))))))))))))))))))))))))))))

Ну, это да. Если честно, не раскрыл пока для себя тему рекурсии.

Если честно, не раскрыл пока для себя тему рекурсии.

Это когда функция вызывает саму себя. Не благодари.

 Это когда функция вызывает саму себя. Не благодари

Спасибо, Капитан Очевидность! Не хочу показаться невежлевым, но эту информацию я знаю и без твоих мудрых сентенций.

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

пустое считание. лучше пусть биткоены майнит...

Спасибо, Капитан Очевидность! Не хочу показаться невежлевым, но эту информацию я знаю и без твоих мудрых сентенций.

Так в чём проблема-то? Это самый прямой и простой способ реализовать вычисление чисел Фибоначчи (а заодно и самый медленный и плохой):

#!/usr/bin/env python3

def fibs(n: int):
    if n < 0:
        return False
    elif n == 0:
        return 0
    elif n == 1: 
        return 1
    else:
        return fibs(n - 2) + fibs(n - 1)

if __name__ == "__main__":
    print(fibs(5))

Это же пистон, т.ч. наверное как-то так:

import fibonacci

нечто глубиной в миллиард рекурсивных вызовов вряд ли сможет средний комп

С Python она по умолчанию ещё и ограничена.

А какие еще варианты функции, вычисляющей числа Фибоначчи приходят вам в голову?

def fib(n):
    q, w, e, r = 0, 1, 0, 1
    n += 1
    while n > 0:
        if n & 1:
            e, r = q * e + w * r, w * e + (q + w) * r
            n -= 1
        else:
            q, w = q * q + w * w, q * w * 2 + w * w
            n //= 2
    return e

(Конечно же это придумал не я. А жаль. Идея довольно красивая.)

Для любого языка можно найти реализацию trampoline

Это самый прямой и простой способ реализовать вычисление чисел Фибоначчи (а заодно и самый медленный и плохой)

Компилятор наверное развернет рекурсию в цикл или питон так не умеет?

Компилятор наверное развернет рекурсию в цикл или питон так не умеет?

никто не умеет, это же не хвостовая рекурсия…

А какие еще варианты функции, вычисляющей числа Фибоначчи приходят вам в голову?

#include <iostream>

template <int N>
struct Fib
{
    enum { value = Fib<N-1>::value + Fib<N-2>::value };
};

template <>
struct Fib<0>
{
    enum { value = 1 } ;
};

template <>
struct Fib<1>
{
    enum { value = 1 } ;
};

struct Null {
    typedef struct Null value;
    typedef struct Null next;
};

template <int N, template<int> typename T, int L = N>
struct Take
{
    typedef T<L-N> value;
    typedef Take<N-1, T, L> next;
};

template <template<int> typename T, int L>
struct Take<0, T, L>
{
    typedef T<L> value;
    typedef Null next;
};

template <typename T, template<typename> typename F, typename value = typename T::value, typename next = typename T::next>
struct For
{
    void operator()() {
        (F<value>())();
        (For<next, F>())();
    }
};

template <template<typename> typename F, typename value, typename next>
struct For<Null, F, value, next>
{
    void operator()() {
    }
};

template<typename value> struct Print {
    void operator()() {
        std::cout << value::value << " ";
    }
};

int main(void)
{
    (For<Take<30, Fib>, Print>())();
    std::cout << std::endl;
    return 0;
}

$ g++ fib.cpp && ./a.out
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 

Ещё немного функциональщины, без рекурсивного ограничения и даже с попыткой «тупой» оптимизации мемоизацией:

from functools import reduce


def fib(n):
    return reduce(
        lambda a, c: c > 2 and {**a, **{c: a[c - 1] + a[c - 2]}} or a,
        range(n + 1),
        {0: 0, 1: 1, 2: 1})[n]


print(fib(10000))

33644...(ещё 2080 знаков)...66875


real    0m1,199s
user    0m1,176s
sys     0m0,024s

Плюсом, сразу получаем весь ряд. )

из-за особенностей питона он будет излишне тормозить. Сделой хотя бы на генераторе.

питон циклы не очень умеет.

Немного изучил тему рекурсии, написал такой код:

#!/usr/bin/python3

def gp (af, q, n):
	if n == 1:
		return af
	if n == 2:
		return af *q**(n-1)
	return q*gp(af, q, n-1)

a = gp(2, 8, 3)
print(a)

Считает n-ый член геометрической прогрессии.

def f(n):
    sqrt5 = 5 ** .5
    golden = (1 + sqrt5) / 2
    return int(golden**n/sqrt5 +.5)

Дьёрдь Пойа тебе

если курить рекурсию - то функцию Аккермана раскури.

и apply|eval Из лишпа 1.5

перепеши их в питончик - получишь самопальный универсальный …

играясь с сим интерпретатор скобок укуришся так рекурсией что твоё умение питона достигнет Юпитера.

дерзай рекурсию правильным образом.

А питон умеет в замыкания? На луа я бы написал итератор, который помнит два последних числа и возвращает следующее. И дергай его пока не надоест. Просто, понятно, стек не кончится

def fibs(n: int) -> int:
    def iter() -> int:
        nonlocal prev, cur
        ret, prev, cur = prev, cur, cur + prev
        return ret

    assert n >= 0
    prev, cur = 0, 1

    for i in range(0, n):
        iter()
    return iter()

Типа такого?

Да это я тебе просто в копилку идей, я весь тред не читал, но вроде не было

Прикольно было бы сравнить по скорости с луа :)

синьор фибоначи девелопер к вашим услугам

print((lambda a:lambda v:a(a,v))(lambda s,x: 1 if x in [0, 1] else s(s, x-1) + s(s, x-2))(5))

пятёрку меняй на нужное число

Чет тег code у меня не работает …

[code=python] FibArray = [0,1]
def fibonacci(n): if n<0: print(«Incorrect input») elif n<=len(FibArray): return FibArray[n-1] else: temp_fib = fibonacci(n-1)+fibonacci(n-2) FibArray.append(temp_fib) return temp_fib

Driver Program

print(fibonacci(9)) [/code]

Чет тег code у меня не работает…

https://www.linux.org.ru/help/markdown.md

или при написании ответа изменить Markdown на LORCODE.

https://i.imgur.com/oNiHJbP.png

Напишите коллективную жалобу на марк даунов в l-o-r и запилите вакабамарк по умычанию.

https://habr.com/ru/post/261159/

Рекурсия - ненужно. Рекурсия в питоне = ненужно^2

Я потом исправился. Но, рекурсия - это красиво, даже в питоне.

Красиво в математике, согласен. Но не красиво когда стек переполняется. Рекурсии место там, где есть умные компиляторы, которые её в цикл разворачивать умеют.

Акермана разверни щен

http://rsdn.org/forum/philosophy/3273241.1

Спасибо! Интересный материал.

а биткоены разве не пустое считание?

затраты на добычу определяют ценность обменного средства

в строке где в N матчится N происходит стекование аргументов акерманки перед вызовом акерманки что кушает стек - т.е сия реализация не полностью концевая :)

гыы )) интересная формулировка

Акермана разверни

Он итак развернут. Проблемы (реализации) языка Аккермана не касаются

мне нравиться вот такая версия

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Компилятор наверное развернет рекурсию в цикл или питон так не умеет?

никто не умеет, это же не хвостовая рекурсия…

Умеет. GHC.