Thủ tục đệ quy c. Đệ quy. Nhiệm vụ đào tạo

Để không phải viết một bài báo dài, trong đó sẽ có rất nhiều ví dụ về đệ quy trong C++, tôi sẽ viết thêm một ví dụ về đệ quy ở đây. Qua nhìn chung Những người hiểu cơ bản và sử dụng đệ quy trực tiếp trong các hàm của mình có thể bỏ qua tài liệu này. Đây là một ví dụ về cách sử dụng đệ quy, như trong bài viết Hàm trong C++ dành cho người mới bắt đầu. đệ quy

Bài 1 – Sử dụng đệ quy, hiển thị giai thừa của một số từ 1 đến N
Viết mã
=============================
GIAI ĐOẠN Số 1 viết một chương trình trống
=============================

#bao gồm

int chính()
{
hệ thống ("cls");

getch();
trả về 0;
}

Một chương trình trống đã được tạo, tôi nghĩ không cần bình luận
GIAI ĐOẠN số 2 ta viết ta viết chính hàm đệ quy
=========================================

#bao gồm

//Hàm đệ quy của chúng ta
int thực tế (int N )
{

//0! = 1, 1!=1, 2!=2, 3!=6... Bởi vì 2 số đầu tiên là số 1 và không theo thứ tự nghiêm ngặt, chúng tôi buộc điểm này trong mã

nếu n<2 return 1 ;
nếu không thì trả về n * sự thật(n–1) // ở đây hàm gọi chính nó

}

int chính()
{
hệ thống ("cls");
cout<//Điểm gọi của hàm đệ quy. In giai thừa 10 lên màn hình
getch();
trả về 0;
}
ddd
============

Phần chính trong chương trình đệ quy C++
trả lại n * sự thật(n–1)

Hàm của chúng tôi tính toán lại để có được giá trị trước đó. Giá trị thực là tham số được truyền cho N từ thời điểm gọi hàm. Mục đích gọi hàm của chúng ta là gọi nó từ khối chính của chương trình. Trong trường hợp của chúng tôi, chúng tôi gọi nó từ một hàm int chính()
Tại sao tôi không viết bài tiếp theo mà viết bài trước? Khi các số được nhân lên, thì đầu tiên 0 * 1 ở đây là giá trị hiện tại của chúng ta là 1 và 0 là giá trị tính toán trước đó. Đây là toàn bộ bản chất của đệ quy, chúng tôi tính giá trị hiện tại bằng cách sử dụng giá trị trước đó, trong khi giá trị trước đó thu được bằng cách tính toán tương tự. Trình biên dịch tự tính toán giá trị trước đó và lưu giá trị này vào bộ nhớ. Tất cả những gì chúng ta cần làm là đưa ra hướng dẫn. . Nhờ tính năng này của trình biên dịch, một hàm gặp phải lệnh gọi chính nó (trong trường hợp của chúng tôi sự thật(n–1) ) không ghi đè tham số được truyền cho Nđể tính hàm. Tham số được truyền tới N nó vẫn còn trong bộ nhớ. Trong trường hợp này, một vùng bộ nhớ khác được xác định bổ sung trong đó hàm đệ quy của chúng ta thực hiện các phép tính đệ quy để thu được kết quả trước đó.

Mong các lập trình viên tha thứ cho tôi vì nhận xét thiếu suy nghĩ như vậy. Đây gần như là cách người mới bắt đầu cảm nhận đệ quy.

Tôi hy vọng blog C++ dành cho người mới bắt đầu này hữu ích với ai đó và giúp ai đó hiểu khái niệm cơ bản về hàm đệ quy trong C++

Ghi chú. Trong bài viết này, cũng như bài trước, tôi không tính toán từ 1 đến N mà tính theo giá trị được nhập bên trong chương trình. Vấn đề là tôi không muốn viết thêm một dòng mã nào và cho rằng người dùng đã thành thạo trong việc nhập dữ liệu và hiển thị nó trên màn hình.

Đệ quy là một hiện tượng khá phổ biến xảy ra không chỉ trong lĩnh vực khoa học mà còn trong đời sống hàng ngày. Ví dụ: hiệu ứng Droste, tam giác Sierpinski, v.v. Cách dễ nhất để xem đệ quy là hướng camera Web vào màn hình điều khiển máy tính, một cách tự nhiên, sau khi bật nó lên trước. Như vậy, camera sẽ ghi lại hình ảnh của màn hình máy tính và hiển thị lên màn hình này, nó sẽ giống như một vòng khép kín. Kết quả là chúng ta sẽ quan sát thấy thứ gì đó tương tự như một đường hầm.

