Programmazione:
Circoli viziosi ovvero
Un’eterna ghirlanda brillante
Eugenio Omodeo
Trieste, 29.03.2021
Programmazione:
Circoli viziosi ovvero
Un’eterna ghirlanda brillante
Eugenio Omodeo
Trieste, 29.03.2021
Bello o conturbante ?
Il paradosso del mentitore ( Epimenide di Creta, 600 a.C. )
Lettera di San Paolo a Tito I, 12-13:
“[11]A questi tali bisogna chiudere la bocca, perch´e mettono in scompiglio intere famiglie, insegnando per amore di un guadagno disonesto cose che non si devono insegnare. [12]Uno dei loro, proprio un loro profeta, gi`a aveva detto: I Cretesi son sempre bugiardi, male bestie, ventri pigri. [13]Questa testimonianza `e vera. Perci`o correggili con fermezza,”
Il paradosso del mentitore ( Epimenide di Creta, 600 a.C. )
Lettera di San Paolo a Tito I, 12-13:
“[11]A questi tali bisogna chiudere la bocca, perch´e mettono in scompiglio intere famiglie, insegnando per amore di un guadagno disonesto cose che non si devono insegnare. [12]Uno dei loro, proprio un loro profeta, gi`a aveva detto: I Cretesi son sempre bugiardi, male bestie, ventri pigri. [13]Questa testimonianza `e vera.
Perci`o correggili con fermezza,”
Test ricorsivo di palindromicit` a
1in Java
private
public static boolean palindroma( String s ) { return s.length() 6 1 ||
s.charAt( 0 ) == s.charAt( s.length() - 1 ) &&
palindroma( s.substring( 1, s.length() - 1 ) ) ;
}
La stringa vuota e le stringhe di lunghezza 1 sono il caso base. Se una stringa non `e vuota, richiediamo che abbia il primo carattere uguale all’ultimo e che, mutilata di questi due caratteri, rimanga palindroma.
1Esempi: “narici di Ciran”, “Avevi visioni d’un evo dove nudi noi si viveva”.
Test ricorsivo di palindromicit` a
1in Java
private
public static boolean palindroma( String s ) { return s.length() 6 1 ||
s.charAt( 0 ) == s.charAt( s.length() - 1 ) &&
palindroma( s.substring( 1, s.length() - 1 ) ) ;
}
La stringa vuota e le stringhe di lunghezza 1 sono il caso base. Se una stringa non `e vuota, richiediamo che abbia il primo carattere uguale all’ultimo e che, mutilata di questi due caratteri, rimanga palindroma.
1Esempi: “narici di Ciran”, “Avevi visioni d’un evo dove nudi noi si viveva”.
Ricorsione mutua ( Es. istruzioni / espressioni )
Ricorsione mutua, in Java
public static boolean pari( int p ) { assert p > 0;
return p == 0 || dispari( p - 1 );
}
public static boolean dispari( int d ) { assert d > 0;
return d != 0 && pari( d - 1 );
}
( Anche questi metodi andrebbero ‘privatizzati’ )
Simulazione del test ricorsivo di disparit` a
L’esecuzione di
System.out.println( dispari( 2 ) );
‘scatena’ le invocazioni I dispari( 2 ) I pari( 1 ) I dispari( 0 )
che forniscono (da sotto in su) i risultati I false
I false
I false( questo verr`a stampato a video )
Simulazione del test ricorsivo di parit` a
L’esecuzione di
System.out.println( pari( 2 ) );
‘scatena’ le invocazioni I pari( 2 ) I dispari( 1 ) I pari( 0 )
che forniscono (da sotto in su) i risultati I true
I true
I true ( questo verr`a stampato a video )
Due esercizi sulla ricorsione
I Implementate in modo ricorsivo il confronto lessicografico fra stringhe.
I Implementate come metodo ricorsivo che abbia il suo caso base nei numeri primi la scomposizione dei numeri interi nonnegativi come somme di quattro quadrati.
Un esempietto liberamente riadattato da Peano
public static long fatt( int n ){
return ( n == 0 ) ? 1 : n * fatt( n - 1 );
}
Queste definizioni rigorose sono adottate nei trattati sco- lastici del prof. Catania.
(Giuseppe Peano, “Le definizioni in matematica”, 1921)
Esempietto analogo: numeri di Fibonacci ( 1170–1240 ca. )
E poi i numeri del triangolo di Tartaglia ( 1499 ca.–1557 )
E poi i numeri del triangolo di Tartaglia ( 1499 ca.–1557 )
Il coefficiente binomiale nk esprime in quanti modi posso prelevare k elementi da un insieme di n elementi.
E poi i numeri del triangolo di Tartaglia ( 1499 ca.–1557 )
Il coefficiente binomiale nk esprime in quanti modi posso prelevare k elementi da un insieme di n elementi.