Fibonacci sequence is one of the most popular interview questions. There are several ways to implement it with Python. Let’s see how to do that.

Fibonacci Sequence

The Fibonacci Sequence is the series of numbers:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

The next number is found by adding up the two numbers before it.

The 2 is found by adding the two numbers before it (1+1)
The 3 is found by adding the two numbers before it (1+2),
And the 5 is (2+3),
and so on!

The rule of Fibonacci Sequence is

x(n) = x(n-1) + x(n-2)

where:

x(n) is term number “n”

x(n-1) is the previous term (n-1)

x(n-2) is the term before that (n-2)

source : https://www.mathsisfun.com/numbers/fibonacci-sequence.html

Method 1 : With for loop


<span># using for loop </span>
<span>def</span> <span>fibonacci_loop</span><span>(</span><span>num</span><span>):</span>
    <span>if</span> <span>num</span> <span>==</span> <span>0</span><span>:</span>
        <span>return</span> <span>0</span>
    <span>elif</span> <span>num</span> <span>==</span> <span>1</span> <span>or</span> <span>num</span> <span>==</span> <span>2</span><span>:</span>
        <span>return</span> <span>1</span>
    <span>elif</span> <span>num</span> <span>></span> <span>2</span><span>:</span>
        <span>a</span> <span>=</span> <span>1</span> <span># variable for (n - 1) </span>        <span>b</span> <span>=</span> <span>1</span> <span># variable for (n - 2) </span>        <span>for</span> <span>_</span> <span>in</span> <span>range</span><span>(</span><span>3</span><span>,</span> <span>num</span> <span>+</span> <span>1</span><span>):</span>
            <span>c</span> <span>=</span> <span>a</span> <span>+</span> <span>b</span>
            <span>a</span><span>,</span> <span>b</span> <span>=</span> <span>b</span><span>,</span> <span>c</span>
        <span>return</span> <span>c</span>
<span># using for loop </span>
<span>def</span> <span>fibonacci_loop</span><span>(</span><span>num</span><span>):</span>
    <span>if</span> <span>num</span> <span>==</span> <span>0</span><span>:</span>
        <span>return</span> <span>0</span>
    <span>elif</span> <span>num</span> <span>==</span> <span>1</span> <span>or</span> <span>num</span> <span>==</span> <span>2</span><span>:</span>
        <span>return</span> <span>1</span>
    <span>elif</span> <span>num</span> <span>></span> <span>2</span><span>:</span>
        <span>a</span> <span>=</span> <span>1</span> <span># variable for (n - 1) </span>        <span>b</span> <span>=</span> <span>1</span> <span># variable for (n - 2) </span>        <span>for</span> <span>_</span> <span>in</span> <span>range</span><span>(</span><span>3</span><span>,</span> <span>num</span> <span>+</span> <span>1</span><span>):</span>
            <span>c</span> <span>=</span> <span>a</span> <span>+</span> <span>b</span>
            <span>a</span><span>,</span> <span>b</span> <span>=</span> <span>b</span><span>,</span> <span>c</span>

        <span>return</span> <span>c</span>
# using for loop 
def fibonacci_loop(num):
    if num == 0:
        return 0
    elif num == 1 or num == 2:
        return 1
    elif num > 2:
        a = 1 # variable for (n - 1)         b = 1 # variable for (n - 2)         for _ in range(3, num + 1):
            c = a + b
            a, b = b, c

        return c


<span>%</span><span>time</span> <span>fibonacci_loop</span><span>(</span><span>40</span><span>)</span>
    <span>CPU</span> <span>times</span><span>:</span> <span>user</span> <span>6</span> <span>µ</span><span>s</span><span>,</span> <span>sys</span><span>:</span> <span>0</span> <span>ns</span><span>,</span> <span>total</span><span>:</span> <span>6</span> <span>µ</span><span>s</span>
    <span>Wall</span> <span>time</span><span>:</span> <span>8.11</span> <span>µ</span><span>s</span>
    <span>102334155</span>
<span>%</span><span>time</span> <span>fibonacci_loop</span><span>(</span><span>40</span><span>)</span>
    <span>CPU</span> <span>times</span><span>:</span> <span>user</span> <span>6</span> <span>µ</span><span>s</span><span>,</span> <span>sys</span><span>:</span> <span>0</span> <span>ns</span><span>,</span> <span>total</span><span>:</span> <span>6</span> <span>µ</span><span>s</span>
    <span>Wall</span> <span>time</span><span>:</span> <span>8.11</span> <span>µ</span><span>s</span>
    <span>102334155</span>
