Qual è la relazione tra ricorsione e prova per induzione?

Question

Qual è la relazione tra ricorsione e prova per induzione?

Diciamo fn(n),

ricorsione è fn(n) chiama se stessa, fino incontrano base condition;

l'induzione è quando base condition è soddisfano, provare a provare (base case + 1) è anche corretto.

Sembra ricorsione e induzione sono in direzione diversa. Uno inizia da n a base case, l'altro è a partire da base case a infinite.

Qualcuno potrebbe spiegare l'idea in dettaglio?

Answer 1

La ricorsione e l'induzione sono praticamente la stessa cosa! Questo diventa ovvio se si utilizza un linguaggio di programmazione con tipi dipendenti, come Agda, ma può essere dimostrato in una certa misura anche senza di essi.

Ricordare che a causa dello Curry-Howard correspondence, i tipi sono proposizioni e i programmi sono prove. Quando scrivi una funzione di tipo Nat -> Nat (userò la notazione Haskell), stai provando a dimostrare che, dato un numero naturale, il tuo programma terminerà e produrrà un altro numero naturale. Ora possiamo avere una definizione come questa:

f 0 = 1 
f (1 + n) = n * f n 

che è sia una definizione ricorsiva di f e una prova induttiva della sua cessazione, allo stesso tempo!

si può leggere come una prova in un modo che segue:

Diamo dimostrare che f x termina per ogni x.

• caso base: abbiamo f 0 costante per definizione, quindi termina.
• Caso induttivo: se assumiamo f n termini, anche f (1 + n) termina (perché tutte le funzioni che chiama terminano).

Si noti che, poiché la ricorsione non è limitata a una funzione che decrementa il suo contatore, l'induzione non è limitata ai numeri naturali. Esiste anche induzione strutturale, corrispondente alla ricorsione strutturale, entrambe molto apprezzate in matematica/programmazione. Questi devono essere usati quando si tenta di provare cose/definire funzioni su strutture dati più complesse (liste/alberi/ecc.).

Ora, per rispondere alle vostre preoccupazioni sulla "direzione" della ricorsione/induzione. È utile considerare qui "direzione della domanda" e "direzione dell'offerta", che sono opposti.

Quando si definisce la funzione ricorsiva, la richiesta (metodo chiamate) passa da valori più grandi a caso base. D'altra parte, l'offerta (i valori di ritorno) passa dal caso base ai valori più grandi del parametro. la "definizione" è un altro modo per pensare all'offerta. Inizia dal caso base e si propaga all'infinito tramite il caso ricorsivo.

Ora, quando si stanno facendo prove induttive, i teoremi sono la vostra fornitura mentre gli obiettivi sono la vostra richiesta.Puoi fare un teorema T 0 fuori dal caso base e poi migliorare a T n grande come per il caso induttivo: la tua scorta scorre da 0 a infinito. Ora se hai un obiettivo G n, puoi fare un obiettivo più piccolo G (n-k) fuori usando il passo induttivo fino a raggiungere lo zero. In questo modo la tua richiesta passa da n a 0.

Come si può vedere, la direzione di alimentazione è "a infinito" in entrambi i casi e la direzione della domanda è "a zero" in entrambi i casi.

È anche possibile invertire l'ordine apparente nelle descrizioni di induzione e ricorsione senza modificarne la sostanza:

induzione è quando per dimostrare che P n detiene è necessario ridurre prima il vostro obiettivo di P 0 ripetutamente applicando il caso induttivo e quindi dimostrare l'obiettivo risultante utilizzando il caso base.

Analogamente, la ricorsione è quando si definisce per la prima volta un caso base e poi si definiscono gli ulteriori valori in termini di quelli precedenti. Vedi, le direzioni sono facilmente scambiate!