1. Cấu trúc của thủ tục Đệ quy

a) Cấu trúc thủ tục Đệ quy

Trong lập trình, hàm hay thủ tục được gọi là đệ quy nếu có lời gọi đến chính mình.

Mọi hàm đệ quy phải có phần gọi đệ quy và phần cơ sở.

Phần cơ sở thiết lập các giá trị ban đầu của hàm và có vai trò kiểm soát, kết thúc các lời gọi đệ quy.

❓Ví dụ. Để tính tổng các số từ 1 đến n, ta thiết kế chương trình (theo kĩ thuật Đệ quy và bằng cấu trúc vòng lặp for) như trong hình. Trong chương trình bên trái, giá trị trả gọi đến chính nó với kích thước đầu vào giảm 1 và chỉ dừng nếu n có giá trị là 1.

b) Thiết kế chương trình Đệ quy

Trước khi lập trình thủ tục, cần thiết kế thuật toán đệ quy để giải bài toán có đối tượng được định nghĩa đệ quy. Tùy thuộc vào bài toán mà thiết kế chương trình khác nhau, nhưng đều có chung mô hình:

❓Bài toán. Tính số thứ n trong dãy cấp số cộng đã cho, biết rằng số hạng đầu tiên là a₁ ​= 4 và công sai d = 4.

Bước 1. Xác định cấu trúc bài toán đưa ra có là một đối tượng được định nghĩa đệ quy.

Trong cấp số cộng, mỗi số hạng bằng số hạng liền trước nó cộng với công sai d. Tức là a_n​ = a_n−1​ + d.

Bài toán lớn (a_n​) được định nghĩa dựa trên phiên bản nhỏ hơn của chính nó (a_n−1​) và một hằng số.

Số hạng đầu tiên là a₁​ = 4 là trường hợp không cần phải tính toán.

Bước 2. Thiết kế lời giải khi đã xác định phần đệ quy và phần cơ sở.

Nếu n = 1 thì trả về 4 (a₁ = 4).

Nếu n > 1 thì a_n ​ = a_{n − 1} ​+ d (với d = 4).

Như vậy, hàm a(n) sẽ gọi lại chính nó để tính a(n−1), sau đó cộng 4 vào kết quả đó.

Mỗi lần gọi đệ quy (a(n−1)), giá trị của n đều giảm đi đến khi n sẽ giảm đến 1 thì đệ quy dừng.

Bước 3. Cài đặt thuật toán bằng ngôn ngữ lập trình cụ thể.

def cap_so_cong_dequy(n):

if n == 1: #phần cơ sở

return 4

return cap_so_cong_dequy(n - 1) + 4 #gọi đến lời giải đệ quy

3. Đệ quy có nhớ

Thuật toán đệ qui gọi đến chính nó với kích thước nhỏ hơn, điều này có thể dẫn đến việc ở mỗi lần gọi, chương trình tính toán lại những lời giải đã được xử lí trước đó. → Mất nhiều thời gian thực hiện chương trình.

❓Ví dụ. Khi cài đặt thủ tục đệ qui tính dãy Fibonacci với n = 6, hàm f(6) cần tính: f(4) hai lần, f(3) ba lần và f(2) được tính nhiều hơn nữa. Khi cài đặt bằng thủ tục đệ qui có nhớ, kiểm tra f(n) đã được tính bằng cách tìm trong mảng, nếu f(n) đã được tính thì trả ra giá trị của nó, ngược lại tính f(n) và lưu lại giá trị vừa tính vào mảng.