Appunti di Fondamenti di informatica - Modulo B

Formattazione del testo

//CON LA CANCELLLAZIONE cancella_contatto(&my_rubrica, "Longo"); //però cancella solo il contatto non tutti i numeri cancella_contatto(&my_rubrica, "Alessi");}

Entro in rubrica.c dove c’è cancella contatto e vedo qual è l’errore, dove o cambio la funzione o faccio un’altra funzione che prima cancella tutti i numeri e poi cancella il contatto:

int cancella_contatto(lista_rubrica* lista, char cognome[]){
    lista_rubrica r = *lista;
    lista_rubrica q = *lista;
    while ((q != NULL) && strcmp(q->cognome, cognome)!=0){
        r = q;
        q = q->next;
    }
    if (q == NULL)
        return 1;
    if (q==*lista)
        (*lista) = (*lista)->next;
    else
        r->next = q->next;
    free(q);
    return 0;
}

Nel caso di condizioni (if, cicli o switch case) che mi dicono che ci sono variabili non inizializzate:

int main(){
    int a;
    int b = a+2;
    printf ("b: %d \n", b);
    if(b>2){
        printf("si");
    }else{
        printf("no");
    }
    42
}

Ci dice che nella riga 11, ovvero quella dell’if

c'è una variabile non inizializzata. Se in questo caso la variabile a la inizializzo:

<pre><code><span class="keyword">int main() {
    int a = 0;
    int b = a + 2;
    printf("b: %d \n", b);
    if (b > 2) {
        printf("si");
    } else {
        printf("no");
    }
}</code></pre>

Gdb è un altro tool, più nello specifico è un debugger, che ci permette di eseguire il programma in un ambiente protetto e fermare il programma ad un certo punto e analizzare la memoria in quel momento. I punti in cui si ferma si chiamano breakpoint.

<pre><code><span class="keyword">#include <stdio.h>

int main() {
    int a = 2;
    int b = 3;
    int c = 5;
    
    if (c < 2) {
        printf("%d", c);
    } else {
        printf("no");
    }
}</code></pre>

Per eseguire il mio programma con gdb basta scrivere: gdb -q ./main

Manda in esecuzione gdb:

<pre><code>run

Esegui il programma:

<pre><code>b 14

Esegui fino alla riga 14:

<pre><code>run

Esegui passo per passo:

<pre><code>step

Inoltre:

<pre><code>p a

Quanto vale la variabile a.

<pre><code>c

Continua fino alla fine.

<pre><code>p c

Quanto vale la variabile c.

<pre><code>whatis c

Di che tipo è c.

<pre><code>set c = 1

Cambiare c in 1.

<pre><code>ricorsione

Oggetti

Un oggetto viene detto ricorsivo se esso comprende parzialmente se stesso, o se è definito in termini di se stesso. La ricorsione è uno strumento particolarmente potente per le definizioni matematiche. Alcuni esempi sono costituiti dai numeri naturali, dalle strutture ad albero e da certe funzioni (ad esempio il calcolo del fattoriale).

Esempio il triangolo di Sierpinski: esso è un oggetto ricorsivo perché anche se lo volessimo descrivere in linguaggio naturale diremmo che è un triangolo formato da 4 triangoli, tre con la punta verso l'alto e uno con la punta verso il basso, di cui ogni triangolo con la punta verso l'alto è suddiviso allo stesso modo. Attraverso l'ultimo pezzo di frase ho la ricorsione che è uno strumento per definire anche insiemi infiniti. In questo caso però non è infinito e termina ad un certo livello di ricorsione, perché, a differenza di quelli infiniti, se zoommo non ho altri.

triangoli nei triangoli.I livelli in questo caso vanno dal primo, ovvero il triangolo grande tutto nero, all'ultimo è il settimo livello del triangolo più piccolo.Quindi abbiamo dei livelli di ricorsione che ci dicono quante volte viene effettuata la ricorsione, ed il livello massimo è il livello nel quale la ricorsione si ferma.Essendo la ricorsione un concetto ripetitivo che non finisce mai, se impongo invece una condizione di terminazione posso decidere quando essa finisce.

Algoritmi ricorsivi

Abbiamo due tipi di algoritmi:

• gli algoritmi iterativi o non ricorsivi sono degli algoritmi che si basano sui blocchi identificati con la programmazione procedurale strutturata che ci permette di avere una sequenza di operazioni, una selezione a una, a due o a n vie, e la possibilità di avere cicli a condizione iniziale e a condizione finale. Questi algoritmi iterativi si basano su cicli;
• gli algoritmi ricorsivi possono, anche non avendo cicli al proprio interno,

