Hàm đệ quy trong lập trình và minh họa với C++

Đây là bài 27/43 bài của series môn học Nhập môn lập trình

Trong bài này, chúng ta sẽ tìm hiểu về kỹ thuật lập trình đệ quy. Cách kỹ thuật đệ quy hoạt động và một số ví dụ về đệ quy.

1. Đệ quy là gì?

Một hàm gọi chính nó được gọi là hàm đệ quy. Kỹ thuật lập trình này gọi là đệ quy.

void recurse()
{
    ... .. ...
    recurse();
    ... .. ...
}

int main()
{
    ... .. ...
    recurse();
    ... .. ...
}
Cách hàm đệ quy hoạt động

Lưu ý: Không thể để hàm gọi hàm liên tục, vô hạn được. Để ngăn chặn đệ quy vô hạn, thường sử dụng câu lệnh if.

Chương trình C++ tính giai thừa minh họa hàm đệ quy

Tính giai thừa của n: S(n) = n! = 1*2*…*(n-1)*n

Ta thấy S(n) = S(n-1)*n. Vậy thay vì tính S(n) ta sẽ đi tính S(n-1). Tương tự tính S(n-2), …, S(2), S(1), S(0) = 1.

// Factorial of n = 1*2*3*...*n

#include <iostream>
using namespace std;

int factorial(int n) {
	if (n > 1) {
		return n * factorial(n - 1);
	}else {
		return 1;
	}
}

int main() {
	int n, result;

	cout << "Enter a non-negative number: ";
	cin >> n;

	result = factorial(n);
	cout << "Factorial of " << n << " = " << result;
    system("pause");
}
Kết quả
Enter a non-negative number: 4
Factorial of 4 = 24

Hàm đệ quy int factorial(int n) trên hoạt động như sau:

int factorial(int n) {
	if (n > 1) {
		return n * factorial(n - 1);
	}else {
		return 1;
	}
}

Khi nhập n = 4, gọi hàm result = factorial(n); tức là result = 4 * factorial(3).

Hàm factorial(3) = 3 * factorial(2). Hàm factorial(2) = 2 * factorial(1).

Mà khi n = 1 (không thỏa điều kiên if (n > 1)) thì return 1; tức là factorial(1) = 1.

Do đó, result = factorial(n) = 4*3*2*1 = 24.

2. Chương trình xuất dãy số fibonacci sử dụng hàm đệ quy

Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 0 và 1. Các phần tử sau đó được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng hai phần tử trước nó. Công thức truy hồi của dãy fibonacci có dạng: f(n) = f(n-1) + f(n-2) với f(0) = 0, f(1) = 1.

Khi tính f(n) với n > 1 phải dựa vào 2 số fibonacci trước đó. Bài toán này có thể dùng hàm đệ quy như sau:

#include <iostream>
using namespace std;
int fibonacci(int x) {
	if((x==1)||(x==0)) {
		return(x);
	}else {
		return(fibonacci(x-1)+fibonacci(x-2));
	}
}
int main() {
	int x , i=0;
	cout << "Enter the number of terms of series : ";
	cin >> x;
	cout << "Fibonacci Series : ";
	while(i < x) {
		cout << " " << fibonacci(i);
		i++;
	}
	system("pause");
}
Kết quả
Enter the number of terms of series : 5
Fibonacci Series :  0 1 1 2 3

3. Ưu và nhược điểm của hàm đệ quy

Ưu điểm: Giúp code ngắn hơn và rõ ràng hơn.

Nhược điểm:

– Việc gọi hàm liên tục sẽ làm khởi tạo các biến cục bộ trong hàm một cách liên tục và gây tốn bộ nhớ.

– Quá trình xử lý tốn nhiều thời gian hơn.

– Khó debug để tìm ra lỗi.

5/5 - (2 bình chọn)
Bài trước và bài sau trong môn học<< Biến toàn cục và biến cục bộ trong chương trìnhMảng một chiều là gì? Cách khai báo và khởi tạo trong C++ >>
Chia sẻ trên mạng xã hội:

Trả lời

Lưu ý:

1) Vui lòng bình luận bằng tiếng Việt có dấu.

2) Khuyến khích sử dụng tên thật và địa chỉ email chính xác.

3) Mọi bình luận trái quy định sẽ bị xóa bỏ.