Đệ quy tuyến tính (Linear Recursion) - Giải thuật đệ quy

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:

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ả:

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!!!