%time fibonacci_loop(40)
    CPU times: user 6 µs, sys: 0 ns, total: 6 µs
    Wall time: 8.11 µs
    102334155

With recursion

We can solve the problem with for-loop, but it is not so intuitive.

From the rule of fibonacci sequence x(n) = x(n-1) + x(n-2) ,

we can make a function that call itself,
it is called recursive function.


<span># Recursive Method 1 : traditional recursive function </span>
<span>def</span> <span>fibonacci_recursion</span><span>(</span><span>num</span><span>):</span>
    <span>'''Return a fibonacci sequence value of num'''</span>
    <span>if</span> <span>num</span> <span>==</span> <span>0</span><span>:</span>
        <span>return</span> <span>0</span>
    <span>if</span> <span>num</span> <span>==</span> <span>1</span> <span>or</span> <span>num</span> <span>==</span> <span>2</span><span>:</span>
        <span>return</span> <span>1</span>
    <span>return</span> <span>fibonacci_recursion</span><span>(</span><span>num</span> <span>-</span> <span>2</span><span>)</span> <span>+</span> <span>fibonacci_recursion</span><span>(</span><span>num</span> <span>-</span> <span>1</span><span>)</span>
<span># Recursive Method 1 : traditional recursive function </span>
<span>def</span> <span>fibonacci_recursion</span><span>(</span><span>num</span><span>):</span>
    <span>'''Return a fibonacci sequence value of num'''</span>
    <span>if</span> <span>num</span> <span>==</span> <span>0</span><span>:</span>
        <span>return</span> <span>0</span>
    <span>if</span> <span>num</span> <span>==</span> <span>1</span> <span>or</span> <span>num</span> <span>==</span> <span>2</span><span>:</span>
        <span>return</span> <span>1</span>

    <span>return</span> <span>fibonacci_recursion</span><span>(</span><span>num</span> <span>-</span> <span>2</span><span>)</span> <span>+</span> <span>fibonacci_recursion</span><span>(</span><span>num</span> <span>-</span> <span>1</span><span>)</span>
# Recursive Method 1 : traditional recursive function 
def fibonacci_recursion(num):
    '''Return a fibonacci sequence value of num'''
    if num == 0:
        return 0
    if num == 1 or num == 2:
        return 1

    return fibonacci_recursion(num - 2) + fibonacci_recursion(num - 1)


<span>%</span><span>time</span> <span>fibonacci_recursion</span><span>(</span><span>40</span><span>)</span>
    <span>CPU</span> <span>times</span><span>:</span> <span>user</span> <span>26.5</span> <span>s</span><span>,</span> <span>sys</span><span>:</span> <span>64</span> <span>ms</span><span>,</span> <span>total</span><span>:</span> <span>26.6</span> <span>s</span>
    <span>Wall</span> <span>time</span><span>:</span> <span>26.6</span> <span>s</span>
    <span>102334155</span>
<span>%</span><span>time</span> <span>fibonacci_recursion</span><span>(</span><span>40</span><span>)</span>
    <span>CPU</span> <span>times</span><span>:</span> <span>user</span> <span>26.5</span> <span>s</span><span>,</span> <span>sys</span><span>:</span> <span>64</span> <span>ms</span><span>,</span> <span>total</span><span>:</span> <span>26.6</span> <span>s</span>
    <span>Wall</span> <span>time</span><span>:</span> <span>26.6</span> <span>s</span>
    <span>102334155</span>
%time fibonacci_recursion(40)
    CPU times: user 26.5 s, sys: 64 ms, total: 26.6 s
    Wall time: 26.6 s
    102334155

Quiet slow??

It takes more and more time while the number is increased.

Because the function itself is needed to calculate same value over and over.

We can reduce total number of calling the function with saving the result to cache.


