#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Nov 26 11:49:13 2019

@author: andrea
"""

# fibo(N) = 1 se N < 2
# fibo(N) = fibo(N-1)+fibo(N-2) altrimenti

def fibo(N):
    if N < 2:
        return 1
    else:
        return fibo(N-1)+fibo(N-2)

# 0 1 2 3 4 5 6
# 1 1 2 3 5 8 13
        
    
    
# memorizziamo i risultati in un dizionario
def fibo_memo(N, dizionario):
    if N in dizionario:
        return dizionario[N]
    if N < 2:
        risultato = 1
    else:
        risultato = fibo_memo(N-1, dizionario) + fibo_memo(N-2, dizionario)
    dizionario[N] = risultato
    return risultato


# fibo lineare iterativa (simulazione delle nascite)
# si parte da F1=1 F2=1 (ultimo anno ed anno precedente)
# dal secondo anno in poi si sommano i due ultimi valori
def fibo_iter(N):
    F1 = 1
    F2 = 1
    while N > 1:
        F1, F2 = F1+F2, F1
        N -= 1
    return F1

# fibo lineare ricorsiva (simuliamo l'iterazione con una ricorsione)
# versione che fa i conti in entrata nella ricorsione

def fibo_lin_ric(N, F1, F2):
    if N <= 1:
        return F1
    else:
        return fibo_lin_ric(N-1, F1+F2, F1)





# fibo lineare ricorsiva (simuliamo l'iterazione con una ricorsione)
# versione che fa i conti in uscita dalla ricorsione
# fibo(N) = 1, 1 se N < 2
# fibo(N) = sum(fibo(N-1)), fibo(N-1)


# 
def fibo_ric_lin(N):
    if N < 2:
        return 1, 1
    else:
        F1, F2 = fibo_ric_lin(N-1)
        F1, F2 = F1+F2, F1
        return F1, F2

from random import randint
def random_color():
    return (randint(0,155),randint(0,155),randint(0,155))
import turtle
def albero(N):
    if N < 1:
        return
    else:
        turtle.pencolor(randint(0,255),randint(0,255),randint(0,255))
        turtle.forward(N*10)
        turtle.left(30)
        albero(N-1)
        turtle.right(60)
        albero(N-2)
        turtle.left(30)
        turtle.back(N*10)