Trong lập trình, đệ quy có quan hệ mật thiết với hàm, hay nói chính xác hơn là nhờ hàm trong lập trình mà mới có đệ quy hay hàm đệ quy. Nói một cách đơn giản, đệ quy là định nghĩa một phần của hàm (phương thức) thông qua chính nó, tức là nó là hàm gọi chính nó, trực tiếp (trong thân hàm) hoặc gián tiếp (thông qua một hàm khác). Các bài toán đệ quy điển hình là: tìm số n!, Fibonacci. Chúng tôi đã giải quyết những vấn đề như vậy, nhưng sử dụng các vòng lặp, nghĩa là lặp đi lặp lại. Nói chung, mọi thứ được giải lặp lại đều có thể được giải bằng đệ quy, nghĩa là sử dụng hàm đệ quy. Toàn bộ giải pháp bắt nguồn từ việc giải quyết trường hợp chính hoặc, như nó còn được gọi là trường hợp cơ sở. Có một thứ gọi là bước đệ quy hoặc lệnh gọi đệ quy. Trong trường hợp hàm đệ quy được gọi để giải quyết một vấn đề phức tạp (không phải trường hợp cơ bản), một số lệnh gọi hoặc bước đệ quy được thực hiện để giảm vấn đề xuống đơn giản hơn. Và cứ như vậy cho đến khi chúng ta có được lời giải cơ bản. Hãy phát triển một chương trình khai báo hàm đệ quy tính n!

"stdafx.h" #include << "Enter n!: "; cin >>n; cout<< n << "!" << "=" << factorial(n) << endl; // вызов рекурсивной функции system("pause"); return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 cout << "Step\t" << i << endl; i++; // операция инкремента шага рекурсивных вызовов cout << "Result= " << result << endl; result = f * factorial(f - 1); // функция вызывает саму себя, причём её аргумент уже на 1 меньше return result; }

// mã Code::Khối

// Mã Dev-C++

// giai thừa.cpp: Xác định điểm vào cho ứng dụng bảng điều khiển. #bao gồm sử dụng không gian tên std; unsigned long int giai thừa(unsigned long int); // nguyên mẫu của hàm đệ quy int i = 1; // khởi tạo một biến toàn cục để đếm số lần gọi đệ quy unsigned long int result; // biến toàn cục để lưu trữ kết quả trả về của hàm đệ quy int main(int argc, char* argv) ( int n; // biến cục bộ để truyền số đã nhập từ bàn phím cout<< "Enter n!: "; cin >>n; cout<< n << "!" << "=" << factorial(n) << endl; // вызов рекурсивной функции return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 cout << "Step\t" << i << endl; i++; // операция инкремента шага рекурсивных вызовов cout << "Result= " << result << endl; result = f * factorial(f - 1); // функция вызывает саму себя, причём её аргумент уже на 1 меньше return result; }

TRONG dòng 7, 9, 21 Kiểu dữ liệu được khai báo unsigned long int , vì giá trị của giai thừa tăng rất nhanh, chẳng hạn đã là 10! = 3.628.800. Nếu kích thước của kiểu dữ liệu không đủ thì kết quả sẽ là giá trị sai hoàn toàn. Mã khai báo nhiều toán tử hơn mức cần thiết để tìm n!. Điều này được thực hiện để sau khi chạy, chương trình sẽ hiển thị những gì xảy ra ở mỗi bước của lệnh gọi đệ quy. Xin lưu ý các dòng mã được đánh dấu, dòng 23, 24, 28 là một giải pháp đệ quy cho n!. Dòng 23, 24 là nghiệm cơ bản của hàm đệ quy, tức là ngay khi giá trị của biến f sẽ bằng 1 hoặc 0 (vì chúng ta biết rằng 1! = 1 và 0! = 1), các lệnh gọi đệ quy sẽ dừng và các giá trị sẽ bắt đầu được trả về cho mỗi lệnh gọi đệ quy. Khi giá trị của lệnh gọi đệ quy đầu tiên trả về, chương trình sẽ trả về giá trị của giai thừa đã tính. TRONG dòng 28 hàm giai thừa() gọi chính nó, nhưng đối số của nó ít hơn một. Đối số được giảm bớt mỗi lần để đạt được một giải pháp cụ thể. Kết quả của chương trình (xem Hình 1).