<span># Recursive Method 2 : With using explicit cache </span><span>cache</span> <span>=</span> <span>{}</span>
<span>def</span> <span>fibonacci_cache</span><span>(</span><span>num</span><span>):</span>
    <span>'''Return a fibonacci sequence value of num'''</span>
    <span>if</span> <span>num</span> <span>in</span> <span>cache</span><span>:</span>
        <span>return</span> <span>cache</span><span>[</span><span>num</span><span>]</span>
    <span>if</span> <span>num</span> <span>==</span> <span>0</span><span>:</span>
        <span>result</span> <span>=</span> <span>0</span>
    <span>elif</span> <span>num</span> <span>==</span> <span>1</span> <span>or</span> <span>num</span> <span>==</span> <span>2</span><span>:</span>
        <span>result</span> <span>=</span> <span>1</span>
    <span>else</span><span>:</span>
        <span>result</span> <span>=</span> <span>fibonacci_cache</span><span>(</span><span>num</span> <span>-</span> <span>2</span><span>)</span> <span>+</span> <span>fibonacci_cache</span><span>(</span><span>num</span> <span>-</span> <span>1</span><span>)</span>
    <span>cache</span><span>[</span><span>num</span><span>]</span> <span>=</span> <span>result</span>
    <span>return</span> <span>result</span>
<span># Recursive Method 2 : With using explicit cache </span><span>cache</span> <span>=</span> <span>{}</span>

<span>def</span> <span>fibonacci_cache</span><span>(</span><span>num</span><span>):</span>
    <span>'''Return a fibonacci sequence value of num'''</span>

    <span>if</span> <span>num</span> <span>in</span> <span>cache</span><span>:</span>
        <span>return</span> <span>cache</span><span>[</span><span>num</span><span>]</span>

    <span>if</span> <span>num</span> <span>==</span> <span>0</span><span>:</span>
        <span>result</span> <span>=</span> <span>0</span>
    <span>elif</span> <span>num</span> <span>==</span> <span>1</span> <span>or</span> <span>num</span> <span>==</span> <span>2</span><span>:</span>
        <span>result</span> <span>=</span> <span>1</span>
    <span>else</span><span>:</span>
        <span>result</span> <span>=</span> <span>fibonacci_cache</span><span>(</span><span>num</span> <span>-</span> <span>2</span><span>)</span> <span>+</span> <span>fibonacci_cache</span><span>(</span><span>num</span> <span>-</span> <span>1</span><span>)</span>

    <span>cache</span><span>[</span><span>num</span><span>]</span> <span>=</span> <span>result</span>
    <span>return</span> <span>result</span>
# Recursive Method 2 : With using explicit cache cache = {}

def fibonacci_cache(num):
    '''Return a fibonacci sequence value of num'''

    if num in cache:
        return cache[num]

    if num == 0:
        result = 0
    elif num == 1 or num == 2:
        result = 1
    else:
        result = fibonacci_cache(num - 2) + fibonacci_cache(num - 1)

    cache[num] = result
    return result


<span>%</span><span>time</span> <span>fibonacci_cache</span><span>(</span><span>40</span><span>)</span>
    <span>CPU</span> <span>times</span><span>:</span> <span>user</span> <span>2</span> <span>µ</span><span>s</span><span>,</span> <span>sys</span><span>:</span> <span>0</span> <span>ns</span><span>,</span> <span>total</span><span>:</span> <span>2</span> <span>µ</span><span>s</span>
    <span>Wall</span> <span>time</span><span>:</span> <span>5.01</span> <span>µ</span><span>s</span>
    <span>102334155</span>
<span>%</span><span>time</span> <span>fibonacci_cache</span><span>(</span><span>40</span><span>)</span>
    <span>CPU</span> <span>times</span><span>:</span> <span>user</span> <span>2</span> <span>µ</span><span>s</span><span>,</span> <span>sys</span><span>:</span> <span>0</span> <span>ns</span><span>,</span> <span>total</span><span>:</span> <span>2</span> <span>µ</span><span>s</span>
    <span>Wall</span> <span>time</span><span>:</span> <span>5.01</span> <span>µ</span><span>s</span>
    <span>102334155</span>
%time fibonacci_cache(40)
    CPU times: user 2 µs, sys: 0 ns, total: 2 µs
    Wall time: 5.01 µs
    102334155

same result but super faster than normal recursive function

Using LRU cache

Python provides a functools library helps the recursive function calls,

let’s use Least Recently Used cache (lru_cache) from functools


<span># import library </span><span>from</span> <span>functools</span> <span>import</span> <span>lru_cache</span>
<span># import library </span><span>from</span> <span>functools</span> <span>import</span> <span>lru_cache</span>
# import library from functools import lru_cache


