Đệ quy và quá trình lặp tuyến tính.

Đệ quy

Chúng ta xem xét thuật toán tính giai thừa của một số như sau:

n! = n · (n − 1) · (n − 2) · · · 3 · 2 · 1.

Có nhiều cách để tính toán giai thừa của một số. Một cách phổ biến là quan sát giai thừa của một số dương bất kì là n! = n*(n-1)!;

n! = n · [(n − 1) · (n − 2) · · · 3 · 2 · 1] = n · (n − 1)!.

Hơn nữa, chúng ta tính giai thừa n! bằng giai thừa của (n-1) và nhân kết quả đó với n. Nếu chúng ta quy ước rằng 1! = 1 , và có thể chuyển thuật toán tính giai thừa thành một procedure.

(define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1)))))

Chúng ta cũng có thể sử dụng mô hình thay thế để xem quy trình tính toán của 6!, như trong hình bên dưới.

Giờ chúng ta hãy có cái nhìn kĩ lưỡng về việc tính toán giai thừa. Chúng ta có thể diễn tả cách tính giai thừa của một số n như sau, đầu tiên nhân 1 với 2, sau đó nhân kết quả với 3, với 4 và cứ thế tiếp tục cho đến khi chúng ta đạt đến giới hạn n.

Qúa trình lặp tuyến tính

Với cách khác, chúng ta gán một product là giá trị của phép giai thừa, cùng với một counter đếm từ 1 đên n. Chúng ta có thể diễn tả việc tính giá trị giai thừa bằng cách liên tục thay đổi giá trị của counter và product từ bước đầu tiên đến các bước tương ứng tiếp theo ngheo nguyên tắc sau:

product ← counter * product
counter ← counter + 1

và return giá trị của n! là giá trị của product khi counter >n;

Chúng ta cũng có thể diễn tả một procedure cho việc tính toán giai thừa bên trên như sau:

Chúng ta có thể sử dụng mô hình thay thế để tái hiện lại quá trình tính toán 6! như hình bên trên.

So sánh hai tiến trình tính toán giai thừa trên từ cái nhìn đơn giản, chúng có những khó khăn nhất định. Cả hai đều sử dụng cùng một hàm toán học trên cùng một công thức và mỗi cái yêu cầu một số bước tỷ lệ với n để tính n!. Thật vậy, cả hai quá trình thậm chí thực hiện cùng một trình tự
phép nhân, thu được cùng một chuỗi các tích từng product. Ở khía cạnh khác, khi chúng ta xem xét “hình dạng” của hai quá trình, chúng ta thấy rằng chúng lũy tiến khá khác nhau.

Số bước thực hiện và nguồn lực để tính đệ quy

Hãy xem xét quá trình tính toàn giai thừa sử dụng đệ quy đầu tiên. Một mô hình thay thế cho thấy một hình dạng của sự giãn ra theo sau là sự co lại, được biểu thị bằng mũi tên trong Hình 1.3.
Việc mở rộng xảy ra khi quá trình xây dựng một chuỗi các hoạt động tính toán bị trì hoãn (trong trường hợp này là một chuỗi các phép nhân). Sự co thắt lại xảy ra khi các quá trình tính toán được thực hiện. Loại quy trình này, đặc trưng bởi một chuỗi các thao tác trì hoãn, được gọi là quy trình đệ quy tuyến tính (Sự mở rộng và sự co thắt lại). Việc thực hiện tiến trình này đòi hỏi trình thông dịch interpreter phải theo dõi
các thao tác cần thực hiện sau này.

Trong tính toán giai thừa của n!, độ dài của chuỗi các phép nhân bị trì hoãn, và do đó lượng thông tin cần thiết để theo dõi nó, tăng tuyến tính với n (tỷ lệ thuận với đến n), giống như số bước để thực hiện tính toán. Quá trình như vậy được gọi là quá trình đệ quy tuyến tính.

Số bước thực hiện và nguồn lực để tính quá trình lặp

Ngược lại, quá trình tính giai thừa sử dụng quá trình lặp tuyến tính thứ hai không giãn nở và co lại (Hình 1.4). Tại mỗi bước, tất cả những gì chúng ta cần theo dõi, với bất kỳ n nào, là các giá trị hiện tại của
các biến product, counter và max-count. Đây gọi là một quá trình lặp lại . Nói chung, một quy trình lặp là một quy trình mà trạng thái của nó có thể được tóm tắt bằng một số biến trạng thái cố định, cùng với một quy tắc cố định. Mô tả cách cập nhật các biến trạng thái chuyển từ giá trị này sang giá trị khác (tùy chọn) và xác định các điều kiện mà quá trình này sẽ kết thúc.

Trong tính toán n!, số bước cần thiết tăng tuyến tính với n. Quá trình như vậy được gọi là một quá trình lặp tuyến tính.

Bài viết tiếp theo: Đệ quy cây