Dano je Fibonacijevo zaporedje. Njegova definicija je:
za
Zapiši rekurzivno funkcijo, ki za podano naravno število vrne -ti člen Fibonaccijevega zaporedja.
Zapiši tudi funkcijo brez rekurzije.
Zaporedje
Zaporedje
Karmen Pekro
Zapisati rekurzivno funkcijo.
Naloga
Razmišljanje
Rešitev z rekurzijo je precej enostavna, saj moramo le definicijo zaporedja pretvoriti v programski jezik.
Za rešite brez rekurzije pa potrebujemo nekaj več dela. Tu si bomo pomagali s seznamom. Vanj si bomo shranjevali posamezne člene zaporedja.
V seznam si najprej shranimo prva dav člena zaporedja, ki sta oba enaka . Za člene od naprej pa do vključno -tega bomo v seznam dodajali nove člene, ki jih bomo izračunali s pomočjo dveh predhodnih po enačbi . Seznamu bomo nove člene preprosto pripeli na konec. Ko bimo pripeli na seznam člen za dani n, bomo kot zadnji člen dobili rešitev naše naloge.
Koda
REKURZIVNA KODA
def fibinacci(n):
'''Rekurzivna koda'''
for n==1 or n==2:
return 1
else:
return fibomacci(n-1) + fibonacci(n-2) #rekurzivni korak
'''Rekurzivna koda'''
for n==1 or n==2:
return 1
else:
return fibomacci(n-1) + fibonacci(n-2) #rekurzivni korak
NE REKURZIVNA KODA
def fibonacci(n):
'''Nerekurzivna funkcija'''
if n==1 or n==2:
return 1
cleni = [1,1]
for i in range(2,n): #Seznam členov Fibonaccijevega zaporedja
noviClen = cleni[i-1] + cleni[i-2]
cleni.append(noviClen)
return noviClen
'''Nerekurzivna funkcija'''
if n==1 or n==2:
return 1
cleni = [1,1]
for i in range(2,n): #Seznam členov Fibonaccijevega zaporedja
noviClen = cleni[i-1] + cleni[i-2]
cleni.append(noviClen)
return noviClen
