Đệ quy là gì? Hàm đệ quy trong lập trình

Đệ quy là gì, cách tính hàm đệ quy trong lập trình. Cùng Trangtailieu tìm hiểu thông tin dưới đây nhé

Đệ quy là gì?

Một đối tượng được gọi là đệ quy nếu nó hoặc một phần của nó được định nghĩa thông qua khái niệm về chính nó.

Đây là một quyển sách toán lớp 3, ở trong bìa sách có ba học sinh, trong đó có một học sinh lại cầm một quyển sách toán lớp ba khác. Và trong quyển sách đó lại có ba học sinh, và cũng có một học sinh cầm một quyển sách lớp 3. Đây chính là ví dụ cho một khái niệm rất căn bản trong bất kỳ ngôn ngữ lập trình nào – khái niệm “đệ quy”.

Hàm đệ quy trong lập trình?

Trước tiên ta cần hiểu phương thức trước, trong lập trình, phương thức là tập hợp các lệnh với tham số truyền vào để máy tính thao tác lệnh theo ý muốn của người viết, đệ quy xảy ra khi người viết các phương thức tự gọi (hoạc định nghĩa lại) chính nó.

Xem ví dụ đơn giản sau nhé. Đề bài: Tính lũy tiến từ 0 đến n.

public int sum(int n) {
if (n >= 1) {
      return sum(n - 1) + n;
}
return n;
}

Giải thích:

• Bạn truyền một tham số n vào phương thức sum(), lệnh trong phương thức sum sẽ trả về tham số n bạn truyền vào khi chạy hết chương trình “return n”.
• Để đến được bước đó, chương trình sẽ chạy qua các lệnh điều kiện “if(n>=1)” để định nghĩa lại phương thức sum một lần nữa “sum(n-1) + n”, phương thức mới sẽ khiến giá trị n sẽ thay đổi theo từng vòng của điều kiện cho đến khi không còn thỏa mãn điều kiện được cho.
• Khi chương trình “return n” thì n chính là giá trị đã được tính ở phương thức ta đặt điều kiện bên trên.

Như vậy, hai yếu tố cần để tiến hành một phương thức đệ quy là:

• Có điều kiện dừng: Xác định quy luật của phương thức và tìm giá trị cụ thể khi thỏa mãn một điều kiện nhất định, ở bước này vẫn chưa có phương thức đệ quy nào được gọi.
• Phương thức đệ quy: Phương thức đệ quy sẽ gọi lại chính nó cho đến khi nó trả về điều kiện dừng ở bước 1.

​Tưởng tượng, mỗi lần bạn sử dụng đệ quy, chương trình chạy một vòng và bộ nhớ Stack sẽ được chồng thêm một lớp dữ liệu, tình trạng lãng phí bộ nhớ rất dễ xảy ra nếu bạn không phân tích kỹ các vòng chạy đệ quy để có tính toán hợp lý. Vấn đề trên có thể giải quyết bằng cách “tối ưu hóa đòn bẩy đệ quy đuôi”.

Bộ nhớ Stack.

Nguyên tắc hoạt động của bộ nhớ Stack là LIFO (Last in – First out hay còn gọi là vào sau – ra trước ). Khi một biến được khai báo trong hàm, nó sẽ được đẩy vào Stack, khi hàm đó kết thúc thì tất cả những biến đó sẽ được đẩy ra, giải phóng khỏi Stack. Hình dưới là minh họa cách hoạt động của bộ nhớ Stack.

Ưu điểm:

Thuận lợi cho việc biểu diễn bài toán, như ở ví dụ trên, nhìn vào hàm là chúng ta có thể thấy ngay nó biểu diễn dãy số fibonacci, hay tính giai thừa.

Nhược điểm:

Tốn nhiều bộ nhớ, nếu không phần cơ sở ( điểm dừng) thì sẽ gây ra việc tràn bộ nhớ stack. Bên cạnh đó việc sử dụng đệ quy tốn nhiều thời gian hơn vòng lặp.

Các ví dụ

Tính tổng các số từ 1 đến n

#include <stdio.h>
 
int sum(int n){
    if(n == 0) // điều kiện dừng (phần cơ sở)
      return 0;
    return n + sum(n-1);
}
 
int main(){
    int sum = sum(5);
    printf("Sum = %d", sum);
}

Kết quả.

Giải thích hàm đệ quy

Với n = 5

5 + sum(4)

5 + 4 + sum(3)

5 + 4 + 3 + sum(2)

5 + 4 + 3 + 2 + sum(1)

5 + 4 + 3 + 2 + 1 + 0

Dãy Fibonacci

#include <stdio.h>
 
int fibonacci(int n)
{
  if ((n == 1) || (n == 2))
    return 1;
  return fibonacci(n-1) + fibonacci(n-2);
}
int main()
{
  printf("%d", fibonacci(30));
}

Kết quả.

Tính giai thừa

#include <stdio.h>
 
int factorial(int n)
{
  if (n == 1) 
    return 1;
  else return factorial(n-1)*n;
}
int main()
{
  printf("%d", factorial(5));
}

Kết quả.

Đệ quy là một khái niệm căn bản trong lập trình và đầy hiệu quả trong tư duy giải quyết vấn đề. Rất nhiều bài toán sau khi được phân tích có thể được giải quyết bằng đệ quy và đồng thời nhiều bài toán khác nếu tiếp cận với đệ quy sẽ tiết kiệm được rất nhiều đoạn code dài dòng.

Thường xuyên rèn luyện giải quyết vấn đề với đệ quy sẽ trợ giúp là rất hữu ích cho tư duy thuật toán của những lập trình viên mới vào nghề, khi mà họ nên học phương pháp tiếp cận và xử lý vấn đề một cách logic và gọn gàng nhất có thể.