<span># Recursive Method 3 : with implicit cache provided by functools </span>
<span># set cache with 1000 (need to set a big values, small cache is NOT useful) </span><span>@</span><span>lru_cache</span><span>(</span><span>maxsize</span> <span>=</span> <span>1000</span><span>)</span>
<span>def</span> <span>fibonacci</span><span>(</span><span>num</span><span>):</span>
    <span>'''Return a fibonacci sequence value of num'''</span>
    <span>if</span> <span>num</span> <span>==</span> <span>0</span><span>:</span>
        <span>return</span> <span>0</span>
    <span>if</span> <span>num</span> <span>==</span> <span>1</span> <span>or</span> <span>num</span> <span>==</span> <span>2</span><span>:</span>
        <span>return</span> <span>1</span>
    <span>return</span> <span>fibonacci</span><span>(</span><span>num</span> <span>-</span> <span>2</span><span>)</span> <span>+</span> <span>fibonacci</span><span>(</span><span>num</span> <span>-</span> <span>1</span><span>)</span>
<span># Recursive Method 3 : with implicit cache provided by functools </span>
<span># set cache with 1000 (need to set a big values, small cache is NOT useful) </span><span>@</span><span>lru_cache</span><span>(</span><span>maxsize</span> <span>=</span> <span>1000</span><span>)</span>

<span>def</span> <span>fibonacci</span><span>(</span><span>num</span><span>):</span>
    <span>'''Return a fibonacci sequence value of num'''</span>

    <span>if</span> <span>num</span> <span>==</span> <span>0</span><span>:</span>
        <span>return</span> <span>0</span>
    <span>if</span> <span>num</span> <span>==</span> <span>1</span> <span>or</span> <span>num</span> <span>==</span> <span>2</span><span>:</span>
        <span>return</span> <span>1</span>

    <span>return</span> <span>fibonacci</span><span>(</span><span>num</span> <span>-</span> <span>2</span><span>)</span> <span>+</span> <span>fibonacci</span><span>(</span><span>num</span> <span>-</span> <span>1</span><span>)</span>
# Recursive Method 3 : with implicit cache provided by functools 
# set cache with 1000 (need to set a big values, small cache is NOT useful) @lru_cache(maxsize = 1000)

def fibonacci(num):
    '''Return a fibonacci sequence value of num'''

    if num == 0:
        return 0
    if num == 1 or num == 2:
        return 1

    return fibonacci(num - 2) + fibonacci(num - 1)


<span>%</span><span>time</span> <span>fibonacci</span><span>(</span><span>40</span><span>)</span>
    <span>CPU</span> <span>times</span><span>:</span> <span>user</span> <span>3</span> <span>µ</span><span>s</span><span>,</span> <span>sys</span><span>:</span> <span>0</span> <span>ns</span><span>,</span> <span>total</span><span>:</span> <span>3</span> <span>µ</span><span>s</span>
    <span>Wall</span> <span>time</span><span>:</span> <span>5.25</span> <span>µ</span><span>s</span>
    <span>102334155</span>
<span>%</span><span>time</span> <span>fibonacci</span><span>(</span><span>40</span><span>)</span>
    <span>CPU</span> <span>times</span><span>:</span> <span>user</span> <span>3</span> <span>µ</span><span>s</span><span>,</span> <span>sys</span><span>:</span> <span>0</span> <span>ns</span><span>,</span> <span>total</span><span>:</span> <span>3</span> <span>µ</span><span>s</span>
    <span>Wall</span> <span>time</span><span>:</span> <span>5.25</span> <span>µ</span><span>s</span>
    <span>102334155</span>
%time fibonacci(40)
    CPU times: user 3 µs, sys: 0 ns, total: 3 µs
    Wall time: 5.25 µs
    102334155

Little differ time values, but it could be ignored. (just some micro seconds)

Conclusion

We need to set lru_cache when using recursive function for performance

Source : https://github.com/Teosoft7/fibonacci_python.git

原文链接：How to implement Fibonacci Sequence with Python

展开阅读全文

文章版权声明 1、本网站名称：拾光赋
2、本站永久网址：https://www.blogs.ink
3、本网站的文章部分内容可能来源于网络，仅供大家学习与参考，如有侵权，请联系站长QQ：805375623进行删除处理。
4、本站一切资源不代表本站立场，并不代表本站赞同其观点和对其真实性负责。
5、本站一律禁止以任何方式发布或转载任何违法的相关信息，访客发现请向站长举报
6、本站资源大多存储在云盘，如发现链接失效，请联系我们我们会第一时间更新。

THE END