Fork me on GitHub

Differenza fra funzione iterativa e funzione ricursiva in python...

In una funzione che implementa un algoritmo iterativo verranno eseguite ripetutamente delle operazioni fin tanto che si verificano determinate condizioni.

Nei linguaggi di programmazione vengono forniti diverse strutture di controllo per eseguire questi cicli (loop) quali ad esempio while, for, if, etc...

Esempio nr.1

Riporto qui sotto il classico esempio del calcolo del numero fattoriale utilizzando una funzione iterativa:

# Definizione di una funzione di fattorializzazione iterativa.
# Restituisce il fattoriale dell'argomento dato "number".
# La variabile "number" esiste esclusivamente(!) all'interno 
# della funzione e non puo' essere richiamata fuori di essa
def factorial(number):
    product = 1    
    for i in range(number):
        product = product*(i+1)  
        # alla fine del loop la variabile product conterra' il fattoriale del numero fornito    return product
        # Valida per python 3
        user_imput = eval(input("Immetti un valore numerico non negativo per ottenere il fattore:"))
        # Valida per python 2
        #user_imput = input("Immetti un valore numerico non negativo per ottenere il fattore:")
        factorial_of_user_imput = factorial(user_imput)print ("La fattorializzazione di:")
        print (user_imput)
        print ("e':")
        print (factorial_of_user_imput)

Una funzione che implementa un algoritmo ricorsivo permette di risparmiare righe di codice, variabili temporanee, a scapito della memoria (overhead) e delle prestazioni. Il tipico campo d'applicazione è all'interno di funzioni.

L'algoritmo ricorsivo richiama se stesso operando una riduzione dei dati originari, sui quali poi applica ancora ed ancora l'algoritmo stesso fino a giungere ad una condizione di terminazione o caso base.

E' possibile implementare le funzioni ricorsive in python in questo modo:

# Definizione della funzione di fattorializzazione ricorsiva.
# Restituisce il fattoriale dell'argomento dato "number".
# In questo tipo di funzione, la funzione richiama se stessa
# operando la riduzione sui dati fino al "caso base"
def factorial(number):
    if number <=1:
        # caso base o condizione di terminazione
        return 1
    else:
        return number*factorial(number-1)
    # Valida per python 3
    user_imput = eval(input("Immetti un valore numerico non negativo per ottenere il fattore:"))
    # Valida per python 2
    #user_imput = input("Immetti un valore numerico non negativo per ottenere il fattore:")
    factorial_of_user_imput = factorial(user_imput)
    print ("La fattorializzazione di:")
    print (user_imput)
    print ("e':")
    print (factorial_of_user_imput)

Esempio nr.2

In questo secondo esempio si implementa un algoritmo per determinare il valore di un elemento della sequenza di Fibonacci.

La sequenza di Fibonacci è una serie di numeri a partire da 0 ed 1 in cui l'elemento successivo è determinato dalla somma dei due elementi precedenti.

Ad esempio, se abbiamo 0 ed 1 come elementi 0 ed 1 della nostra lista python, il secondo elemento della lista sarà 0+1 quindi 1, il terzo elemento della lista sarà 1+1 quindi 2, il quarto sarà 2+1 quindi 3 e così via con una sequenza simile alla seguente:

[0,1,1,2,3,5,8,13,21,34,55,89,...]

La funzione implementata, ci consente di conoscere il valore di un elemento della sequenza di Fibonacci fornito da un imput dell'utente.

Funzione fibonacci iterativa:

def fib(n):
    # Definisco i primi 2 termini della serie di Fibonacci
    terms = [0,1]
    # "i" a 2 per entrare nel loop valutando il 3 elemento della lista
    # ricordiamoci che il primo elemento di una lista python è sempre l'elemento 0...
    i = 2
    while i <=n:
        # Utilizziamo la funzione interna di python "append" per aggiungere i valori
        # calcolati alla lista terms fino a raggiungere l'elemento n richiesto
        # dall'imput dell'utente.
        # Nella parte fra parentesi calcoliamo il valore del termine successivo a
        # rispetto agli ultimi due elementi della lista in elaborazione nel ciclo while.
        # i-1 è l'ultimo elemento, i-2 è il penultimo elemento.
        terms.append(terms[i-1]+terms[i-2])
        # Incremento i e ricomincio il ciclo, per arrivare fino a n e fermarmi
        i = i + 1
        return terms[n]
    # Valida per python 3
    user_imput = eval(input("Termine:"))
    # Valida per python 2
    #user_imput = input("Termine:")
    eval_n = fib(user_imput)
    print(eval_n)

Implementiamo ora lo stesso algoritmo utilizzando una funzione ricorsiva:

def fib(n):
    if n<2:
        # caso base o condizione di terminazione
        return n
    # restituisce 1 o 0
    else:
        # Richiamo la funzione di Fibonacci per il penultimo e l'ultimo elemento
        # che poi sommo, per ottenere i valore richiesto
        return (fib(n-1)+fib(n-2))
    # Valida per python 3
    user_imput = eval(input("Termine:"))
    # Valida per python 2
    #user_imput = input("Termine:")
    eval_n = fib(user_imput)
    print(eval_n)

Vediamo cosa succede nella funzione ricorsiva quando decidiamo di voler conoscere il valore del quarto elemento della serie di Fibonacci, con la seguente:

Caso per n = 4

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

sostituendo e semplificando si avrà:

return (fib(n=4-1)+fib(n=4-2))return (((fib(n=3-1)+fib(n=3-2))+(fib(n=2-1)+fib(n=2-2)))return (((fib(n=2-1)+fib(n=2-2))+(fib(n=2-1)+fib(n=2-2))+(1+0))return (((1+0)+(1+0))+(1+0)))return (1+1+1)return (3)

Caso per n = 5

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

sostituendo e semplificando si avrà:

return (fib(n=5-1)+fib(n=5-2))return ((fib(n=4-1)+fib(n=4-2))+(fib(n=3-1)+fib(n=3-2))return (((fib(n=3-1)+fib(n=3-2))+(fib(n=2-1)+fib(n=2-2)))+((fib(n=2-1)+fib(n=2-2))+(1)))return (((fib(n=2-1)+fib(n=2-2))+(fib(n=2-1)+fib(n=2-2))+(1+0))+((1+0)+1))return (((1+0)+(1+0))+1)+(1+1))return ((1+1+1)+(1+1))return (3+2)return (5)

Commenti !

blogroll

social