(Python) Subroutine. ricorsione

Ricorsione

Una procedura o una funzione può contenere una chiamata a un'altra procedura al suo interno. Compreso, la subroutine può chiamare se stessa. In questo caso, al computer non importa. Inoltre, come sempre, esegue costantemente i comandi che ha incontrato dall'alto verso il basso.

Se ricordi la matematica, allora lì puoi incontrare il principio dell'induzione matematica. È il seguente:
qualche affermazione è vera per ogni naturale n if
    1. è valido per n = 1 e
    2. dalla validità dell'affermazione per qualsiasi n = knaturale arbitrario ne consegue che è vera per n = k + 1.

In programmazione, questa tecnica è chiamata ricorsione.
   

Esempio

def Rec(a):
    if (a>0): Rec(a-1)
    stampa(a)

Schematicamente, il lavoro di ricorsione può essere rappresentato da un diagramma di flusso



La procedura Rec() viene eseguita con parametro 3. Quindi, all'interno della procedura con parametro 3, viene chiamata la procedura con parametro 2, e così via, fino a quando viene chiamata la procedura con parametro 0. Quando viene chiamata la procedura con parametro 0, la chiamata ricorsiva non avverrà più e la procedura con parametro 0 stamperà il numero 0 ed uscirà. Poi il controllo viene ritrasferito alla procedura con il parametro 1, anch'essa termina il suo lavoro stampando il numero 1, e così via. prima della procedura con parametro 3. 

Tutte le procedure chiamate vengono archiviate in memoria finché non completano il loro lavoro. Il numero di procedure concorrenti è chiamato profondità di ricorsione.
 

Ricorsione come sostituzione del ciclo

Abbiamo visto che la ricorsione è l'esecuzione ripetuta di istruzioni contenute in una subroutine. E questo, a sua volta, è simile al lavoro del ciclo. Esistono linguaggi di programmazione in cui il costrutto loop è del tutto assente. Ad esempio, Prolog. 
Proviamo a simulare il lavoro del ciclo for. 
Il ciclo for contiene una variabile contapassi. In una subroutine ricorsiva, tale variabile può essere passata come parametro.

# Procedura LoopImitation() con due parametri
# Primo parametro – contapassi, secondo parametro – numero totale di passi
def LoopImitation(i, n):
    print("Ciao N", i) # Istruzione da ripetere per qualsiasi valore di i
    se io < n: # Finché il contatore del ciclo non raggiunge il valore n,
        LoopImitation(i + 1, n) # chiama una nuova istanza della procedura,
                                # con parametro i+1 (vai al valore successivo i)

Ricorsione e iterazione

Iterazione nella programmazione: una fasedi un processo ciclico di elaborazione dei dati. 
Spesso gli algoritmi iterativi nella fase corrente (iterazione) utilizzano il risultato della stessa operazione o azione calcolata nelle fasi precedenti.  Un esempio di tali calcoli è il calcolo delle relazioni di ricorrenza. 
Un semplice esempio di valore ricorsivo è il fattoriale: \(N!=1 \cdot 2 \cdot 3 \cdot \ ... \ \cdot N\).
Il calcolo del valore ad ogni passo (iterazione) è \(N=N \cdot i\) .  Quando calcoliamo il valore di \(N\), prendiamo il valore già memorizzato \(N\).

Il fattoriale di un numero può anche essere descritto usando la formula ricorrente:
\(\begin{equation*} n!= \begin{cases} 1 &\text{n <= 1,}\\ (n-1)! \cdot n &\text{n > 1.} \end{casi} \end{equazione*}\)

Potresti notare che questa descrizione non è altro che una funzione ricorsiva.
Qui la prima riga (\(n <= 1\)) è il caso base (condizione di terminazione della ricorsione) e la seconda riga è la transizione al passaggio successivo.  

Funzione fattoriale ricorsiva	Algoritmo iterativo
def Fattoriale(n): se n > 1: return n * Fattoriale(n - 1) altro:   ritorna 1	x=1 per i nell'intervallo(1, n + 1): x = x * io;

Dovrebbe essere chiaro che le chiamate di funzione comportano un sovraccarico aggiuntivo, quindi un calcolo fattoriale non ricorsivo sarà leggermente più veloce. 

Conclusione: dove puoi scrivere un programma con un semplice algoritmo iterativo, senza ricorsione, allora devi scrivere senza ricorsione. Tuttavia, esiste un'ampia classe di problemi in cui il processo computazionale è implementato solo mediante ricorsione.
D'altra parte, gli algoritmi ricorsivi sono spesso più comprensibili.
 

Attività

Nell'alfabeto della lingua della tribù «Tumba-Yumba» quattro lettere: "K", "L", "M" e "N". È necessario visualizzare sullo schermo tutte le parole composte da n lettere che possono essere costruite dalle lettere di questo alfabeto

Il problema è un normale problema di forza bruta che può essere ridotto a un problema minore.
Sostituiremo in sequenza le lettere per la parola.
La prima posizione di una parola può essere una delle 4 lettere dell'alfabeto (K, L, M, N).
Per prima cosa, metti prima la lettera 'K'. Quindi, per ottenere tutte le varianti con la prima lettera 'K', devi enumerare tutte le possibili combinazioni di lettere nel restante n-1 posizioni e .etc. (Guarda l'immagine)

Così, abbiamo trovato una soluzione ricorsiva: in un ciclo, passa attraverso tutte le possibili prime lettere (mettendo ogni lettera dell'alfabeto a sua volta al primo posto) e per ogni caso costruisci tutte le possibili "code"; lunghezza n-1.
 

Iterazione ricorsiva di caratteri

Devi interrompere la ricorsione e produrre la parola finita quando la parte rimanente è vuota (n = 0), cioè tutte le lettere sono già selezionate. 
La procedura ricorsiva sarebbe simile a questa: 

def TumbaWords(parola, alfabeto, n):
    se n < 1:
        stampa (parola)
        ritorno
    per c in alfabeto:
        TumbaParole(parola+c, alfabeto, n - 1)