GIẢI THUẬT ĐỆ QUY
CÁC CHỦ ĐỀ
BÀI MỚI NHẤT
Dự án mới của mình là gamehow.net, mời anh em ghé thăm và góp ý ạ.

Đệ 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ó.

banquyen png
Bài viết này được đăng tại freetuts.net, không được copy dưới mọi hình thức.

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

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

Cùng chuyên mục:

Tìm các số chẵn lẻ bằng Queue và Stack

Tìm các số chẵn lẻ bằng Queue và Stack

Để làm được bài này các bạn cần có kiến thức về cấu trúc Queue…

Cài đặt hàng đợi Queue bằng mảng một chiều

Cài đặt hàng đợi Queue bằng mảng một chiều

Chúng ta sẽ cùng nhau tìm hiểu về cách cài đặt hàng đợi Queue bằng…

Cài đặt hàng đợi Queue bằng danh sách liên kết

Cài đặt hàng đợi Queue bằng danh sách liên kết

Chúng ta sẽ cùng nhau tìm hiểu về cách khởi tạo cấu trúc dữ liệu…

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Hàng đợi Queue là gì? Cấu trúc dữ liệu và các cách cài đặt Queue

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Bài tập kiểm tra số nguyên tố bằng Stack

Bài tập kiểm tra số nguyên tố bằng Stack

Chúng ta sẽ cùng nhau tạo một cấu trúc Stack với danh sách liên kết…

Bài tập chuyển đổi cơ số bằng Stack

Bài tập chuyển đổi cơ số bằng Stack

Trong hướng dẫn này mình sẽ thực hiện giải một bài toán chuyển đổi cơ…

Cài đặt Stack bằng mảng một chiều

Cài đặt Stack bằng mảng một chiều

Chúng ta sẽ lần lượt thực hiện tạo các hàm cơ bản cho Stack như:…

Cài đặt Stack bằng danh sách liên kết

Cài đặt Stack bằng danh sách liên kết

Chúng ta sẽ thực hiện lần lượt các thao tác trong Stack sử dụng danh…

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Ngăn xếp Stack là gì? Cấu trúc và cơ chế hoạt động ra sao?

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc lưu trữ…

Xóa Node khỏi cây đỏ đen

Xóa Node khỏi cây đỏ đen

Chúng ta sẽ cùng nhau tìm hiểu về cách xóa một Node khỏi cây đỏ…

Thêm Node mới vào cây đỏ đen

Thêm Node mới vào cây đỏ đen

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Cây đỏ đen là gì? Cấu trúc của Red-Black Tree

Trong hướng dẫn này mình sẽ giới thiệu các bạn một cấu trúc dữ liệu…

Xóa Node khỏi cây nhị phân tìm kiếm

Xóa Node khỏi cây nhị phân tìm kiếm

Chúng ta sẽ cùng nhau thực hiện xóa Node có 1 con, Node có 2…

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Tìm Node MAX và MIN trong cây nhị phân tìm kiếm

Chúng ta sẽ thực hiện một vài cách tìm ra giá trị MAX và MIN…

Xuất Node con và lá trong cây nhị phân tìm kiếm

Xuất Node con và lá trong cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách xuất các Node con…

Tìm kiếm Node trên cây nhị phân tìm kiếm

Tìm kiếm Node trên cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn cách tìm kiếm một Node…

Duyệt cây nhị phân tìm kiếm

Duyệt cây nhị phân tìm kiếm

Chúng ta sẽ tìm hiểu lần lượt 6 cách duyệt cây nhị phân tìm kiếm:

Thêm Node vào cây nhị phân tìm kiếm

Thêm Node vào cây nhị phân tìm kiếm

Trong hướng dẫn này mình sẽ giới thiệu các bạn về cấu trúc dữ liệu…

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Cấu trúc cây nhị phân là gì? Hoạt động ra sao?

Trong bài này mình sẽ giới thiệu các bạn một trong các cấu trúc dữ…

Gộp hai danh sách liên kết đôi

Gộp hai danh sách liên kết đôi

Chúng ta sẽ cùng nhau tìm hiểu về cách nối hai danh sách liên kết…

Top