definizione ricorsiva di una funzione per il calcolo del fattoriale:

• int fattoriale(int N)
  { if ( N == 0 ) return 1; return N*fattoriale(N-1); } 
  

definizione ricorsiva, ma non induttiva, di una funzione per il problema di Collatz:

• int collatz(int N)
  { if ( N == 1 ) return 1; 
    if ( N%2 == 0 ) return collatz(N/2); return collatz((3*N+1)/2); }
  

  • N.B. si congettura che questa funzione restituisca 1 per qualsiasi valore dell'argomento ...

per la definizione precedente, definiamo una funzione che ne misuri la profondità della ricorsione:

• int cd(int N, int& d)
  { if ( N == 1 ) return d;
    d++; if ( N%2 == 0 ) return cd(N/2, d); return cd((3*N+1)/2, d); }
  int collatzd(int N) { int d = 1, return cd(N, d); }
  

algoritmo di Euclide per il calcolo del massimo comun divisore di due numeri:

• int gcd(int m, int n) { if ( n == 0 ) return m; return gcd(n, m%n); }
  

si ha ricorsione in coda (ingl. tail recursion) quando un'invocazione ricorsiva è presente nell'ultima istruzione di una definizione ricorsiva di funzione

• la ricorsione in coda è facilmente eliminabile mediante l'iterazione

tre delle seguenti definizioni sono ricorsive in coda, mentre non lo è la definizione di traverseR, per l'attraversamento in ordine inverso di una lista concatenata

• int count(nlink x)
  { if (x == 0) return 0; return 1 + count(x->next); }
  

• void traverse(nlink h, void visit(nlink))
  { if (h == 0) return; visit(h); traverse(h->next, visit); }  
  

• void traverseR(nlink h, void visit(nlink))
  { if (h == 0) return; traverseR(h->next, visit); visit(h); }
  

• void remove(nlink& x, Elem e)
  { while (x != 0 && x->elem == e)
    { nlink t = x; x = x->next; delete t; }
    if (x != 0) remove(x->next, e); }
  

si è già invocata la regola divide et impera, per caratterizzare una vasta classe di algoritmi, quando si sono introdotte le relazioni di ricorrenza

appare ora chiaro che gli algoritmi di questa classe hanno definizioni ricorsive basate sull'induzione

per questi algoritmi, la struttura ricorsiva del programma fornisce lo schema essenziale

• sia per una dimostrazione induttiva di correttezza
• sia per una valutazione analitica delle prestazioni

riguardo al secondo aspetto, si dimostrano spesso per induzione proprietà di sottoclassi di algoritmi divide et impera

eccone una, a titolo di esempio:

• una funzione ricorsiva che, quando l'input ha dimensione N > 2, lo divide in due parti indipendenti non vuote e si invoca ricorsivamente su ciascuna di esse, ha profondità di ricorsione minore di N

l'approccio divide et impera fornisce spesso una soluzione rapida al problema, in termini di tempo necessario a trovarla e/o codificarla

ecco ad esempio una soluzione divide et impera al problema di trovare il massimo in un insieme di elementi

• gli elementi sono memorizzati in un array, e si assume che siano di un tipo di prima categoria su cui sia definito l'operatore booleano >

• Elem max(Elem a[], int l, int r)
  { if (l == r) return a[l];
    int m = (l+r)/2;
    Elem u = max(a, l, m);
    Elem v = max(a, m+1, r);
    if (u > v) return u; else return v; }
  

per il risultato enunciato in precedenza, questo algoritmo ha profondità di ricorsione inferiore al numero N di elementi nell'array

l'analisi dell'algoritmo permette una valutazione più accurata della profondità di ricorsione, che è all'incirca lg N

1. dare definizioni non ricorsive delle funzioni collatz e gcd equivalenti alle rispettive definizioni ricorsive qui proposte
2. v. esercizio 5.1 del testo (Sedgewick, 2003), a p. 208: dare una definizione ricorsiva della funzione lg(N!) che riesca a produrre il risultato anche per valori di N abbastanza grandi da rendere N! non rappresentabile
3. v. esercizio 5.2 del testo (Sedgewick, 2003), a p. 208: dare una definizione ricorsiva della funzione N! mod M che produca il risultato per qualsiasi valore rappresentabile di N, dunque anche per valori abbastanza grandi da rendere N! non rappresentabile
4. la Proprietà 5.1 nel testo (Sedgewick, 2003), a p. 212, recita: una funzione ricorsiva che divide un problema di dimensione N in due parti indipendenti (non vuote) che risolve in modo ricorsivo, invoca se stessa per meno di N volte; verificare che tale formulazione è erronea
   • la dimostrazione per induzione fornita dal testo è basata sulla seguente ricorrenza, dove T_N è il numero totale di chiamate ricorsive su un input di dimensione N, e si ipotizza che le due parti abbiano rispettivamente dimensione k e N-k: trovare in questa ricorrenza la fonte dell'errore nel testo
     • T_N = T_k + T_N-k + 1, per N > 1, dove T₁ = 0