Đệ Quy Tuyến Tính (Linear Recursion) - Giải Thuật đệ Quy

Trang chủ » đệ Quy Tuyến Tính » Đệ Quy Tuyến Tính (Linear Recursion) - Giải Thuật đệ Quy

Có thể bạn quan tâm

Trong bài này mình sẽ giới thiệu đến các bạn một trong các hàm đệ quy đó chính là đệ quy tuyến tính. Đây là một hàm đệ quy cơ bản nhất và được sử dụng rất nhiều trong lập trình.

Chúng ta sẽ cùng nhau tìm hiểu về khái niệm đệ quy tuyến tính (Linear Recursion) cũng như cơ chế hoạt động của nó.

1. Đệ quy tuyến tính là gì?

Đệ quy tuyến tính là hàm đệ quy chỉ gọi chính nó một lần trong thân hàm. Hiểu đơn giản là trong một hàm, nếu có duy nhất một câu lệnh gọi chính hàm đó thì được gọi là hàm đệ quy tuyến tính.

Ví dụ hàm tính giai thừa chính là một hàm đệ quy tuyến tính, vì nó chỉ gọi lại chính nó một lần duy nhất.

Int factorial(int n){ If(n == 0) return 1; return n * factorial(n-1); }

2. Cơ chế hoạt động của đệ quy tuyến tính (Linear Recursion)

Chúng ta sẽ lấy ví dụ hàm factorial() tính giai thừa, để xem cơ chế hoạt động của nó như thế nào nhé.

Int factorial(int n){ If(n == 0) return 1; return n * factorial(n-1); }

Giả sử chúng ta muốn tính 5! thì khi đó cơ chế hoạt động như hình bên dưới đây:

co che de quy tuyen tinh PNG

Cứ sau mỗi lần gọi hàm factorial(), kết quả sẽ được đẩy vào Stack cho đến khi gặp điều kiện dừng hàm sẽ kết thúc và trả về kết quả 1. Sau đó gọi Stack để tính kết quả, cơ chế Stack sẽ lấy từ trên xuống vì vậy kết quả sẽ là : 1 * 1 * 2 * 3 * 4 * 5 = 120.

Code mẫu:

#include <iostream> using namespace std; //hàm đệ quy tuyến tính int factorial(int n){ if(n == 0) return 1; // điểm dừng của hàm, nếu n == 0 thì kết thúc hàm và trả về 1 return n * factorial(n-1); } //hàm main int main() { int n; cout<<"Nhập vào số giai thừa bạn muốn tính: "; cin>>n; int kq = factorial(n);//gọi hàm factorial() để tính giai thừa cho n và gán kết quả vào biến kq cout<<" Kết quả "<<n<<"! = "<<kq; cout<<" ----------------------------- "; cout<<"chương trình này được đăng tại Zaidap.com.net"; }

Kết quả:

de qui tuyen tinh1 PNG

Như vậy là chúng ta đã thực hiện xong chương trình tính giai thừa của số nguyên n áp dụng hàm đệ quy. Cũng như kết thúc hướng dẫn đệ quy tuyến tính (Linear Recursion), chúc các bạn thực hiện thành công!!!

Từ khóa » đệ Quy Tuyến Tính