#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""
Efficiency discusion using fibonacci sequence:

f(n) = f(n - 2) + f(n - 1)
     = 1 if n == 0 or n == 1
"""


# recursive Fibonacci (inefficient)
def fib_rec(n: int) -> int:
    """Return Fibonacci of x, where x is a non-negative int"""
    if n < 2:
        return n  # or 1
    else:
        return fib_rec(n - 1) + fib_rec(n - 2)


# above 30-35 this slows down terribly
for i in range(28):
    print("fib of", i, "=", fib_rec(i))


# %% Tail recursion

# fibonacci using a loop
def fib_loop(n: int) -> int:
    """
    Computes first n fib numbers, using loop
    """
    a, b = 0, 1  # the first and second Fibonacci numbers
    for i in range(n):
        a, b = b, a + b
    return a


print(fib_loop(35))


# %% tail recursive fibonacci (efficient)
def fib_rec_tail(n: int) -> int:
    """
    Computes first n fib numbers, using tail recursion
    One way of defaulting values, which hides the values.
    """

    def loop(a: int, b: int, i: int) -> int:
        if i < n:
            return loop(b, a + b, i + 1)
        else:
            return a

    return loop(0, 1, 0)


print(fib_rec_tail(35))


# %% tail recursive fibonacci (efficient)
def fib_rec_tail2(n: int, a: int = 0, b: int = 1, i: int = 0) -> int:
    """
    Computes first n fib numbers, using tail recursion
    Another way of defaulting values.
    This is both more sensible and more dangerous,
    since the user can break it.
    """
    if i < n:
        return fib_rec_tail2(n, b, a + b, i + 1)
    else:
        return a


print(fib_rec_tail2(35))