GEB.G ovvero come ho scoperto la ricorsività nella programmazione

gebIo sono in ferie. Nel senso che sto tentando di tenermi lontano dal ‘puter per qualche giorno, disintossicarmi. E cosa si fa in questi casi? Altro, per esempio rileggere i classici. Io sono alle prese con Gödel, Escher, Bach di Douglas Hofstadter (1979, versione italiana 1984).

Ogni volta che lo rileggo salta fuori qualcosa di nuovo. O, come nei giorni scorsi un ricordo (attenzione: nostalgia qui) di cose successe all’inizio degli anni ’80, peccato non aver tenuto appunti e sorgente dei programmi! (ma sono passati più di trent’anni).
Allora il mio ‘puter, il Pr1me 550, un mini voleva che si usasse principalmente il Fortran. Vero che c’erano linguaggi di scipting come il CPL, Cobol e RPG per i gestionali, Basic per Giorgio ma erano complementari. E i capi insistevano per usare il IV (1964) meno esoso di risorse del 77 (1978).
DRH invece parla di ricorsività, vietata nel Fortran, prendi questo pezzo copiato da p.146-148 (sperando che l’autore e il sgnor Adelphi non si arrabbino):

Possiamo definire strutture geometriche infinite usando lo stesso metodo, cioè quello di espandere un nodo dopo l’altro. Per esempio, definiamo un diagramma infinito chiamato “Diagramma G”. Useremo a questo scopo una rappresentazione implicita. In due nodi scriveremo semplicemente la lettera ‘G’, che starà per una copia del Diagramma G. Nella Figura 31a abbiamo disegnato il Diagramma G implicitamente.

g1

Ora, se vogliamo vedere il Diagramma G più esplicitamente, possiamo espandere ognuna delle due G, cioè, sostituirle con lo stesso diagramma, ma in dimensioni ridotte (vedi Fig. 31b). Questa versione “di secondo ordine” del diagramma G ci dà una vaga idea dell’aspetto che avrebbe il Diagramma G se fosse completato, cosa che è impossibile.

g2

Nella Figura 32 si vede una parte ancora più grande del Diagramma G, in cui i nodi sono stati numerati, cominciando dal basso e da sinistra a destra. In basso sono stati inseriti due nodi supplementari che portano i numeri 1 e 2.
[…]
Ma il Diagramma G possiede proprietà ancora più sorprendenti. Tutta la sua struttura può essere racchiusa in un’unica definizione ricorsiva che è la seguente:

g3Come fa questa funzione G(n) a racchiudere la struttura ad albero di G? È molto semplice: se si costruisce un albero nel quale si colloca G(n) al di sotto di n per tutti i valori di n, si ritrova il Diagramma G. È proprio così che ho scoperto il Diagramma G la prima volta. Stavo indagando la funzione G e, mentre cercavo un metodo rapido per calcolarne i valori, mi venne l’idea di disporre i valori già noti in un albero. Con mia grande sorpresa, trovai che questo albero ammetteva quella descrizione geometrica ricorsiva estremamente ordinata.

Etc.
Uh! mi ero detto, chissà se… A quei tempi era normale avere un contratto di assistenza, tipo che l’hard disk andava in crash un paio di volte all’anno (fare spesso il back-up!) e conoscevi bene i tecnici. Io mi ero fatto dare un nastro con una versione non proprio ufficiale del Lisp e me ne sono innamorato, e perdura ancora. Tanto che l’altra sera arrivato a p.148 del GEB mi sono detto: ma la G cos’è già che fa, e se…
Ecco (g.nl):

#!/usr/bin/newlisp

(define (g n)
	(if (= 0 n) 
		0
		(- n (g (g (- n 1))))))

;; main
(set 'n (int (main-args 2)))
(print n " -> " (g n) "\n")
(exit)

gnl

Sì, lo so che il Lisp non è che piaccia proprio a tutti e allora ecco Python, il Basic di adesso, ormai la ricorsività non è più un taboo (g.py):

#!/usr/bin/env python3

from sys import argv

def g(n):
	if n == 0:
		return 0
	else:
		return n - g(g(n - 1))

#main
n = int(argv[1])
print(n, '->', g(n))

gpy
OK?
Ma però –ricordo perfettamente– mi disse teh Boss: la ricorsività costa!
Vero. Riscriviamo lo script Python à la Fortran –potrei installarlo ma sapete che sono in ferie :wink:– (g-nonric.py):

#!/usr/bin/env python3

from sys import argv

n = int(argv[1])
g = [0]
for c in range(1, n + 1):
	g.append(c - g[g[c - 1]])
print(n, '->', g[n])

Adesso g non è più una funzione ma una lista, in Fortran sarebbe un array. A proposito allora gli array si chiamavano vettori se monodimensionali e matrici se con due o più dimensioni, oggi i giovani mi hanno cambiato anche il vocabolario 😯

Non cambia niente ma i pythonisti per bene userebbero la list comprehension, lo script precedente sarebbe così:

#!/usr/bin/env python3

from sys import argv

n = int(argv[1])
g = [0]
[g.append(c - g[g[c - 1]]) 
	for c in range(1, n + 1)]
print(n, '->', g[n])

Quindi torniamo all’osservazione del capo di allora (se vi dicessi che il suo nome inizia per G ci credereste?), ecco:

cpy

Quasi 17 secondi contro meno di 3 centesimi! G, teh Boss ha ragione, ancora adesso. Lo so che non interessa ma newLISP ha la possibilità di creare l’eseguibile, vediamo:

cnl

Nessun vantaggio. Però basta nostalgia e basta ‘puter, sono in ferie 😉

Posta un commento o usa questo indirizzo per il trackback.

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.

%d blogger hanno fatto clic su Mi Piace per questo: