# DATA STRUCTURES & ALGORITHMS RECURSION(Đệ Quy)

***Chà vừa đọc tiêu đề là muốn đóng hòm luôn gòi. Dù sao thì bài viết dưới đây của tớ sẽ nói về đệ quy cũng như cách hoạt động của nó. Ở thời điểm này tớ vẫn đang trong quá trình học C++ nên là mọi thứ dưới đây sẽ được tớ mô phỏng dựa trên ngôn ngữ này.***

- Đệ quy có lẽ sẽ khó hiểu đặc biệt là với những người mới bắt đầu học lập trình.
- Vậy thì để tớ giới thiệu nó qua 1 ví dụ :

Đây là bạn, một hôm bạn bị nhốt bên ngoài phòng ngủ do bạn lỡ khóa chốt khi bước ra khỏi đó. Bạn chợt thấy 1 con búp bê matryoshka nằm ở góc nhà và nhớ rằng mình để chìa khóa cửa phòng trong đấy.

Thế là bạn bắt đầu mở con búp bê để tìm ra ...con búp bê nhỏ hơn nữa. Búp bê trong búp bê. Và cứ tiếp tục cho đến khi bạn mở đến con nhỏ nhất thì bạn tìm thấy chìa khóa.
## 1 Đệ Quy?
## 1.1 ĐỆ QUY LÀ GÌ?
- Hiểu 1 cách đơn giản thì khi một hàm gọi lại bản thân chính nó thì được gọi là **đệ quy**.

Ví dụ :

void Đệ quy(int n)
{
if(n == 1)
return 1;
else
return Đệ quy(n - 1);
}

- Nghe thì có vẻ hơi khó hiểu đấy nhưng mà đừng lo. Những ví dụ ở phía sau có lẽ thể giúp bạn hiểu được về định nghĩa của nó đấy.
## 1.2 Tại sao lại phải sử dụng đệ quy?
- Đệ quy được cho là 1 công cụ rất hiệu quả giúp ta giải quyết các vấn đề khó. Chúng giúp ta bằng cách chia nhỏ các vấn đề lớn thành dạng cơ bản nhất của nó từ đó xử lý.

int fibo(int n = 5)
{
if(n<=1) // stop recursion
return 1;
else
return fibo(n-1) + fibo(n-2); // call recursion
}
Out put:

fibo = 8

Hãy cùng xem cách đoạn code trên hoạt động nào.

+ Ở đây bạn có thể thấy hàm tự gọi chính bản thân nó 2 lần và ở trên tớ đã truyền vào hàm 1 tham số n = 5. Hai lời gọi trong hàm đã sửa đổi giá trị ban đầu lần lượt là **n -1** và **n-2** (độ khó của bài toán đã được giảm đi bớt). Và với tham số tớ truyền bên trên thì hàm đệ quy sẽ chia nhỏ vấn đề như này.

fibo(5)
=>fibo(4) + fibo(3)
=>fibo(3) + fibo(2) + fibo(2) + fibo(1)
=>fibo(2) + fibo(1) + fibo (1) + fibo(0) + fibo(1) + fibo(0) + 1
=>fibo(1) + fibo(0) + 1 + 1 + 1 + 1 + 1 + 1
=> 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 = 8

Đệ quy thường là giải pháp đầu tiên và nhanh nhất mà ta nghĩ ra để giải quyết vấn đề. **Tại sao?**
Đối với các bài toán lớn và có độ phức tạp cao thì việc sử dụng Đệ Quy như là phương pháp dùng để mổ xẻ các vấn đề lớn và đưa nó về dạng cơ bản ( Hay ta thường gọi phương pháp này là chia để trị ).
. Phạm vi áp dụng: Các bài toán dạng chia để trị, quy hồi…
- Ta có thể chỉ dựa vào định nghĩa cũng có thể viết được 1 đoạn code tính số fibo như ở trên

- So với đoạn code dưới đây sử dụng vòng lặp thì việc nghĩ ra thuật toán cho nó có vẻ rắc rối hơn.

int Fibonacci(int n){
int a1 = 1, a2 = 1;
if(n==1||n==2) return 1;
int i=3,a;
while(i<=n){
a=a1+a2;
a1=a2;
a2=a;
i++;
}
return a;
## 2.Xây Dựng Cấu trúc của hàm đệ quy.

#### 2.1: Cấu trúc của 1 hàm đệ quy.
- Khi sử dụng đệ quy thì điều quan trọng nhất đó chính là cách chúng hoạt động.

Hãy xem ví dụ dưới đây để có thể biết được trong đệ quy có những thành phần gì.


- Ở đoạn code bên trên bạn có thể thấy tớ đặt 1 câu điều kiện **if(n==1)** và gọi nó là điểm dừng.

**Lý do là vì đây là phần thể hiện tính dừng của thuật toán. Vốn dĩ hàm đệ quy là 1 hàm chia tách vấn đề sau những lần gọi lại. Và 1 vấn đề thì sẽ không thể nào tách mãi được mà phải đạt tới một bài toán cơ sở đã có sẵn kết quả. Có 1 điều khá hay ở điểm dừng đó là nó ***có thể*** giải trực tiếp vấn đề mà không cần qua bài toán nhỏ nào.**

- Phần tiếp theo trong đoạn code đó chính là Phần đệ quy.
**Đây chính là thành phần chính của 1 hàm đệ quy bởi trong trường bài toán chưa giải được thì ta gọi lại hàm để chia nhỏ bài toán rồi sử dụng tính truy hồi từ đó có thể tìm ra được kết quả.**

#### 2.2 : Cách mà đệ quy lưu trữ bộ nhớ.
-Trong ngôn ngữ lập trình ta có khái niệm Stack, Stack là một cấu trúc dữ liệu tuyến tính hay là một ngăn xếp được dùng để lưu trữ các dữ liệu cùng kiểu

(trong đệ quy dữ liệu được lưu trữ theo cơ chế được gọi là LIFO (Last IN -
First Out).


- Điều này khá giống với việc bạn xếp sách thành chồng. Để thêm quyển sách vào chồng thì bạn chỉ có thể đặt nó ở trên đầu và khi muốn lấy quyển sách nằm cuối cùng thì phải lấy cuốn sách nằm ở trên ra trước.

- Hãy cùng nhìn vào đoạn code tính giai thừa bằng đệ quy dưới đây.

int factorial(int n)
{
if(n==1) // stop recursion
return 1;
else
return factorial(n-1) * n; // call recursion and save into stack
}

OUT PUT : FACTORIAL = 6

- Chúng ta hãy cùng xem việc truyền n = 3 vào recursion được thể hiện như thế nào trong stack.


**Giả Sử nếu như ở trên chúng ta không có điều kiện dừng thì chuyện gì sẽ xảy ra?**

- Như đã nói ở trên Stack là 1 cấu trúc dữ liệu tuyến tính dùng để lưu trữ dữ liệu, tùy thuộc vào chương trình đang chạy Stack sẽ được cung cấp vùng nhớ nhất định, khi Stack bị tràn và ghi đè sang vùng nhớ khác thì điều này dẫn đến hiện tượng như trong hình dưới đây


*Tham khảo thêm dòng link dưới đây để có thể biết thêm về sự nguy hiểm của StackOverFlow.*

https://www.quora.com/What-makes-a-stack-overflow-dangerous

## 3. Đệ quy và vòng lặp

- Tất nhiên đến đây sẽ có người thắc mắc rằng đệ quy cũng giống như vòng lặp vậy do tính chất lặp lại của nó.
- Nhưng thực ra thì cả 2 khái niệm này đều có 1 vài sự khác biệt.


- Một vài trường hợp vòng lặp sử dụng Stack là khi ta dùng để cấp phát động bộ nhớ.
- Thêm vào đó với các hệ máy hiện nay thì Đệ Quy được cho là có tốc độ được xử lý nhanh hơn so với vòng lặp.
( https://leetcode.com/problems/powx-n/solutions/179886/why-recursion-runs-faster-than-loop/ )

**Một câu hỏi thường gặp là: "Tại sao lại sử dụng hàm đệ quy trong khi bạn có thể thực hiện với vòng lăp (vòng lặp for hoặc while )?".**

Câu trả lời : Thông thường, các bài toán đệ quy có thể giải quyết bằng vòng lặp. Tuy nhiên, hàm đệ quy giúp code dễ đọc và đơn giản hơn.
Ví dụ như bài toán tháp HaNoi

using namespace std;
int move(int n, char A, char B, char C)
{
//checking n
if(n == 1)
{
//move variable from A to C
cout<<A<<"-->"<<C<<"\n";
}
else // n # 1
{
//Call Recursion
//n = n - 1
//swap variable B & C
move(n-1,A,C,B);
cout<<A<<"-->"<<C<<"\n";

//Call Recursion
// n = n - 1
//swap variable A & B ( now it's C)
move(n-1,B,A,C);
}
}
int main()
{
int n = 3;
move(n,'A','B','C');
return 0;
}

OutPut:

## 4.Conclusion
- Đệ quy là một phương pháp cơ bản trong kỹ thuật lập trình.Việc sử dụng đệ quy vào các bài toán thì nên cân nhắc, mặc dù đệ quy khiến code chúng ta dễ đọc, nhưng rất khó cho việc debug.

## Nguồn tham khảo :
https://www.geeksforgeeks.org/introduction-to-recursion-data-structure-and-algorithm-tutorials/?ref=gcse

https://www.freecodecamp.org/news/how-recursion-works-explained-with-flowcharts-and-a-video-de61f40cb7f9/

https://www.youtube.com/watch?v=tHo18sWKqDs
***Đây là bài blog đầu tiên của tớ trong quá trình học nên chắc hẳn sẽ có nhiều thiếu sót, hi vọng mọi người có thể giúp tớ khắc phục những thiếu sót đó.Cảm ơn vì đã dành thời gian ra để xem bài viết của tớ. Peace!***