Nhập n!: 5 Bước 1 Kết quả= 0 Bước 2 Kết quả= 0 Bước 3 Kết quả= 0 Bước 4 Kết quả= 0 5!=120

Hình 1 - Đệ quy trong C++

Dựa trên kết quả của chương trình, mỗi bước được hiển thị rõ ràng và kết quả ở mỗi bước bằng 0, ngoại trừ lệnh gọi đệ quy cuối cùng. Cần phải tính năm giai thừa. Chương trình đã thực hiện bốn lệnh gọi đệ quy và ở lệnh gọi thứ năm, trường hợp cơ bản đã được tìm thấy. Và khi chương trình đã có lời giải cho trường hợp cơ bản, nó sẽ giải quyết các bước trước đó và đưa ra kết quả tổng thể. Trong Hình 1, chỉ có bốn bước được hiển thị vì ở bước thứ năm, một giải pháp một phần đã được tìm thấy, giải pháp cuối cùng trả về giải pháp cuối cùng, tức là 120. Hình 2 hiển thị sơ đồ tính toán đệ quy 5!. Sơ đồ cho thấy rõ ràng rằng kết quả đầu tiên được trả về khi đạt được một giải pháp cụ thể, nhưng không phải ngay lập tức, sau mỗi lệnh gọi đệ quy.

Hình 2 - Đệ quy trong C++

Vậy tìm được 5! cần biết 4! và nhân nó với 5; 4! = 4 * 3! và như thế. Theo sơ đồ trong Hình 2, phép tính sẽ được rút gọn thành việc tìm một trường hợp đặc biệt, tức là 1!, sau đó các giá trị sẽ lần lượt được trả về cho từng lệnh gọi đệ quy. Cuộc gọi đệ quy cuối cùng sẽ trả về giá trị 5!.

Chúng ta hãy làm lại chương trình tìm giai thừa để có được bảng giai thừa. Để làm điều này, chúng ta sẽ khai báo một vòng lặp for trong đó chúng ta sẽ gọi hàm đệ quy.

sử dụng không gian tên std; unsigned long int giai thừa(unsigned long int); // nguyên mẫu của hàm đệ quy int i = 1; // khởi tạo một biến toàn cục để đếm số lần gọi đệ quy unsigned long int result; // biến toàn cục để lưu trữ kết quả trả về của hàm đệ quy int main(int argc, char* argv) ( int n; // biến cục bộ để truyền số đã nhập từ bàn phím cout<< "Enter n!: "; cin >>n; vì (int k = 1; k<= n; k++) { cout << k << "!" << "=" << factorial(k) << endl; // вызов рекурсивной функции } system("pause"); return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 //cout << "Step\t"<< i <>n; vì (int k = 1; k<= n; k++) { cout << k << "!" << "=" << factorial(k) << endl; // вызов рекурсивной функции } return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 //cout << "Step\t"<< i < << "Enter number from the Fibonacci series: "; cin >> <= entered_number; counter++) cout << setw(2) <

// mã Code::Khối

// Mã Dev-C++

// fibonacci.cpp: xác định điểm vào cho ứng dụng console. #bao gồm // thư viện định dạng thông tin hiển thị trên màn hình #include sử dụng không gian tên std; unsigned long fibonacci(unsigned long); // nguyên mẫu của hàm đệ quy để tìm kiếm các số từ dãy Fibonacci int main(int argc, char* argv) ( unsigned long enter_number; cout<< "Enter number from the Fibonacci series: "; cin >> số_đã nhập; for (int bộ đếm = 1; bộ đếm<= entered_number; counter++) cout << setw(2) <#bao gồm sử dụng không gian tên std; tháp void(int, int, int, int); // khai báo nguyên mẫu của hàm đệ quy int count = 1; // biến toàn cục để đếm số bước int _tmain(int argc, _TCHAR* argv) ( cout<< "Enter of numbers of disks: ";// введите количество дисков, которые надо переместить int number; cin >> số; cout<< "Enter the number of basic rod: "; // введите номер стержня, на котором диски будут находится изначально int basic_rod; cin >> basic_rod; cout<< "Enter the number of final rod: "; // введите номер стержня, на который необходимо переместить диски int final_rod; cin >> cuối cùng_rod; int help_rod; // khối xác định số lượng thanh phụ, phân tích số lượng thanh đầu và cuối if (basic_rod != 2 && Final_rod != 2) help_rod = 2; khác nếu (basic_rod != 1 && Final_rod != 1) help_rod = 1; khác nếu (basic_rod != 3 && Final_rod != 3) help_rod = 3; tower(// khởi chạy hàm đệ quy để giải số bài toán Tháp Hà Nội, // một biến lưu trữ số lượng đĩa cần di chuyển basic_rod, // một biến lưu trữ số lượng thanh mà ban đầu các đĩa sẽ được di chuyển định vị help_rod , // một biến lưu trữ số lượng của thanh, được sử dụng làm Final_rod phụ trợ); // biến lưu trữ số lượng thanh mà các đĩa cần được di chuyển system("pause"); trả về 0; ) void tower(int count_disk, int baza, int help_baza, int new_baza) ( if (count_disk == 1) // điều kiện để kết thúc cuộc gọi đệ quy ( cout<< setw(2) << count << ") "<< baza << " " << "->" << " " << new_baza << endl; count++; } else { tower(count_disk -1, baza, new_baza, help_baza); // перемещаем все диски кроме самого последнего на вспомогательный стержень tower(1, baza, help_baza, new_baza); // перемещаем последний диск с начального стержня на финальный стержень tower(count_disk -1, help_baza, baza, new_baza); // перемещаем все диски со вспомогательного стержня на финальный } }

