1.4 Lập trình hàm  (Page 5/6)

• Có ít nhất một trường hợp “dừng” để kết thúc việc gọi đệ quy.
• Lời gọi đệ quy phải bao hàm yếu tố dẫn đến các trường hợp “dừng”.

Ví dụ 1: Viết hàm tính n giai thừa

Công thức đệ quy tính n giai thừa là $\text{n!}=\{\begin{array}{c}\text{1 neu n}=0\\ \text{n*}(n-1)!\end{array}$

Hàm (giai_thua N) viết bằng ngôn ngữ LISP:

(defun giai_thua (n)

(if (= n 0) 1 ; trường hợp “dừng”

(* n (giai_thua (1- n))); n-1 là yếu tố dẫn đến trường hợp dừng

) ; If

)

Ví dụ 2: Viết hàm DIV chia a cho b lấy phần nguyên, viết bằng đệ quy.

Công thức đệ quy:

Hàm (DIV a b) viết bằng LISP:

(defun DIV (a b)

(if (<a b) 0 ; Trường hợp “dừng”

(1+ (DIV (- a b) b)); a-b là yếu tố dẫn đến trường hợp dừng

) ; If

)

Ví dụ 3: Viết hàm (phan_tu i L), nhận vào số nguyên dương i và danh sách L. Hàm trả về phần tử thứ i trong danh sách L hoặc thông báo “không tồn tại”.

Công thức đệ quy:

$\text{Phan tu thu i trong DS L}=\{\begin{array}{c}\mathrm{Khong}\mathrm{ton}\mathrm{tai}\text{neu DS L rong}\\ \text{Phan tu dau tien cua L neu i}=\text{1}\\ \text{Phan tu thu}(i-1)\text{trong DS}\mathrm{duoi}\text{cua L}\end{array}$

Hàm (phan_tu i L) viết bằng LISP:

(defun phan_tu(i L)

(cond

((Null L) “Khong ton tai”)

((= i 1) (car L)); trường hợp dừng thứ hai

(T (phan_tu (1- i) (cdr L)))

) ; cond

)

Trong chương trình trên, (null L) là trường hợp “dừng” thứ nhất; (= i 1) là trường hợp “dừng” thứ hai; (cdr L) là yếu tố dẫn đến trường hợp “dừng” thứ nhất và (1- i) yếu tố dẫn đến trường hợp “dừng” thứ hai.

Các hàm nhập xuất

• (LOAD<Tên tập tin>)

Nạp một tập tin vào cho LISP và trả về T nếu việc nạp thành công, ngược lại trả về NIL. Tên tập tin là một chuỗi kí tự có thể bao gồm cả đường dẫn đến nơi lưu trữ tập tin đó. Tên tập tin theo quy tắc của DOS, nghĩa là chỉ có tối đa 8 ký tự trong phần tên và 3 ký tự phần mở rộng và không chứa các ký tự đặc biệt.

Ta có thể sử dụng LOAD để nạp một tập tin chương trình của LISP trước khi gọi thực hiện các hàm đã được định nghĩa trong tập tin đó.

Ví dụ:

>(Load “D:\btlisp\bai1.lsp”)

• (READ)

Ðọc dữ liệu từ bàn phím cho đến khi gõ phím Enter, trả về kết quả là dữ liệu được nhập từ bàn phím.

• (PRINT E)

In ra màn hình giá trị của biểu thức E, xuống dòng và trả về giá trị của E.

• (PRINC E)

In ra màn hình giá trị của biểu thức E (không xuống dòng) và trả về giá trị của E.

• (TERPRI)

Ðưa con trỏ xuống dòng và trả về NIL.

Biến toàn cục và biến cục bộ

Biến toàn cục

Biến toàn cục (global variables) là biến mà phạm vi của nó là tất cả các hàm. Biến toàn cục sẽ tự động giải phóng khi chương trình dịch LISP kết thúc.

• Hàm (SETQ<tên biến><biểu thức>)

Gán trị của<biểu thức>cho<tên biến>và trả về kết quả là giá trị của<biểu thức>.

Ví dụ:

>(setq x (* 2 3))

= 6

>x ; biến x vẫn còn tồn tại và có giá trị là 6

= 6

Biến cục bộ

Biến cục bộ (local variables) là biến mà phạm vi của nó chỉ nằm trong hàm mà nó được tạo ra. Biến cục bộ sẽ tự động giải phóng hàm tạo ra nó kết thúc.

• (LET ( (var1 E1) (var2 E2) ... (vark Ek)) Ek+1 ... En)

Ta thấy hàm này có 2 phần: phần gán trị cho các biến và phần định trị các biểu thức.

Gán trị của biểu thức Ei cho biến cục bộ vari tương ứng và thực hiện (PROGN Ek+1 ... En).

Ví dụ:

>(Let ((a 3) (b 5)) (* a b) (+ a b))

= 8

>a ; biến a lúc này đã được giải phóng nên LISP sẽ thông báo lỗi