# Ricorsione e Ricerca

## Esercizio 01: 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);
    }
}

---

## Esercizio 02: 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);
    }
}

---

## Esercizio 03: 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);
    }
}

---

## Esercizio 04 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);
    }
}

---

## Esercizio 05: 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];
    }
}

---

## Esercizio 06: 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);
    }
}

---