// mã Code::Khối

// Mã Dev-C++

// hanoi_tower.cpp: Xác định điểm vào cho ứng dụng console. // Chương trình giải đệ quy bài toán Tháp Hà Nội #include #bao gồm sử dụng không gian tên std; tháp void(int, int, int, int); // khai báo nguyên mẫu của hàm đệ quy int count = 1; // biến toàn cục để đếm số bước int main() ( cout<< "Enter of numbers of disks: ";// введите количество дисков, которые надо переместить int number; cin >> số; cout<< "Enter the number of basic rod: "; // введите номер стержня, на котором диски будут находится изначально int basic_rod; cin >> basic_rod; cout<< "Enter the number of final rod: "; // введите номер стержня, на который необходимо переместить диски int final_rod; cin >> cuối cùng_rod; int help_rod; // khối xác định số lượng thanh phụ, phân tích số lượng thanh đầu và cuối if (basic_rod != 2 && Final_rod != 2) help_rod = 2; khác nếu (basic_rod != 1 && Final_rod != 1) help_rod = 1; khác nếu (basic_rod != 3 && Final_rod != 3) help_rod = 3; tower(// khởi chạy hàm đệ quy để giải số bài toán Tháp Hà Nội, // một biến lưu trữ số lượng đĩa cần di chuyển basic_rod, // một biến lưu trữ số lượng thanh mà ban đầu các đĩa sẽ được di chuyển định vị help_rod , // một biến lưu trữ số lượng của thanh, được sử dụng làm một Final_rod phụ trợ); // biến lưu trữ số lượng thanh mà các đĩa cần được di chuyển return 0; ) void tower(int count_disk, int baza, int help_baza, int new_baza) ( if (count_disk == 1) // điều kiện để kết thúc cuộc gọi đệ quy ( cout<< setw(2) << count << ") "<< baza << " " << "->" << " " << new_baza << endl; count++; } else { tower(count_disk -1, baza, new_baza, help_baza); // перемещаем все диски кроме самого последнего на вспомогательный стержень tower(1, baza, help_baza, new_baza); // перемещаем последний диск с начального стержня на финальный стержень tower(count_disk -1, help_baza, baza, new_baza); // перемещаем все диски со вспомогательного стержня на финальный } }

Hình 5 thể hiện một ví dụ về chương trình đệ quy Tháp Hà Nội. Đầu tiên, chúng tôi nhập số đĩa bằng ba, sau đó chúng tôi nhập thanh cơ sở (đầu tiên) và chỉ định thanh cuối cùng (thứ ba). Tự động thanh thứ hai trở thành thanh phụ. Chương trình tạo ra kết quả hoàn toàn trùng khớp với giải pháp hoạt hình cho vấn đề này.

Nhập số đĩa: 3 Nhập số thanh cơ bản: 1 Nhập số thanh cuối cùng: 3 1) 1 -> 3 2) 1 -> 2 3) 3 -> 2 4) 1 -> 3 5) 2 -> 1 6) 2 -> 3 7) 1 -> 3

Hình 5 - Đệ quy trong C++

