Esercizio 7ricorsione su file e stringhe

1. Contare le righe con la ricorsione

Schema. Una ricorsione sul file ha la stessa forma di una ricorsione su una lista: si consuma un elemento (una riga) e si risolve lo stesso problema sul resto.

• Caso base: non ci sono più righe → il conteggio è $0$.
• Passo: leggo una riga; il conteggio è $1$ se la riga inizia con ->, altrimenti $0$, più il conteggio sul resto del file.

Il "resto del file" è lo stesso oggetto file, la cui posizione di lettura è avanzata: non serve passare un indice.

import io

def conta_righe(f):
    riga = f.readline()
    if riga == "":                       # caso base: fine del file
        return 0
    c = 1 if riga.startswith("->") else 0
    return c + conta_righe(f)            # passo: stesso problema sul resto


testo = ("Ironman:Malibu\nSpider man:New York\n->Batman:Gotham\n->Superman:Metropolis\n"
         "->Flash:Central City\n->Green Arrow:Starling City\nThor:Asgard\nX-Men:Salem Center\n")
print(conta_righe(io.StringIO(testo)))      # 4

(Con un file vero: with open("supereroi.txt") as f: print(conta_righe(f)).)

Punti delicati:

• readline() restituisce "" (stringa vuota) solo alla fine del file; una riga vuota del file è "\n", che non è "": così le righe vuote non fermano la ricorsione.
• riga.startswith("->") funziona anche per righe più corte di due caratteri (una riga - o vuota). La soluzione Java di partenza con line.charAt(0) e line.charAt(1) fallisce su una riga vuota o di un solo carattere.
• La ricorsione non è in coda ($c + \ldots$ resta da fare dopo la chiamata): ogni riga occupa un frame sullo stack. Python ha un limite di circa $1000$ chiamate annidate: per file di migliaia di righe questo programma darebbe RecursionError. La versione iterativa sum(1 for r in f if r.startswith("->")) non ha il problema; l'esercizio chiede però la ricorsione, che per un file piccolo va bene.

2. Rovesciare una stringa

Definizione ricorsiva. Per s di lunghezza 0 o 1 l'inverso è s stessa (caso base). Altrimenti l'inverso di s è l'inverso del resto (tutti i caratteri tranne il primo) seguito dal primo carattere:

$$\text{rov}(c\,\cdot\,w) = \text{rov}(w)\,\cdot\,c.$$

import sys

def rovescia(s):
    if len(s) < 2:                      # caso base: "" e un carattere
        return s
    return rovescia(s[1:]) + s[0]       # passo: inverso del resto + primo carattere


if __name__ == "__main__":
    if len(sys.argv) != 2:
        print("uso: python rovescia.py <stringa>")
    else:
        print(rovescia(sys.argv[1]))     # python rovescia.py FestivaldiCannes -> sennaCidlavitseF

Traccia di rovescia("abc"):

rovescia("abc") = rovescia("bc") + "a"
                = (rovescia("c") + "b") + "a"
                = (("c") + "b") + "a" = "cba"

Costo. Ogni chiamata crea una nuova stringa con s[1:] e +: $O(n)$ per chiamata, $O(n^2)$ in totale; la profondità è $n$. Una variante che divide a metà ha profondità $O(\log n)$:

def rovescia2(s):
    if len(s) < 2:
        return s
    m = len(s) // 2
    return rovescia2(s[m:]) + rovescia2(s[:m])    # l'inverso è: inverso della seconda metà + inverso della prima

Con una stringa di $2000$ caratteri rovescia supera il limite di ricorsione di Python, rovescia2 no (profondità $\approx 11$).

In C: in loco

In C le stringhe sono array di char modificabili: si può rovesciare senza creare altre stringhe, scambiando gli estremi e restringendo l'intervallo.

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

/* rovescia s[i..j] scambiando gli estremi e restringendo l'intervallo */
void rovescia(char *s, int i, int j) {
    if (i >= j)                 /* caso base: 0 o 1 carattere */
        return;
    char t = s[i]; s[i] = s[j]; s[j] = t;
    rovescia(s, i + 1, j - 1);  /* passo: problema più piccolo di 2 */
}

int main(int argc, char *argv[]) {
    if (argc != 2) { fprintf(stderr, "uso: %s <stringa>\n", argv[0]); return 1; }
    char buf[256];
    strncpy(buf, argv[1], sizeof buf - 1);
    buf[sizeof buf - 1] = '\0';
    rovescia(buf, 0, (int)strlen(buf) - 1);
    printf("%s\n", buf);
    return 0;
}

./rovescia FestivaldiCannes stampa sennaCidlavitseF. Il cast (int)strlen(buf) - 1 è necessario: strlen restituisce un tipo senza segno e per la stringa vuota strlen(buf) - 1 darebbe un numero enorme invece di $-1$. La ricorsione è in coda (l'ultima azione è la chiamata): un compilatore può trasformarla in un ciclo. Per le stringhe letterali come "Hello" non si può modificare in loco (char *s = "Hello" punta a memoria di sola lettura): serve una copia in un array, come buf.

Verifica

import random, string

assert conta_righe(io.StringIO("")) == 0
assert conta_righe(io.StringIO("\n-\n->\n")) == 1          # righe vuote o troppo corte
for _ in range(300):
    s = "".join(random.choice(string.ascii_letters) for _ in range(random.randint(0, 60)))
    assert rovescia(s) == s[::-1] == rovescia2(s)
print(rovescia("FestivaldiCannes"), rovescia2("FestivaldiCannes"))     # sennaCidlavitseF sennaCidlavitseF
try:
    rovescia("x" * 2000)
except RecursionError:
    print("RecursionError")
print(rovescia2("x" * 2000) == "x" * 2000)                 # True

Errori comuni

• Dimenticare il caso base (o metterlo troppo tardi): RecursionError in Python, stack overflow in C.
• Chiamare ricorsivamente con lo stesso problema (rovescia(s) invece di rovescia(s[1:])).
• Confondere riga vuota ("\n") con fine file ("").
• Accedere a riga[0] e riga[1] senza controllare la lunghezza.
• In C, modificare una stringa letterale o usare strlen(s) - 1 senza cast.