Calcolo ricorsivo della sequenza di Fibonacci (Python)

La sequenza di fibonacci è una delle sequenze più famose al mondo. Proviamo a calcolarla in modo ricorsivo.

 

Logica

numero_successivo = numero_precedente1 + numero_precedente2

Ora quindi dobbiamo mettere questa operazione in un ciclo. In una condizione tradizionale senza adottare alcun tipo di ricorsione la nostra funzione assomiglierebbe a questo (faccio esempio con php ma si può facilmente trasportare in altri linguaggi):

Markup di esempio senza ricorsione


<?php function fibonacci($limite=10){ 
   $a= 1; $b= 1; 
   while($limite>0){
      //mostro la somma di $a + $b
      //memorizzo una terza variabile per ricordare i due numeri precedenti
      $limite = $limite - 1;
   }
} 

Ricorsivamente invece…


<?php function fibonacci_ricorsivo($a=1,$b=1,$limite=10){ 
   echo $b;
   if($limite>0) return fibonacci_ricorsivo($b,$b+$a,$limite-1);
} 

In python quindi:

NB ho aggiunto un po’ l’interfaccia per arricchire la cosa, non spaventatevi dalle righe di codice 😀

 

import time
from subprocess import call
def is_int_number(num):
    return num.strip().lstrip('-+').isdigit() and num.count('-') + num.count('+') <= 1 

def fibonacci(one=1,two=1,limit=10): 
        #sum two previous numbers 
        time.sleep(0.1) 
        print two 
        newone = two 
        two = two + one 
        if(limit > 0):
		limit = limit - 1
		return fibonacci(newone,two,limit)
	else:
		exit()
def fibonacci_ask():
	print "How many number want me to calc?"
	l = raw_input()
	limit = int(l)
	print "Want me to start from 1 on counting?(y/give me a number)"
	s = raw_input()
	if(is_int_number(s)):
		s = s
	else:	
		s = 1
	startfrom = int(s)
	if(limit > 1):
		print "Oh right!"
		time.sleep(0.5)
		call("clear")
		print "Here are the ",l," fibonacci number starting from",startfrom,":"
		fibonacci(startfrom,1,limit)
	else:
		print "hmm... please retry"
		time.sleep(2)
		fibonacci_ask()	
	return ""
def start(asking_again=0):
	
	if(asking_again==1):
		print ":( why not?"
		time.sleep(1)
		print "and now? (y/n)"
	else:
		call("clear")
		print "Hi there!!"
		time.sleep(1)
		print "I am gonna calc some fibonacci numbers for you!"
		time.sleep(2.5)
		print "are you ready? (y/n)"
	ready = raw_input()
	if(ready=="y"):
		fibonacci_ask()
	else:	
		start(1)

#program start
start()

NB: per calcoli con grandi numeri è consigliato utilizzare long() al posto di int()

Ed infine eccolo qui in azione!

By | 2017-04-23T18:12:44+00:00 aprile 23rd, 2017|Categories: Codice, Come fare per|1 Comment

About the Author: