# Cơ bản về đệ quy (recursion) và giải thuật đệ quy [toc] ## I. Định nghĩa về đệ quy Đệ quy là một phương pháp giải bài toán lớn dựa trên kết quả của các bài toán nhỏ hơn. ## II. Giải thuật đệ quy > Một bài toán $P$ được gọi là có tính chất đệ quy khi lời giải của nó có thể đưa về lời giải của bài toán $P'$ nhỏ hơn nó và có dạng giống nó, đồng thời lời giải của $P'$ không cần dùng tới $P$. Lời giải cho những bài toán như vậy được gọi là giải thuật đệ quy. Bản chất của giải thuật đệ quy là phân tách một bài toán lớn thành những bài toán nhỏ hơn và dễ giải hơn, sau đó tìm cách kết hợp lời giải của các bài toán nhỏ lại thành lời giải cho bài toán lớn ban đầu. > Theo [Viblo](https://viblo.asia/p/de-quy-va-giai-thuat-de-quy-gGJ5969JKX2). Ví dụ với bài toán tìm số Fibonacci thứ $n$ > Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử 0 hoặc 1 và 1, các phần tử sau đó được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng hai phần tử trước nó. > Theo [Wikipedia](https://vi.wikipedia.org/wiki/D%C3%A3y_Fibonacci). Gọi $f(n)$ là số Fibonacci thứ $n$, thì ta có công sau dựa trên nhưng quy luật của số Fibonacci: $f(n) = f(n - 1) + f(n - 2)$ $f(1) = 1$ $f(2) = 1$ Hai số đầu tiên của dãy số Fibonacci là $1$ và $1$ nên ta có $f(1) = 1$ và $f(2) = 1$. Với $n \ge 2$, số Fibonacci thứ $n$ là tổng của $2$ số Fibonacci liền trước nó. Ta có thể thấy, số Fibonacci thứ $n - 1$ (là số Fibonacci liền trước số Fibonacci thứ $n$) là $f(n - 1)$ và số Fibonacci thứ $n - 2$ (là số Fibonacci gần cuối số Fibonacci thứ $n$) là $f(n - 2)$. Vậy nên, $f(n) = f(n - 1) + f(n - 2)$. Ta có công thức $f(n) = f(n - 1) + f(n - 2)$. Đây là công thức truy hồi trong một bài toán đệ quy. Bài toán tìm $f(n)$ sẽ phải phụ thuộc vào một hoặc nhiều các bài toán nhỏ hơn chẳng hạn như $f(n - 1)$ và $f(n - 2)$ trong bài toán trên. ## III. Công thức truy hồi và trường hợp cơ sở Trong một bài toán đệ quy, luôn có 2 thành phần: **công thức truy hồi** và **trường hợp cơ sở**. ### 1. Trường hợp cơ sở là gì? *Trường hợp cơ sở* là trường hợp mà bài toán nhỏ tới mức cực tiểu. Nghĩa là bài toán con lúc ấy không thể chia nhỏ hơn. Lúc ấy, kết quả của bài toán thường là một giá trị cố định tùy theo yêu cầu của đề bài. Ví dụ như trong bài toán tìm số Fibonacci thứ $n$ ở trên, có 2 trường hợp cơ sở là $f(1) = 1$ và $f(2) = 1$. ### 2. Công thức truy hồi là gì? *Công thức truy hồi* là công thức tính bài toán lớn dựa theo kết quả của những bài toán con. Ví dụ như ở trong bài toán tìm số Fibonacci thứ $n$, ta có công thức truy hồi là $f(n) = f(n - 1) + f(n - 2)$. $f(n)$ là kết quả của bài toán lớn, từ bài toán lớn đó truy hồi xuống những bài toàn nhỏ hơn tới khi gặp *trường hợp cơ sở* thì ngưng. ## IV. Cài đặt giải thuật đệ quy trong lập trình Những giải thuật đệ quy thường được khai triển trong lập trình thông qua hàm. Trong bài viết này, ta sẽ cài đặt bài toán tìm số Fibonacci thứ $n$ bằng ngôn ngữ lập trình C++ và Python. Ta sẽ định nghĩa hàm ```fib``` với ```fib(n)``` là kết quả của $f(n)$ (số Fibonacci thứ n). Ngôn ngữ: C++ ```cpp= int fib(int n) { if (n == 1) // Trường hợp cơ sở thứ nhất. Kết quả là 1. return 1; if (n == 2) // Trường hợp cơ sở thứ hai. Kết quả là 1. return 1; // Công thức truy hồi. return fib(n - 1) + fib(n - 2); } ``` Ngôn ngữ: Python ```python= def fib(n): if (n == 1): # Trường hợp cơ sở thứ nhất. Kết quả là 1. return 1 if (n == 2): # Trường hợp cơ sở thứ hai. Kết quả là 1. return 1 # Công thức truy hồi. return fib(n - 1) + fib(n - 2) ``` **Nếu không có trường hợp cơ sở, thuật toán sẽ gọi đi gọi lại hàm đệ quy liên tục tới vô tận lần. Nếu đạt giới hạn số lần gọi đệ quy của máy tính, ngôn ngữ thì sẽ xảy ra lỗi StackOverflow.**