Thuật toán đệ quy trong lập trình C/C++

Thuật toán đệ quy trong lập trình C/C++ là một giải thuật cực kì quan trọng. Toàn tập khái niệm và đặc điểm của đệ quy, ví dụ minh họa bài toán tính Fibonaci thứ n.

1. Thuật toán đệ quy là gì?

Trước tiên bạn cần hiểu đệ quy là gì: Đệ quy là một kỹ thuật dùng để định nghĩa trực tiếp hay gián tiếp theo chính nó. Một đối tượng được gọi là đệ quy nếu nó bao gồm chính nó như một bộ phận hoặc nó được định nghĩa dưới dạng của chính nó.
Ví dụ: n! = n*(n-1)!

Khái niệm thuật toán đệ quy: Thuật toán được gọi là đệ quy nếu nó có lời giải được gọi đến nó một cách trực tiếp hay gián tiếp.
Như vậy khi bạn viết một hàm để giải quyết một vấn đề nào đó, nếu trong hàm lại gọi lại chính hàm đó thì đây chính là đệ quy.

Các đặc điểm của thuật toán đệ quy:

1. Trong đó bao giờ cũng có lời gọi đến chính tên thuật toán (hàm)
2. Mỗi lần gọi thì kích thước của bài toán lại nhỏ đi
3. Có trường hợp đặc biệt để kết thúc đệ quy. (tính dừng của đệ quy)

Nếu như trong thuật toán của bạn thiết bất kì đặc điểm nào ở trên thì

Các bài toán đệ quy C/C++ thường gặp:

• Tính n giai thừa
• Tính fibonaci
  Duyệt cây
• . . .

Chú ý: Thuật toán này có thể áp dụng với mọi ngôn ngữ lập trình (Python, Java, C#, PHP, JavaScript . . .). Nhưng thường chúng ta mới học sẽ bắt đầu với C/C++ nhé!

2. Bài toán tìm số Fibonacci thứ N

Bài toán tìm Fibonacci thứ n là một bài toán hay về đệ quy. Dãy số fibonacci được định nghĩa như sau:

• Nếu n = 1 hoặc n = 2 thì fib(n) = 1
• Nếu n >2 thì fib(n) = fib(n-1) + fib(n-2)

Giải thuật bài toán tìm fibonacci viết bằng C/C++:

// Thuật toán đệ quy tìm fibonacci thứ n
int fibonacci(int n){

	if(n==1 || n==2)  // trường hợp đặc biệt
		return 1;
	else
		return fibonacci(n-1) +fibonacci(n-2);  // Lời gọi đến chính nó
}

Bài toán Fibonacci viết bằng Python:

// Tim so fibonacci thu n
def fibonacci(n):
	if(n==1 or n==2):
		return 1
	else:
		return (fibonacci(n-1)+fibonacci(n-2))
print(fibonacci(4))

Lời kết

Đệ quy là một thuật toán được sử dụng rất nhiều trong lập trình. Đây là một thuật toán giúp các lập trình viên giải quyết được nhiều bài toán khó trong thực tế. Tóm lại nó là một thuật toán cực kì quan trọng và bạn cần phải nắm chắc nó.

Xem thêm các bài viết về lập trình khác của mình tại đây!

Cảm ơn bạn đã ghé thăm blog của mình nha!