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


Problem

5/12

Đệ quy và lặp lại

Theory Click to read/hide

Đệ quy và phép lặp
Để hiểu đệ quy, bạn cần hiểu đệ quy...
 
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.

Problem

Xác định một hàm K(n) trả về số chữ số trong một số tự nhiên đã cho n dưới dạng

\(\begin{equation*} K(n) = \begin{cases} 1 &\text{if n < 10}\\ K(n / 10) + 1 &\text{if n >= 10} \end{cases} \end{equation*}\).

Viết hàm đệ quy để tính số chữ số của một số tự nhiên n sử dụng tỷ lệ trê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
}   

     

Program check result

To check the solution of the problem, you need to register or log in!