Contents
Đệ quy là gì?
Khi một thủ tục đệ quy được lặp lại, nó được gọi là đệ quy . Đệ quy là một loại hàm hoặc biểu thức nêu một số khái niệm hoặc thuộc tính của một hoặc nhiều biến, được chỉ định bởi một thủ tục mang lại các giá trị hoặc phiên bản của hàm đó bằng cách áp dụng lặp đi lặp lại một quan hệ đã cho hoặc phép toán thông thường cho các giá trị đã biết của hàm.
Hoặc là
Một hàm gọi chính nó từ giá trị trước đó của nó để tạo ra giá trị tiếp theo.
Hoặc là
Một hàm gọi chính nó trong quá trình thực thi.
Bạn có thể hiểu khái niệm đệ quy bằng cách lấy một ví dụ thực tế. Giả sử bạn đang đi một cầu thang để đi từ tầng trệt lên tầng một. Vì vậy, bạn thực hiện từng bước một ở đây. Bạn chỉ có thể đạt được bước thứ hai khi bạn đã bước đầu tiên. Một lần nữa để đạt được bước thứ ba, bạn phải thực hiện bước thứ hai trước. Đây là quá trình lặp lại. Với mỗi bước tiếp theo, bạn đang thêm các bước trước đó dưới dạng một chuỗi lặp lại với sự khác biệt chung giữa mỗi bước. Đây là ý nghĩa của đệ quy.
Bước 2 = Bước 1 + tầng trệt
Bước 3 = Bước 2 + bước 1 + tầng trệt
Và như thế.
Ví dụ phổ biến nhất mà chúng ta có thể lấy là tập hợp các số tự nhiên, bắt đầu từ một cho đến vô cùng, tức là 1,2,3,4,5,6,7,…., ∞ . Do đó, trong dãy số tự nhiên, mỗi số hạng có một điểm khác biệt chung giữa chúng là 1, có nghĩa là mỗi lần số hạng tiếp theo gọi số hạng trước của nó sẽ được thực hiện.
Hàm được xác định đệ quy là gì?
Đối với bất kỳ hàm được định nghĩa đệ quy nào, nó có hai phần. Phần đầu tiên là định nghĩa của đối số nhỏ nhất và phần thứ hai là định nghĩa của số hạng thứ n. Đối số nhỏ nhất thường được ký hiệu là f (0) hoặc f (1) và đối số thứ n được ký hiệu là f (n).
Bây giờ, chúng ta hãy hiểu hàm được định nghĩa đệ quy với sự trợ giúp của một ví dụ.
Cho dãy số là 5, 7, 9, 11
Công thức rõ ràng cho dãy đã cho là f (n) = 2n + 5
Công thức đệ quy cho dãy đã cho được đưa ra bởi
f (0) = 5
f (n) = f (n-1) +2
Bây giờ, chúng ta có thể kiểm tra các số hạng trình tự bằng cách sử dụng công thức đệ quy như sau:
f (0) = 5
f (1) = f (0) +2
f (1) = 5 + 2 = 7
f (2) = f (1) +2
f (2) = 7 + 2 = 9
f (3) = f (2) +2
f (3) = 9 + 2 = 11
Bằng cách này, chúng ta có thể tìm số hạng tiếp theo trong dãy với sự trợ giúp của công thức hàm đệ quy.
Điều gì làm cho hàm đệ quy?
Để làm cho hàm đệ quy, nó yêu cầu số hạng riêng của nó để tìm ra số hạng tiếp theo trong chuỗi. Ví dụ, nếu chúng ta muốn tìm số hạng thứ n trong dãy, chúng ta cần biết số hạng trước và số hạng đứng trước số hạng trước đó. Do đó, chúng ta cần biết số hạng trước đó để xác định xem chuỗi là đệ quy hay không đệ quy. Vì vậy, chúng ta có thể nói rằng, nếu hàm yêu cầu số hạng trước để tìm số hạng tiếp theo trong dãy, thì hàm là một hàm đệ quy. Hầu hết các hàm đệ quy sẽ cung cấp giá trị đầu của dãy và công thức giúp tạo ra các số hạng tiếp theo trong dãy.
Công thức hàm đệ quy
Nếu a 1 , a 2 , a 3 , a 4 ,… .., a n ,… là một tập hợp các chuỗi hoặc một dãy. Sau đó, một công thức đệ quy cho dãy này sẽ yêu cầu tính tất cả các số hạng trước đó và tìm giá trị của một n .
tức là a n = a n-1 + a 1
Công thức này cũng có thể được định nghĩa là Công thức đệ quy dãy số học . Như bạn có thể thấy từ chính dãy số, nó là một dãy Số học , bao gồm số hạng đầu tiên theo sau là các số hạng khác và sự khác biệt chung giữa mỗi số hạng là số bạn cộng hoặc trừ chúng.
Một hàm đệ quy cũng có thể được xác định cho một dãy hình học , trong đó các số hạng trong dãy có nhân tử chung hoặc tỷ lệ chung giữa chúng. Và nó có thể được viết là;
a n = r × a n-1
Nói chung, hàm đệ quy được định nghĩa thành hai phần. Nó là một tuyên bố của số hạng đầu tiên cùng với công thức / quy tắc liên quan đến các số hạng kế tiếp.
Làm thế nào để viết một công thức đệ quy cho dãy số học?
Thực hiện các bước sau để tìm công thức đệ quy cho dãy số học:
Bước 1: Xác định xem dãy đã cho là cấp số cộng. (Cộng hoặc trừ hai số hạng kế tiếp nhau. Nếu ta lấy một số hạng bằng nhau từ số hạng này đến số hạng tiếp theo thì dãy đó là cấp số cộng).
Bước 2: Tìm công sai chung của dãy số đã cho.
Bước 3: Lập công thức đệ quy bằng cách nêu số hạng đầu tiên, sau đó lập công thức là số hạng trước + hiệu chung.
Do đó, công thức đệ quy cho dãy số học được đưa ra là:
a n = a n-1 + d
Hãy xem xét chuỗi: 2, 4, 6, 8, 10,…
Dãy số trên là dãy số học vì mỗi số hạng trong dãy được tăng thêm 2. Do đó, hiệu chung là 2. Do đó, công thức đệ quy cho dãy là a n = a n-1 + 2.
Giải trình:
Đây, a 1 = 2
Như vậy, a 2 = a (2-1) +2 = a 1 +2 = 2 + 2 = 4
a 3 = a (3-1) +2 = a 2 + 2 = 4 + 2 = 6
a 4 = a (4-1) +2 = a 3 + 2 = 6 + 2 = 8, và quá trình tiếp tục.
Làm thế nào để viết một công thức đệ quy cho dãy hình học?
Thực hiện các bước sau để tìm công thức đệ quy cho dãy hình học:
Bước 1: Xác định xem dãy đã cho có phải là hình học hay không. (Nhân hoặc chia mỗi số hạng với một số. Nếu chúng ta nhận được cùng một số tiền từ số hạng này đến số hạng tiếp theo, thì dãy đó là hình học.)
Bước 2: Tìm tỉ số chung của dãy số đã cho.
Bước 3: Lập công thức đệ quy bằng cách nêu số hạng đầu tiên, sau đó lập công thức là tỉ số chung của số hạng trước.
Do đó, công thức đệ quy cho dãy hình học được đưa ra là:
a n = r. một n-1
Hãy xem xét dãy số: 3, 15, 75, 375,…
Dãy số trên là dãy hình học vì số hạng kế tiếp trong dãy có được bằng cách nhân 5 với số hạng trước đó. Do đó, tỷ lệ chung là 5. Do đó, công thức đệ quy cho dãy là a n = 5. a n-1 .
Giải trình:
Đây, a 1 = 3
Như vậy, a 2 = a (2-1) .5 = a 1 .5 = 3 (5) = 15
a 3 = a (3-1) .5 = a 2 .5 = 15 (5) = 75
a 4 = a (4-1) .5 = a 3 .5 = 75 (5) = 375, và quá trình tiếp tục.
Ví dụ về hàm đệ quy
Ví dụ 1:
Cho a 1 = 10 và a n = 2a n-1 + 1
Vì vậy, chuỗi trở thành;
- a 1 = 10
- a 2 = 2a 1 + 1 = 21
- a 3 = 2a 2 + 1 = 43
- a 4 = 2a 3 + 1 = 87
- và như thế.
Ví dụ 2:
Tìm công thức đệ quy cho dãy 3, 6, 12, 24, 48, 96.
Giải pháp:
Cho dãy, 3, 6, 12, 24, 48, 96,…
Dãy đã cho là dãy hình học vì nếu nhân số hạng đứng trước với 2 thì ta được các số hạng kế tiếp.
Để tìm công thức đệ quy cho dãy đã cho, hãy viết nó dưới dạng bảng.
| Số thuật ngữ | Thuật ngữ trình tự | Ký hiệu chức năng | Ký hiệu chỉ số |
| 1 | 3 | f (1) | một 1 |
| 2 | 6 | f (2) | một 2 |
| 3 | 12 | f (3) | và 3 |
| 4 | 24 | f (4) | một 4 |
| 5 | 48 | f (5) | một 5 |
| 6 | 96 | f (6) | và 6 |
| n | .
. |
f (n) | một n |
Do đó, công thức đệ quy trong ký hiệu hàm được đưa ra là:
f (1) = 3, f (n) = 2. f (n-1)
Trong ký hiệu chỉ số con, công thức đệ quy được đưa ra bởi:
a 1 = 3, a n = 2.a n-1
Những điểm cần nhớ để tìm ra công thức đệ quy
- Các hàm đệ quy gọi hàm riêng của chúng cho các thuật ngữ kế tiếp.
- Luôn luôn kiểm tra loại của dãy số đó là số học hay hình học, nghĩa là số được cộng hoặc trừ trong số hạng tiếp theo của dãy với một hiệu số chung hoặc chúng được nhân và có nhân tử chung giữa chúng tương ứng.
- Tìm ra sự khác biệt chung cho dãy số và nhân tử chung cho dãy hình học giữa mỗi số hạng trong dãy tương ứng.
- Sau đó, viết công thức đệ quy dựa trên số hạng đầu tiên và các số hạng kế tiếp và hiệu chung hoặc nhân tử chung giữa chúng cho cả chuỗi.
Các vấn đề thực hành về hàm đệ quy
Giải các bài toán sau trên hàm đệ quy:
- Tìm công thức đệ quy cho dãy số: 4, 8, 12, 16, 20, 24, 28,…
- Tìm công thức đệ quy trong ký hiệu hàm cho dãy: 5, 10, 15, 20, 25,…
Các câu hỏi thường gặp về hàm đệ quy
Hàm đệ quy nghĩa là gì?
Hàm sử dụng số hạng trước để tìm số hạng tiếp theo trong dãy được gọi là hàm đệ quy.
Đề cập đến hai phần được sử dụng trong công thức hàm đệ quy?
Hàm đệ quy có hai phần. Phần đầu tiên là định nghĩa của đối số nhỏ nhất và phần thứ hai là định nghĩa của số hạng thứ n.
Hàm đệ quy của dãy Fibonacci là gì?
Hàm đệ quy của dãy Fibonacci là
f (n) = f (n-2) + f (n-1)
Trong đó f (1) = 1, f (2) = 1
Công thức hàm đệ quy cho dãy 1, 1, 2, 6, 24, 120 là gì?
Hàm đệ quy cho dãy 1, 1, 2, 6, 24, 120 là f (n) = n. f (n-1), trong đó f (0) = 1.
Làm thế nào để viết công thức đệ quy?
Công thức đệ quy được viết dựa trên số hạng đầu tiên, các số hạng kế tiếp và hiệu số chung hoặc tỉ số chung của dãy số.
