Module: chương trình con. đệ quy

Đệ quy và phép lặp

Lặp lại trong lập trình - một bướccủa quy trình xử lý dữ liệu tuần hoàn. 
Thông thường các thuật toán lặp ở bước hiện tại (lặp) sử dụng kết quả của cùng một thao tác hoặc hành động được tính ở các bước trước đó.  Một ví dụ về các phép tính như vậy là phép tính các quan hệ lặp lại. 
Một ví dụ đơn giản về giá trị đệ quy là giai thừa: \(N!=1 \cdot 2 \cdot 3 \cdot \ ... \ \cdot N\).
Phép tính giá trị ở mỗi bước (lặp lại) là \(N=N \cdot i\) .  Khi tính giá trị của \(N\), chúng tôi lấy giá trị đã được lưu trữ \(N\).

Giai thừa của một số cũng có thể được mô tả bằng cách sử dụng công thức truy hồi:
\(\begin{equation*} n!= \begin{cases} 1 &\text{n <= 1,}\\ (n-1)! \cdot n &\text{n > 1.} \end{cases} \end{equation*}\)

Bạn có thể nhận thấy rằng mô tả này không gì khác hơn là một hàm đệ quy.
Ở đây, dòng đầu tiên (\(n <= 1\)) là trường hợp cơ sở (điều kiện kết thúc đệ quy) và dòng thứ hai là chuyển tiếp sang bước tiếp theo.  
 
Bạn nên hiểu rằng các lệnh gọi hàm liên quan đến một số chi phí bổ sung, do đó phép tính giai thừa không đệ quy sẽ nhanh hơn một chút. 

Kết luận:chỗ bạn có thể viết chương trình với thuật toán lặp đơn giản, không đệ quy, thì bạn cần viết không đệ quy. Tuy nhiên, có rất nhiều bài toán mà quá trình tính toán chỉ được thực hiện bằng đệ quy.
Mặt khác, thuật toán đệ quy thường dễ hiểu hơn.

Hàm giai thừa đệ quy	Thuật toán lặp
static int Factorial(int n){ nếu (n > 1) trả về n * Giai thừa (n - 1); khác trả lại 1; }	int x = 1; cho (int i = 2; i <= n; i++) x = x * i; Console.WriteLine("%d", x);

1	using System;
2	class Program
3	{
4	static int countDigits(int n)
5	{
6	// напишите условие окончание рекурсии
7
8
9
10	return 1 + countDigits(n / 10);
11	}
12	static void Main()
13	{
14	int n = Convert.ToInt32(Console.ReadLine());
15	Console.WriteLine(countDigits(n));
16	}
17	}