# -*- coding: UTF-8 -*-
# 作者：幻灰龙
# 标题：Python 函数递归
# 描述：递归计算斐波那契函数

from typing_extensions import runtime


def fibonacci1(n):
    if n == 1 or n == 2:
        return 1

    return fibonacci1(n-1) + fibonacci1(n-2)


def fibonacci2(n):
    if n == 1 or n == 2:
        return 1

    r = [1, 1]
    for i in range(2, n):
        r[1], r[0] = r[1]+r[0], r[1]

    return r[1]


def fibonacci_inner3(n, m, r0, r1):
    if m == n:
        return r1

    return fibonacci_inner3(n, m+1, r1, r0+r1)


def fibonacci3(n):
    return fibonacci_inner3(n, 2, 1, 1)


def fibonacci_inner4(n, r):
    if n == 1 or n == 2:
        return r

    return fibonacci_inner4(n-1, fibonacci_inner4(n-2, r))


def fibonacci4(n):
    return fibonacci_inner4(n, 0)


def fibonacci5(n):
    from math import pow, sqrt
    return int(1/sqrt(5)*(pow((1+sqrt(5))/2, n)-pow((1-sqrt(5))/2, n)))


if __name__ == '__main__':
    print(fibonacci1(20))
    print(fibonacci2(20))
    print(fibonacci3(20))
    print(fibonacci4(20))
    print(fibonacci5(20))