Đệ quy cây. Tree recursion

Một mô hình tính toán phổ biến khác cũng được sử dụng nhiều tron thực tế đó là đệ quy cây ( tree recursion). Một ví dụ cụ thể, tính số Fibonacci, với mỗi số là tổng của hai số trước nó.

0, 1, 1, 2, 3, 5, 8, 13, 21, . . . .

Nhìn chung, Số Fibonacci có thể được định nghĩa theo quy tắc sau

Bạn cũng có thể chuyển công thức trên thành một procedure đệ quy cho việc tính số Fibonacci như sau:

(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))

Hãy cùng xem mô hình tính toán đệ quy cây này. Để tính (fib 5), bạn cần phải tính (fib 4) và (fib 3). Để tính (fib 4), bạn cần tính (fib 3) và (fib 2). Nhìn chung quá trình tính toán như thế trông giống như một cây (Hình 1.5). Chú ý ở đây là, các nhánh chia tách thành hai nhánh con, ngoại trừ các nhánh ở lá. Điều này nói lên sự thật rằng thủ tục tính toán số Fib gọi chính nó hai lần mỗi lần bạn muốn tìm một số Fib ở vị trí bất kì.

Qúa trình gọi Procedure tính toán số Fib như là một cây đệ quy (tree recursion), nhưng nó không phải là cách tốt nhất để tính số Fibonacci, vì nó không làm giảm kích thước tính toán. Chú ý ở hình 1.5, toàn bộ quá trình tính toán (fib 3) , hầu hết công việc tính toán mang tính chất lặp lại. Sự thật, chúng khó để đưa ra rằng số lần procedure sẽ tính (fib 1) và (fib 0) (là các nút lá của cây) là một mẫu Fib(n+1).

Để đưa ra một ý tưởng về cách tính toán đó tệ như thế nào, chúng ta có thể chứng minh rằng, giá trị của Fib(n) tăng nhanh với n. Hơn nữa, Fib(n) là một số nguyên gần bằng nhất với ((ϕ^n)/√5), với ϕ =(1 + √5)/2 ≈ 1.6180 là tỉ lệ vàng sắp xỉ (golden ratio) thỏa mãn hằng đẳng thức sau ϕ^2 = ϕ + 1.

Hơn nữa, tiến trình sử dụng số lượng bướcđể tính toán tương ứng với input n. Trên khía cạnh khác, nguồn lực bộ nhớ cũng tăng với giá trị input, vì chúng ta cần theo dõi các node ở trên của cây ở bất kỳ node tính toán nào. Nhìn chung, số bước để tính toán trong tiến trình đệ quy cây tương ứng với số node trong cây, nguồn lực tính toán yêu cầu tương ứng là độ cao của cây.

Các số Fib cũng có thể được tính toán bằng một tiến trình lặp. Ý tương của việc tính toán là sử dụng một cặp số nguyên a và b, sau đó khởi tạo Fib(1) = 1 và Fib(0) =0, và áp dụng sự lặp lại cho việc gán giá trị mới đồng thời cho cặp số nguyên a và b như sau

a ← a + b,
b ← a

It is not hard to show that, aer applying this transformation n times, a
and b will be equal, respectively, to Fib(n + 1) and Fib(n). us, we can
compute Fibonacci numbers iteratively using the procedure

Sau khi gán giá trị mới đồng thời cho a và b với n lần sự lặp lại, thì ta mong đợi rằng a và b sẽ bằng tương ứng với Fib(b+1) và Fib(n). Hơn nữa, chúng ta có thể tính toán các số Fibonacci bất kì bằng việc sử dụng thủ tục như bên dưới:

(define (fib n)
(fib-iter 1 0 n))
(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))

Phương thức tính toán số Fib(n) là một quá trình lặp tuyến tính. Sự khác biệt của hai quá trình tính toán dựa vào đệ quy và quá trình lặp tuyến tính là số bước để thực hiện. Một tuyến tính với n, và một bùng nổ nhanh chóng trong Fib(n) là rất lớn, thậm chí với đối số nhập vào nhỏ.

