Khái niệm đệ quy

1. Khái niệm đệ quy
Một đối tượng là đệ quy nếu nó được định nghĩa qua chính nó hoặc qua một đối tượng khác cùng dạng với nó bằng quy nạp.
Nếu lời giải của một bài toán P thực hiện bằng lời giải của bài toán P’ có dạng giống như P thì đó là một lời giải đệ quy. Nói cách khác, đệ quy trong tin học là dạng hồi quy trong toán học.
Một thủ tục (hàm) đệ quy gồm 2 phần:
 Phần neo (điều kiện dừng): phần nay thực hiện khi công việc đơn giản, có thể giải trực tiếp được.
 Phần đệ quy (lời gọi đệ quy): trong trường hợp bài toán chưa giải được bằng phần neo, ta xác định các bài toán con và gọi lại chính thủ tục (hàm) của nó với tham số khác để giải những các bài toán con đó.
Phần đệ quy thể hiện tính hồi quy của lời giải. Trong một thủ tục (hàm) đệ quy phải có đủ hai phần trên. Nếu không có phần neo thì thủ tục (hàm) sẽ thực hiện vô hạn. Vì vậy, nó rất quan trọng trong việc xác định tính hữu hạn của lời giải.
2. Phân loại đệ quy
2.1 Đệ quy tuyến tính
Đệ quy tuyến tính là loại đệ quy đơn giản và có độ phức tạp dạng đa thức.
Cú pháp:

Ví dụ: Tính n! được định nghĩa đệ quy như sau:
2.2 Đệ quy nhị phân
Dạng đệ quy này cũng đơn giản và có độ phức tạp dạng đa thức. Sự phân cấp biến nhớ trong quá trình xử lý phát triển theo dạng cây nhị phân.
Cú pháp:

Ví dụ:
2.3 Đệ quy phi tuyến
Dạng đệ quy này tương đối phức tạp và thường được sử dụng trong thuật toán quay lui vét cạn. Tùy theo độ khó của bài toán mà ta xác định độ phức tạp của chương trình, hầu hết dạng đệ quy này có độ phức tạp dạng hàm mũ.
Cú pháp 1:

Cú pháp 2:

Kỹ thuật xử lý và các bài tập của đệ quy phi tuyến sẽ bàn chi tiết thông qua từng bài toán trong thuật toán quay lui vét cạn.
2.4 Đệ quy hỗ tương
Dạng đệ quy này khá thú vị, thể hiện tính tương tác đệ quy giữa các đối tuợng cùng xử lý một bài toán với những trường hợp riêng. Tùy thuộc vào dạng toán xử lý ta tính được độ phức tạp của bài toán.
Cú pháp:

1)Tính S(n) = 1 + 2 + 3 + ... + n - 1 + n
2)Tính S(n) = 1^2 + 2^2 + 3^2 + ... + (n-1)^2 + n^2
3)Tính S(n) = 1 + 1/2 + 1/3 + ... + 1/n
4)Tính S(n) = 1/2 + 1/4 + ... + 1/2n
5)Tính S(n) = 1 + 1/3 + 1/5 + ... + 1/(2n+1)
6)Tính S(n) = 1/(1*2) + 1/(2*3) + 1/( n(*n-1) )
7)Tính S(n) = 1/2 + 2/3 + 3/4 + ... + n/(n+1)
8)Tính S(n) = 1/2 + 3/4 + 5/6 + ... + (2n+1)/(2n+2)
9)Tính T(n) = 1*2*3*.....*n
10)Tính T(x,n) = x^n
11)Tính S(n) = 1 + 1.2 + 1.2.3 + .... + 1.2.3....n
12)Tính S(x,n) = x + x^2 + x^3 + ... + x^n
13)Tính S(x,n) = x^2 + x^4 +.... + x^2n
14)Tính S(x,n) = x + x^3 + x^5 +....+ x^(2n+1)
15)Tính S(n) = 1 + 1/(1+2) + 1/(1+2+3) + ... + 1/(1+2+3+...+n)
16)Tính S(x,n) = x + (x^2)/2! + (x^3)/3! + ... + (x^n)/n!
17)Tính S(x,n) = 1 + (x^2)/2! + (x^4)/4! + ... + (x^2n)/(2n)!
18)Tìm ước số lẻ lớn nhất của số nguyên dương n . Ví dụ : n = 100 ước lẻ lớn nhất của 100 là 25
19)Tính S(n) = sqrt(2 + sqrt (2 + ... sqrt ( 2 + sqrt(2) ) ) )
20)Tính S(n) = sqrt(n + sqrt (n-1 + sqrt(n-2 + ...sqrt(2 + sqrt (1) ) ) ) )
21)Tính S(n) = sqrt(1 + sqrt(2 + sqrt (3 + ...sqrt (n-1 + sqrt (n)))))
22)S(n) = 1/(1 + 1/(1 + 1/(1 + 1/(... 1 /(1/(1 + 1/(1 + 1 )))))))
23)Hãy đếm số lượng chữ số của số nguyên dương n
24)Hãy tính tổng các chữ số của số nguyên dương n
25)Hãy tính tích các chữ số của số nguyên dương n
26)Hãy đếm số lượng chữ số lẻ của số nguyên dương n
27)Hãy tính tổng các chữ số chẵn của số nguyên dương n
28)Hãy tính tích các chữ số lẻ của số nguyên dương n
29)Cho số nguyên dương n . Hãy tìm chữ số đầu tiên của n
30)Hãy tìm chữ số đảo ngược của số nguyên dương n
31)Tìm chữ số lớn nhất của số nguyên dương n
32)Tìm chữ số nhỏ nhất của số nguyên dương n
33)Hãy kiểm tra số nguyên dương n có toàn chữ số lẻ hay không ?
34)Hãy kiểm tra số nguyên dương n có toàn chữ số chẵn hay không ?