Iterare all'infinito. La potenza della ricorsione nasce dalla possibilità di definire un insieme infinito di oggetti con una regola finita. Un insieme infinito di computazioni può, quindi, essere descritto con un programma ricorsivo finito, persino se il programma non contiene iterazioni esplicite.

Gli algoritmi ricorsivi sono appropriati principalmente quando i problemi da risolvere, o le funzioni da calcolare o le strutture dati da elaborare sono già definiti in termini ricorsivi.

Le funzioni del linguaggio C sono lo strumento necessario e sufficiente per esprimere ricorsivamente i programmi, poiché permettono di dare un nome a delle istruzioni che potranno poi essere invocate con quel nome.

Vi sono due tipi di funzioni ricorsive: dirette e indirette:

• È una funzione diretta quando la funzione chiama se stessa;
• Una funzione indiretta o ricorsione mutua si ha quando una prima funzione f richiama una funzione g e la seconda funzione g richiama la funzione f.

La ricorsione è un concetto fondamentale nella programmazione. Consiste nel fatto che una funzione si chiama a se stessa. Si distinguono due tipi di ricorsione: la ricorsione diretta lineare e la ricorsione diretta non lineare.

• La ricorsione diretta lineare si ha quando una funzione si chiama a se stessa una sola volta.
• La ricorsione diretta non lineare si ha quando una funzione si chiama a se stessa più volte.

L'uso della ricorsione potrebbe non essere immediatamente evidente nel testo di un programma. Ad esempio, se consideriamo il seguente programma:

int main(){}

Esso non fa nulla e se lo compili non succede nulla. Ma se lo rendiamo ricorsivo:

int main(){
    main();
}

Succede che si verifica un segmentation fault. Questo accade perché man mano che la funzione main viene richiamata nello stack, si ha un'allocazione di memoria che supera la dimensione assegnata dal sistema operativo per lo stack e il sistema operativo uccide il programma. Questo fenomeno è chiamato stack overflow.

Un altro esempio di funzione ricorsiva è il calcolo del fattoriale. Chiamiamo fattoriale di n e scriviamo n!, che rappresenta il prodotto dei primi n numeri naturali.

ottenuto come segue:!

N → Nn! = 1; per n = 0

n! = 1 * 2 * 3 * ...... * n-1 * n; per n > 0

Rielaborando la definizione, ci si accorge di come sia possibile darne una versione ricorsiva. Sia a tal proposito:

n! = (1 * 2 * 3 * ...... * n-1) * n;

si ottiene: n! = (n-1)! * n

Implementazione iterativa:

int fattoriale_i (int n){
    int fatt=1;
    while(n>0){
        fatt*=n--;
    }
    return fatt;
}

Implementazione ricorsiva:

int fattoriale_r (int n){
    if (n==0)
        //se non impongo una condizione di terminazione essa va all’infinito
        return 1;
    else
        return n*fattoriale_r(n-1);
}

E’ possibile estendere la definizione ai numeri interi come segue:

n!: Z → N

n! = 1 se n ≤ 0

n! = n*(n-1)! se n > 0

Implementazione ricorsiva in linguaggio C:

int fact(int n) {
    if (n<=0)
        return 1;
    else
        return n*fact(n-1);
}

La nuova istanza lega il parametro. Analogamente, fact(2) effettua n-1. La condizione n <= 0 è vera e una nuova chiamata di funzione. La funzione fact(0) torna come risultato 1.

Esecuzione: n-1

nell'environnement di fact(2) risultato 1 e termina

int fact(int n) {

if (n<=0) {

return 1;

} else {

return n*fact(n-1);

}

}

Il controllo torna all'istanza precedente fact(1) che può

valutare l'espressione che costituisce il parametro

main() {

int fz,z = 5;

fz = fact(z-2);

// ottenendo come risultato 1 e

// terminando.

}

fact(3) effettuerà poi analogamente una nuova

chiamata di funzione fact(2). fact(3)

Il controllo passa infine al main che assegna a fz il

valore 6.

Environment delle funzioni ricorsive

È pratica comune associare ad una funzione un insieme di oggetti locali, cioè variabili, costanti, ecc.., che sono definiti localmente e non esistono né hanno significato al di fuori di essa.

Ogni volta che la