Nhưng không vì thế mà chúng ta kết luận rằng tiến trình của cây đệ quy là vô dụng. Khi chúng ta xem xét tiến trình tính toán trên dữ liệu cấu trúc phân cấp hơn là các số, chúng ta sẽ tìm thấy rằng cây đệ quy là một công cụ hữu ích và mạnh mẽ. Thậm chí trong các tính toán số học, các tiến trình cây đệ quy giúp chúng ta hiểu rõ hơn về các thiết kế chương trình. Ví dụ, đệ quy cậy cần ít sự đầu tư để hiểu hơn trong việc chuyển từ công thức toán học sang định nghĩa một thủ tục tính toán Fibonacci trong ngôn ngữ lập trình. Còn việc công thực hóa một thuật toán lặp đê tính số Fib yêu cầu nhiều sự nổ lực để tổng quát hóa việc tính toán trong việc xác định trạng thái của 3 biến trên.

Ví dụ: Counting change

Cần có một sự thông minh nhất định để có thể đưa ra được thuật toán tính số Fibonacci sử dụng tiến trình lặp. Ngược lại với nó là cây đệ quy, hãy xem xét một ví dụ dưới đây.

Có bao nhiêu cách để đổi 1$ sang các mệnh tiền giá thấp hơn như, 0.5$, 0.25$, 0.1$, 0.05$ và 0.01$ ( tương ứng với 50, 25, 10, 5 và 1 cent)? Nhìn chung chúng ta có thể tính toán số cách để đổi bất kì số lượng tiền nào đến các mệnh giá trên?

Sủ dụng thủ tục đệ quy để giải quyết bài toán trên. Chúng ta sẽ xem các loại coins được sắp xếp theo thứ tự tăng dần là 1, 5, 10, 25 và 50 cents. Sau đéo xem xét môi quan hệ tính toán như sau.

Số lượng cách để đổi lượng tiền(amount – a) sử dụng tất cả các loại mệnh tiền nhỏ, ngoại trừ mệnh tiền đầu tiên. Cộng với
Số lượng cách để đổi số lượng tiền (a – d) sử dụng tất cả các mệnh tiền nhỏ, d là mênh giá của coin đầu tiên.

Chúng ta sử dụng đệ quy để giảm thiểu vấn đề của việc đổi tiền với lượng tiền cho trước đến vấn đề đổi tiền với số lượng tiền nhỏ hơn sử dụng ít loại coins hơn. Hãy xem xét kỹ lưỡng nguyên tắc, và thuyết phục chúng ta có thể diễn tả thuật toán đổi tiền này bằng cách cụ thể hóa nó thành các trường hợp như sau:

Nếu số lượng tiền (a) là 0, thì chúng ta có 1 cách để đổi.
Nếu a nhỏ hơn 0, chúng ta có 0 cách để đổi.
Nếu số lượng mệnh tiền nhỏ (n) là 0, chúng ta có 0 cách để đổi tiền.

Chúng ta có thể dễ dàng thực hiện các trường hợp trên vào trong một thủ tục đệ quy như sau:

(define (count-change amount) (cc amount 5))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1) ((or (< amount 0) (= kinds-of-coins 0)) 0) (else (+ (cc amount (- kinds-of-coins 1)) (cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins)))))

(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 5)
((= kinds-of-coins 3) 10)
((= kinds-of-coins 4) 25)
((= kinds-of-coins 5) 50)))

Procedure first-denomination cần giá trị input là số lượng coins cần để đổi và trả về mệnh giá tương ứng của đồng tiền coin đó. Xem như các loại coins được sắp xếp theo thứ tự giảm dần.

Bây giờ chún ta sẽ trả lời được câu hỏi ban đầu hóc búa của chúng ta về có bao nhiêu cách để đổi 1$ (100 cent).

(count-change 100)
Kết quả: 292

Bài viết tiếp theo: Orders of Growth