Từ hình vẽ có thể thấy rằng đầu tiên đĩa di chuyển từ thanh 1 sang thanh 3, sau đó từ thanh 1 sang thanh 2, từ thanh 3 sang thanh 3.hai, v.v. Nghĩa là, chương trình chỉ hiển thị trình tự chuyển động của đĩa và số bước tối thiểu mà tất cả các đĩa sẽ được di chuyển.

Tất cả những vấn đề này có thể được giải quyết lặp đi lặp lại. Câu hỏi được đặt ra là: “Giải quyết theo phương pháp lặp hay đệ quy, cái nào tốt hơn?” Tôi trả lời: “Nhược điểm của đệ quy là nó tiêu tốn nhiều tài nguyên máy tính hơn so với phép lặp. Điều này dẫn đến tải nặng cho cả RAM và bộ xử lý. Nếu rõ ràng là một vấn đề cụ thể có thể được giải theo cách lặp đi lặp lại thì nó nên được sử dụng theo cách khác, sử dụng đệ quy!” Tùy thuộc vào vấn đề đang được giải quyết, độ phức tạp của việc viết chương trình sẽ thay đổi khi sử dụng phương pháp giải này hoặc phương pháp giải khác. Nhưng thường xuyên hơn, một vấn đề được giải quyết bằng phương pháp đệ quy từ quan điểm về khả năng đọc mã sẽ rõ ràng và ngắn gọn hơn nhiều.

Xin chào Habrahabr!

Trong bài viết này chúng ta sẽ nói về các vấn đề đệ quy và cách giải quyết chúng.

Nói ngắn gọn về đệ quy

Đệ quy là một hiện tượng khá phổ biến xảy ra không chỉ trong lĩnh vực khoa học mà còn trong đời sống hàng ngày. Ví dụ: hiệu ứng Droste, tam giác Sierpinski, v.v. Một cách để xem đệ quy là hướng camera Web vào màn hình điều khiển máy tính, một cách tự nhiên, sau khi bật nó lên trước. Như vậy, camera sẽ ghi lại hình ảnh của màn hình máy tính và hiển thị lên màn hình này, nó sẽ giống như một vòng khép kín. Kết quả là chúng ta sẽ quan sát thấy thứ gì đó tương tự như một đường hầm.

Rất nhiều điều đã được nói về sự đệ quy. Dưới đây là một số tài nguyên tốt:

Đệ quy và các vấn đề đệ quy. Các lĩnh vực ứng dụng đệ quy

Giả định rằng về mặt lý thuyết, người đọc đã quen thuộc với đệ quy và biết nó là gì. Trong bài viết này chúng ta sẽ chú ý hơn tới các bài toán đệ quy.

Nhiệm vụ

Khi học đệ quy, cách hiểu đệ quy hiệu quả nhất là giải quyết vấn đề.

Làm thế nào để giải quyết vấn đề đệ quy?

Trước hết, bạn cần hiểu rằng đệ quy là một dạng quá mức cần thiết. Nói chung, mọi thứ được giải lặp lại đều có thể được giải bằng đệ quy, nghĩa là sử dụng hàm đệ quy.

từ mạng

Bất kỳ thuật toán nào được thực hiện ở dạng đệ quy đều có thể được viết lại ở dạng lặp và ngược lại. Câu hỏi đặt ra là liệu điều này có cần thiết hay không và nó sẽ hiệu quả đến mức nào.

Những lập luận sau đây có thể được đưa ra để biện minh cho điều này.

Để bắt đầu, chúng ta có thể nhớ lại các định nghĩa về đệ quy và lặp lại. Đệ quy là một cách tổ chức xử lý dữ liệu trong đó chương trình gọi chính nó trực tiếp hoặc với sự trợ giúp của các chương trình khác. Lặp lại là một cách tổ chức xử lý dữ liệu trong đó một số hành động nhất định được lặp lại nhiều lần mà không dẫn đến lệnh gọi chương trình đệ quy.

