Các kiểu dữ liệu trong C ( int - float - double - char ...) 
Thuật toán tìm ước chung lớn nhất trong C/C++ 
Cấu trúc lệnh switch case trong C++ (có bài tập thực hành) 
Lệnh cin và cout trong C++ 
Random trong Python: Tạo số random ngẫu nhiên 
ComboBox - ListBox trong lập trình C# winforms 
Thuật toán kiếm tra số nguyên tố 
Cách khai báo biến trong PHP, các loại biến thường gặp 
Download và cài đặt Vertrigo Server 
Thẻ li trong HTML 
Thẻ article trong HTML5 
Cấu trúc HTML5: Cách tạo template HTML5 đầu tiên 
Cách dùng thẻ img trong HTML và các thuộc tính của img 
Thẻ a trong HTML và các thuộc tính của thẻ a thường dùng Đệ quy tuyến tính (Linear Recursion)
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.
Bài viết này được đăng tại [free tuts .net]
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<<"\nKết quả \n"<<n<<"! = "<<kq;
cout<<"\n-----------------------------\n";
cout<<"chương trình này được đăng tại Freetuts.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!!!
