Đệ quy là một quá trình mà một hàm gọi chính nó. Chúng ta sử dụng đệ quy để giải bài toán lớn hơn thành các bài toán con nhỏ hơn. Một điều chúng ta phải ghi nhớ, rằng nếu mỗi bài toán con tuân theo cùng một loại mẫu, thì chỉ chúng ta mới có thể sử dụng phương pháp đệ quy.
Một hàm đệ quy có hai phần khác nhau. Trường hợp cơ sở và trường hợp đệ quy. Trường hợp cơ sở được sử dụng để kết thúc nhiệm vụ lặp lại. Nếu trường hợp cơ sở không được xác định, thì hàm sẽ lặp lại vô số lần (Về mặt lý thuyết).
Trong chương trình máy tính, khi chúng ta gọi một hàm, giá trị của bộ đếm chương trình được lưu vào ngăn xếp bên trong trước khi chuyển vào vùng hàm. Sau khi hoàn thành nhiệm vụ, nó bật ra địa chỉ và gán nó vào bộ đếm chương trình, sau đó tiếp tục nhiệm vụ. Trong cuộc gọi đệ quy, nó sẽ lưu trữ địa chỉ nhiều lần và chuyển sang câu lệnh gọi hàm tiếp theo. Nếu một trường hợp cơ sở không được xác định, nó sẽ lặp lại nhiều lần và lưu trữ địa chỉ vào ngăn xếp. Nếu ngăn xếp không còn khoảng trống nữa, nó sẽ xuất hiện lỗi là "Tràn ngăn xếp nội bộ".
Một ví dụ về cuộc gọi đệ quy là tìm giai thừa của một số. Chúng ta có thể thấy rằng giai thừa của một số n =n! giống với n * (n-1) !, lại giống với n * (n - 1) * (n - 2) !. Vì vậy, nếu giai thừa là một hàm, thì nó sẽ được gọi lại nhiều lần, nhưng đối số bị giảm đi 1. Khi đối số là 1 hoặc 0, nó sẽ trả về 1. Đây có thể là trường hợp cơ bản của đệ quy.
Ví dụ
#include<iostream>
using namespace std;
long fact(long n){
if(n <= 1)
return 1;
return n * fact(n-1);
}
main(){
cout << "Factorial of 6: " << fact(6);
} Đầu ra
Factorial of 6: 720