 |
Lisp »Tips 'n Tricks
»Funzioni ricorsive in AutoLISP »1 | 2 | 3 | 4 | 5 | 6 | 7
L'esempio seguente è una traduzione in Lisp di un programma in C++ per calcolare il fattoriale di un numero.
Questo è indicato con la notazione n! ed è definito per interi n>=0 come:
n! = 1 se n=0
n! = n x (n - 1)! se n>0
quindi:
n! = 1 x 2 x 3 x ... x n
Visto che per calcolare n! si deve prima calcolare (n-1)! si usa una funzione che invoca se stessa fino a quando n=0.
Le funzioni che chiamano se stesse sono dette funzioni ricorsive.
L'esempio presenta una situazione in cui il programma termina (stop con n=0), se non è presente uno stop la funzione invoca se stessa all'infinito cioè una funzione ricorsiva non può essere definita esclusivamente in termini di se stessa, altrimenti darebbe luogo ad una definizione circolare; una caratteristica essenziale in una definizione ricorsiva è data dalla condizione di terminazione, il cui scopo consiste nel determinare quando una funzione non deve più essere definita in termini di se stessa (nell'esempio n=0).
;;;
;;; Fatt.lsp (versione con bug) - 8 Febbraio 2004
;;; (C) by Claudio Piccini
;;; http://www.cg-cad.com/
;;;
;;; Calcolo del fattoriale di un numero N
;;; Traduzione in Autolisp di
;;; P-05.07-Funzioni ricorsive Fattoriale() 1.cpp
;;; (Introduzione alla programmazione in C++, C.Padovani. Ed.FrancoAngeli)
;;;
(defun fattoriale (n)
(if (= n 0)
(setq n 1) ;stop!
(setq n (* n (fattoriale (- n 1))))
)
)
(defun c:n! (/ num)
(initget (+ 1 4)) ;non nil(1) non negativo(4)
(setq num (getint "\nInserisci un numero intero positivo: "))
(princ (fattoriale num))
(princ)
)
;;;eof
|
//P-05.07-Funzioni ricorsive Fattoriale() 1.cpp
//Introduzione alla programmazione in C++, C. Padovani
#include <iostream>
using namespace std;
double Fattoriale(int n) //restituisce un numero reale
{
if(n==0) return 1; else return n*Fattoriale(n-1);
}
int main()
{
while(true)
{
int n;
cout << "Inserisci un intero positivo ";
cout << "(negativo per uscire) ";
cin >> n;
if(n<0) break;
cout << n << "! = " << Fattoriale(n) << endl;
}
}
Fatt.zip
|
Test del LISP
Che succede al lisp se elimino l'istruzione (initget (+ 1 4)) e batto -1 ?
Command: n!
Inserisci un numero intero positivo: -1
Hard error occurred ***
internal stack limit reached (simulated)
La chiamata a (fattoriale -1) dà luogo ad un ciclo ricorsivo infinito, spezzato da Autocad.
Provo fatt.lsp con i numeri:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17
Command: n!
Inserisci un numero intero positivo: 0
1
Command: n!
Inserisci un numero intero positivo: 1
1
Command: n!
Inserisci un numero intero positivo: 2
2
Command: n!
Inserisci un numero intero positivo: 3
6
Command: n!
Inserisci un numero intero positivo: 4
24
Command: n!
Inserisci un numero intero positivo: 5
120
Command: n!
Inserisci un numero intero positivo: 6
720
Command: n!
Inserisci un numero intero positivo: 7
5040
Command: n!
Inserisci un numero intero positivo: 8
40320
Command: n!
Inserisci un numero intero positivo: 9
362880
Command: n!
Inserisci un numero intero positivo: 10
3628800
Command: n!
Inserisci un numero intero positivo: 11
39916800
Command: n!
Inserisci un numero intero positivo: 12
479001600
Command: n!
Inserisci un numero intero positivo: 13
->1932053504
Command: n!
Inserisci un numero intero positivo: 14
1278945280
Command: n!
Inserisci un numero intero positivo: 15
2004310016
Command: n!
Inserisci un numero intero positivo: 16
2004189184
Command: n!
Inserisci un numero intero positivo: 17
-288522240
Consultando una tavola di fattoriali si vede che il programma dà una risposta errata con n>=13.
Una soluzione è usare la funzione (getreal) al posto di (getint).
Sostituire:
(setq num (getint "\nInserisci un numero intero positivo: "))
con:
(setq num (getreal "\nInserisci un numero intero positivo: "))
Getreal restituisce un numero reale anche se il numero immesso è intero (3 -> 3.0), per eliminare la parte decimale usa la funzione (fix).
Sostituire:
(princ (fattoriale num))
con:
(princ (fix (fattoriale num)))
;;;
;;; Fatt.lsp - 8 Febbraio 2004
;;; (C) by Claudio Piccini
;;; http://www.cg-cad.com/
;;;
;;; Calcolo del fattoriale di un numero N
;;; Traduzione in Autolisp di
;;; P-05.07-Funzioni ricorsive Fattoriale() 1.cpp
;;; (Introduzione alla programmazione in C++, C.Padovani. Ed.FrancoAngeli)
;;;
(defun fattoriale (n)
(if (= n 0)
(setq n 1) ;stop!
(setq n (* n (fattoriale (- n 1))))
)
)
(defun c:n! (/ num)
(initget (+ 1 4)) ;non nil(1) non negativo(4)
(setq num (getreal "\nInserisci un numero intero positivo: "))
(princ (fix (fattoriale num)))
(princ)
)
;;;eof
|
Provo fatt.lsp con i numeri:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 79, 99, 100.
Command: N!
Inserisci un numero intero positivo: 0
1
Command: N!
Inserisci un numero intero positivo: 1
1
Command: N!
Inserisci un numero intero positivo: 2
2
Command: N!
Inserisci un numero intero positivo: 3
6
Command: N!
Inserisci un numero intero positivo: 4
24
Command: N!
Inserisci un numero intero positivo: 5
120
Command: N!
Inserisci un numero intero positivo: 6
720
Command: N!
Inserisci un numero intero positivo: 7
5040
Command: N!
Inserisci un numero intero positivo: 8
40320
Command: N!
Inserisci un numero intero positivo: 9
362880
Command: N!
Inserisci un numero intero positivo: 10
3628800
Command: N!
Inserisci un numero intero positivo: 11
39916800
Command: N!
Inserisci un numero intero positivo: 12
479001600
Command: N!
Inserisci un numero intero positivo: 13
6.22702e+009
Command: N!
Inserisci un numero intero positivo: 14
8.71783e+010
Command: N!
Inserisci un numero intero positivo: 15
1.30767e+012
Command: N!
Inserisci un numero intero positivo: 79
8.94618e+116
Command: N!
Inserisci un numero intero positivo: 99
9.33262e+155
Command: N!
Inserisci un numero intero positivo: 100
9.33262e+157
Lisp »Tips 'n Tricks
Ultimo Aggiornamento_Last Update: 8 Febbraio 2004
|
|
