# Ricorsione e Ordinamento

# Stampa numeri

Si scriva una funzione ricorsiva che prende in input un intero positivo n e che stampi tutti i numeri interi da 1 a n.

// Librerie
#include <stdio.h>

// Prototipi
void f(int);

// Main
int main(){
    // definisco il numero
    int n = 10;
    
    // chiamo la funzione ricorsiva
    f(n);

    return 0;
}

// Funzioni
void f(int n){
    // Finché n è più grande di 1, chiamo la funzione con il numero precedente
    if(n > 1){
        f(n-1);
    }
    // Quando la funzione termina stampo il numero
    printf("%d\n", n);
}

Si scriva una funzione ricorsiva che prende in input un intero positivo n e che stampi tutti i numeri interi da n a 1.

// Librerie
#include <stdio.h>

// Prototipi
void f(int);

// Main
int main(){
    // definisco il numero
    int n = 10;
    
    // chiamo la funzione ricorsiva
    f(n);

    return 0;
}

// Funzioni
void f(int n){
    // Prima di chiamare se stessa la funzione stampa il numero
    printf("%d\n", n);

    // Finché n è più grande di 1, chiamo la funzione con il numero precedente
    if(n > 1){
        f(n-1);
    }
}

---

# Potenze

Si scriva una funzione ricorsiva “potenza” che prende in input un numero base e un numero esponente e restituisce la base elevata all’esponente.

==Suggerimento==
Il caso base si ha per $e = 0$, dove $b^{0}=1$.
Altrimenti, si sfrutti la proprietà $b^e = b \cdot b^{e-1}$.

// Librerie
#include <stdio.h>

// Prototipi
int potenza(int, int);

// Main
int main(){
    // Variabili
    int base = 2, esponente = 2, res;
    
    // calcolo potenza
    res = potenza(base, esponente);

    printf("%d^%d = %d\n", base, esponente, res);

    return 0;
}

// Funzioni
int potenza(int base, int esponente){
    // Caso base
    if(esponente == 0){
        return 1;
    }
    else{
        return base * potenza(base, esponente - 1);
    }
}

---

# Conversione in Binario

Si scriva un funzione ricorsiva per la conversione di un numero n in binario. La funzione deve restituire un intero che sembra la rappresentazione in binario del numero.

**Esempi:** $(6)_{10} = (110)_{2}$, $(7)_{10} = (111)_{2}$.

==Suggerimento==
Si pensi all'algoritmo visto a lezione. Quando $\frac{n}{2} = 0$ allora siamo arrivati alla fine e bisogna restituire `n%2`. Si ricordi che ad ogni step, il prossimo ci darà la cifra più significativa.

// Librerie
#include <stdio.h>

// Prototipi
int converti(int);

// Main
int main(){
    int n = 6;
    int res = converti(n);
    printf("%d -> %d\n", n, res);
    return 0;
}

// Funzioni
int converti(int n){
    // Caso base
    if(n/2 == 0){
        return n % 2;
    }
    else{
        return n % 2 + 10 * converti(n/2);
    }
}

---

# Triangolo di Tartaglia

Scrivere una funzione che stampi il triangolo di tartaglia dato un numero intero N.

Si utilizzi una funzione ricorsiva per il calcolo dei coefficienti del triangolo.

**Esempio**

==Suggerimento==
Ogni elemento del tringolo di tartaglia in posizione n (riga), k (colonna) è il coefficiente binomiale $\binom{n}{k} = \frac{n!}{k! (n-k)!}$. Si noti che $\binom{n}{0} = \binom{n}{n} = 1$ dato che per convenzione $0! = 1$. Si ricordi la proprietà $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$.

// Librerie
#include <stdio.h>

// Prototipi
int binom(int, int);

// Main
int main(){
    int N = 10;
    for(int n = 0; n <= N; n++){
        for(int k = 0; k <= n; k++){
            printf("%d\t", binom(n, k));
        }
        printf("\n");
    }
    return 0;
}

// Funzioni
int binom(int n, int k){
    // coefficiente binomiale 
    if(n  == k || k == 0){
        return 1;
    }
    else{
        return binom(n-1, k) + binom(n-1, k-1);
    }
}

---

# Inverti Stringa

Si scriva una funzione ricorsiva in grado di invertire una stringa data in ingresso.

## Versione 1

// Librerie
#include <stdio.h>
#include <string.h>

// Macro
#define LEN 100

// Prototipi
void wrapper(char [], char[]);
void invertiStringa(char [], char [], int);

// Main
int main(){
    char src[LEN] = "ciao mamma!", dest[LEN]; 

    wrapper(src, dest);

    printf("Stringa originale: %s\n", src);
    printf("Stringa invertita: %s\n", dest);

    return 0;
}

// Funzioni
void wrapper(char src [], char dest []){
    invertiStringa(src, dest, strlen(src)-1);
    dest[strlen(src)] = '\0';
}

void invertiStringa(char src[], char dest[], int pos){
    if(src[0] != '\0'){
        // stringa sorgente non è finita
        // copio nelle attuali celle di memoria
        dest[pos] = src[0];
        // chiamo ricorsivamente cambiando i contatori
        invertiStringa(src+1, dest, pos - 1);
    }
}

## Versione 2

// Librerie
#include <stdio.h>
#include <string.h>

// Macro
#define LEN 100

// Prototipi
void invertiStringa(char [], char [], int);

// Main
int main(){
    char src[LEN] = "ciao mamma!", dest[LEN]; 
    int len = 0;

    invertiStringa(src, dest+strlen(src)-1, strlen(src));

    printf("Stringa originale: %s\n", src);
    printf("Stringa invertita: %s\n", dest);

    return 0;
}