Sau đó, chúng ta có thể kết luận rằng chúng có thể thay thế cho nhau, nhưng không phải lúc nào cũng có cùng chi phí về tài nguyên và tốc độ. Để chứng minh điều này, chúng ta có thể đưa ra ví dụ sau: có một hàm trong đó để tổ chức một thuật toán nhất định, có một vòng lặp thực hiện một chuỗi hành động tùy thuộc vào giá trị hiện tại của bộ đếm (nó có thể không phụ thuộc vào Nó). Vì có một chu trình, có nghĩa là cơ thể lặp lại một chuỗi hành động - sự lặp lại của chu trình. Bạn có thể di chuyển các thao tác vào một chương trình con riêng biệt và chuyển cho nó giá trị bộ đếm, nếu có. Sau khi hoàn thành việc thực hiện chương trình con, chúng tôi kiểm tra các điều kiện để thực hiện vòng lặp và nếu nó đúng, chúng tôi tiến hành gọi chương trình con mới; nếu sai, chúng tôi hoàn thành việc thực thi. Bởi vì Chúng ta đặt tất cả nội dung của vòng lặp vào một chương trình con, nghĩa là điều kiện để thực hiện vòng lặp cũng được đặt trong chương trình con và có thể lấy được thông qua giá trị trả về của hàm, các tham số được truyền bằng tham chiếu hoặc con trỏ tới chương trình con , cũng như các biến toàn cục. Hơn nữa, thật dễ dàng để chỉ ra rằng một lệnh gọi đến một chương trình con nhất định từ một vòng lặp có thể dễ dàng được chuyển đổi thành một lệnh gọi hoặc không gọi (trả về một giá trị hoặc đơn giản là hoàn thành công việc) của một chương trình con từ chính nó, được hướng dẫn bởi một số điều kiện (những điều kiện mà trước đây ở trạng thái vòng lặp). Bây giờ, nếu bạn nhìn vào chương trình trừu tượng của chúng tôi, nó gần giống như chuyển các giá trị cho một chương trình con và sử dụng chúng, chương trình con sẽ thay đổi khi nó kết thúc, tức là. chúng tôi đã thay thế vòng lặp bằng lệnh gọi đệ quy đến một chương trình con để giải một thuật toán nhất định.

Nhiệm vụ đưa đệ quy vào một cách tiếp cận lặp lại là có tính đối xứng.

Tóm lại, chúng ta có thể bày tỏ những suy nghĩ sau: đối với mỗi cách tiếp cận, có một loại nhiệm vụ riêng, được xác định bởi các yêu cầu cụ thể cho một nhiệm vụ cụ thể.

Bạn có thể tìm hiểu thêm về điều này

Cũng giống như một phép liệt kê (chu trình), đệ quy phải có điều kiện dừng - Trường hợp cơ sở (nếu không, cũng giống như một chu trình, đệ quy sẽ hoạt động mãi mãi - vô hạn). Điều kiện này là trường hợp đệ quy đi tới (bước đệ quy). Ở mỗi bước, một hàm đệ quy được gọi cho đến khi lệnh gọi tiếp theo kích hoạt điều kiện cơ bản và quá trình đệ quy dừng lại (hay nói đúng hơn là quay lại lệnh gọi hàm cuối cùng). Toàn bộ giải pháp bắt nguồn từ việc giải quyết trường hợp cơ bản. Trong trường hợp hàm đệ quy được gọi để giải quyết một vấn đề phức tạp (không phải trường hợp cơ bản), một số lệnh gọi hoặc bước đệ quy được thực hiện để giảm vấn đề xuống đơn giản hơn. Và cứ như vậy cho đến khi chúng ta có được lời giải cơ bản.

Vì vậy hàm đệ quy bao gồm

Điều kiện dừng hoặc trường hợp cơ sở
Điều kiện tiếp tục hoặc bước đệ quy là một cách để giảm bớt vấn đề thành những vấn đề đơn giản hơn.

Hãy xem xét điều này bằng cách sử dụng ví dụ về việc tìm giai thừa:

Giải pháp lớp công khai ( public static int recursion(int n) ( // thoát điều kiện // Trường hợp cơ sở // khi nào dừng lặp lại đệ quy? if (n == 1) ( return 1; ) // Bước đệ quy / trả về điều kiện đệ quy đệ quy( n - 1) * n; ) public static void main(String args) ( System.out.println(recursion(5)); // gọi hàm đệ quy ) )

Ở đây điều kiện cơ bản là điều kiện khi n=1. Vì chúng ta biết rằng 1!=1 và để tính 1! chúng tôi không cần bất cứ điều gì. Để tính 2! chúng ta có thể sử dụng 1!, tức là 2!=1!*2. Để tính 3! chúng ta cần 2!*3... Để tính n! chúng ta cần (n-1)!*n. Đây là bước đệ quy. Nói cách khác, để lấy giá trị giai thừa của một số n, chỉ cần nhân giá trị giai thừa của số trước đó với n là đủ.

Thẻ: