Convertire un Intero in una Stringa in una qualsiasi Base usando la Ricorsione¶

Supponiamo di voler convertire un intero in una stringa in qualche base tra binaria e esadecimale. Per esempio, convertiamo l’intero 10 nella rappresentazione di tipo stringa decimale "10", oppure nella sua rappresentazione binaria "1010". Un approccio per effettuare la conversione può essere ricorsivo.

Consideriamo il numero 769 in base 10. Supponiamo che abbiamo una sequenza di caratteri corrispondenti alle prime 10 cifre, del tipo convString = "0123456789". E’ facile convertire un numero minore di 10 nella stringa equivalente controllando la sequenza. Per esempio, se il numero è 9, allora la stringa corrispondente è convString[9] oppure "9". Se possiamo separare il numero 769 in tre cifre singole, 7, 6, e 9, allora convertirlo a una stringa è semplice. Un numero minore di 10 sembra un buon caso base.

Questo ci suggerisce una sequenza di passi in cui dividere un algoritmo per risolvere il problema:

1. Ridurre il numero originale in una serie di cifre.
2. Convertire una cifra nella stringa corrispondente.
3. Concatenare le stringhe che rappresentano le cifre per ottenere il risultato finale.

Come ottenere le unità, le decine, le centinaia? Per esempio, dal numero 769, vogliamo ottenere 9 e convertirlo nella stringa "9", ottenere 6 e convertirlo nella stringa "6", ottenere "7" e convertirlo nella stringa 7. Per fare ciò possiamo dividere 769 per 10: il resto 9 (che è minore di 10) può essere convertito a stringa, il risultato della divisione 76 ci è utile per proseguire la risoluzione. Infatti, con 76 dobbiamo fare la stessa cosa, dividiamo per 10, ottenendo resto 6, che può essere convertito direttamente, e 7 come risultato. In questo caso possiamo interrompere le iterazioni in quanto anche 7 può essere convertito direttamente. Quindi dalla conversione di 769 ci siamo ricondotti alla conversione di 76, e poi alla conversione di 7, come mostrato in Figure 3.

Figura 3: Convertire un Intero in una Stringa in Base 10

Notiamo che alla linea 3, controlliamo se siamo in un caso base, ovvero che n è minore della base in cui stiamo convertendo. Quando siamo in un caso base, fermiamo la ricorsione e ritorniamo semplicemente la stringa ottenuta dalla sequenza convertString. Alla riga 6 facciamo la chiamata ricorsiva, dove l’input della chiamata ha una taglia più piccola del problema corrente.

Questa invece è l’esecuzione se vogliamo convertire 10 nella stringa che lo rappresenta in base 2 ("1010").

Figura 4: Convertire il numero 10 nella sua rappresentazione in base 2

Figura 4 mostra che otteniamo il risultato che ci aspettiamo, ma sembra che le cifre siano nell’ordine sbagliato. Abbiamo risolto il problema ritardando la concatenazione finché la chiamata ricorsiva interna è ritorna, in modo da ottenere il risultato nell’ordine corretto.