// Funzioni
void invertiStringa(char src[], char dest[], int og_len){
    if(src[0] != '\0'){
        // stringa sorgente non è finita
        // copio nelle attuali celle di memoria
        dest[0] = src[0];
        // chiamo ricorsivamente cambiando i contatori
        invertiStringa(src+1, dest-1, og_len);
    }
    else{
        // dest sarà una cella prima dell'inizio e devo puntare alla fine
        dest[og_len+1] = src[0];
    }
}

## Versione 3

// Librerie
#include <stdio.h>
#include <string.h>

// Macro
#define LEN 100

// Prototipi
void invertiStringa(char [], char [], int*);

// Main
int main(){
    char src[LEN] = "ciao mamma!", dest[LEN]; 
    int len = 0;

    invertiStringa(src, dest+strlen(src)-1, &len);

    printf("Stringa originale: %s\n", src);
    printf("Stringa invertita: %s\n", dest);

    return 0;
}

// Funzioni
void invertiStringa(char src[], char dest[], int * og_len){
    if(src[0] != '\0'){
        // stringa sorgente non è finita
        // copio nelle attuali celle di memoria
        dest[0] = src[0];
        // incremento il counter di lettere copiate
        (*og_len) = (*og_len) + 1;
        // chiamo ricorsivamente cambiando i contatori
        invertiStringa(src+1, dest-1, og_len);
    }
    else{
        // dest sarà una cella prima dell'inizio e devo puntare alla fine
        dest[*og_len+1] = src[0];
    }
}

---

# Ricerca Binaria

Scrivere un programma che effettua una ricerca binaria tramite una funzione ricorsiva su un array ordinato.

// Librerie
#include <stdio.h>

#define N 5

// Prototipi
int ricercaBinaria(int[], int, int, int);

// Main
int main(){
    int v[N] = {1,3,5,7,9};
    int n = 7;
    if(!ricercaBinaria(v, 0, N-1, n)){
        printf("Non ");
    }
    printf("Trovato\n");
    return 0;
}

// Funzioni
int ricercaBinaria(int v[], int start, int end, int n){
    if(start > end){
        return 0;
    }
    else{
        int m = (start+end)/2;
        if(v[m] == n) return 1;
        else if(v[m] < n) return ricercaBinaria(v, m+1, end, n);
        else return ricercaBinaria(v, start, m-1, n);
    }
}

---

# Ordinamento

Si scrivano le funzioni iterative per implementare selection sort e bubble sort per ordinare un array di interi.

Si scriva la funzione ricorsiva merge sort per ordinare un array di interi

// Librerie
#include <stdio.h>

#define N 10

// Prototipi
void stampaArray(int[], int);
void selectionSort(int[], int);
void bubbleSort(int[], int);
void mergeSort(int[], int, int);
void merge(int[], int, int, int);
void copiaArray(int[], int[], int);

// Main
int main(){
    int v[N] = {2,4,1,6,5,9,5,10,4,2};
    int t[N];

    printf("Array: ");
    stampaArray(v, N);

    printf("Selection Sort: ");
    copiaArray(v, t, N);
    selectionSort(t, N);
    stampaArray(t, N);

    printf("Bubble Sort: ");
    copiaArray(v, t, N);
    bubbleSort(t, N);
    stampaArray(t, N);

    printf("Merge Sort: ");
    copiaArray(v, t, N);
    mergeSort(t, 0, N-1);
    stampaArray(t, N);

    return 0;
}

// Funzioni
void selectionSort(int v[], int dim){
    for(int i = 0; i < dim; i++){
        for(int j = i + 1; j < dim; j++){
            if(v[i] > v[j]){
                int tmp = v[j];
                v[j] = v[i];
                v[i] = tmp;
            }
        }
    }
}

void bubbleSort(int v[], int dim){
    int i, j, n_swap,tmp;
    for(i = 0; i < dim - 1; i++){
        n_swap = 0;
        for(j = 0; j < dim - i - 1; j++){
            if(v[j] > v[j+1]){
                tmp = v[j];
                v[j] = v[j+1];
                v[j+1] = tmp;
                n_swap++;
            }
        }
        if(n_swap == 0) break;
    }
}

void mergeSort(int v[], int start, int end){
    int mid;
    if(start < end){
        mid = (start + end)/2;
        mergeSort(v, start, mid);
        mergeSort(v, mid + 1, end);
        merge(v, start, end, mid);
    }
}

void merge(int v[], int start, int end, int mid){
    int i=start, j=mid+1, k=start, copy[N];
    // faccio il merge fino alla fine di una delle due porzioni
    while((i <= mid) && (j <= end)){
        if(v[i] > v[j]){
            copy[k] = v[j];
            j++;
        }
        else{
            copy[k] = v[i];
            i++;
        }
        k++;
    }
    // finisco la copia della prima porzione (se necessario)
    while(i <= mid){
        copy[k] = v[i];
        k++;
        i++;
    }
    // OPPURE finisco la copia della seconda porzione (se necessario)
    while(j <= end){
        copy[k] = v[j];
        k++;
        j++;
    }
    // copio "copy" nell'array di partenza, ma solo nella porzione interessata
    for(i=start; i <= end; i++){
        v[i] = copy[i];
    }
}

void stampaArray(int v[], int dim){
    printf("[");
    for(int i = 0; i<dim; i++) printf("%d,", v[i]);
    printf("]\n");
}

void copiaArray(int src[], int dest[], int dim){
    for(int i = 0; i < dim; i++){
        dest[i] = src[i];
    }
}