Tự học lập trình C - Bài 9: Đệ qui

ĐỆ QUI

Giải thuật đệ quy:

Giải thuật đệ quy là giải thuật có chứa thao tác gọi đến chính nó. Giải thuật đệ quy cho phép mô tả một dãy lớn các thao tác bằng một số ít các thao tác trong đó có chứa thao tác gọi lại giải thuật (gọi đệ quy).

Giải thuật giải bài toán bằng đệ quy thường rất đẹp, gọn gàng, dễ hiểu, dễ sửa đổi. Tuy nhiên, việc xử lý giải thuật đệ quy lại thường gây khó khăn cho máy tính (tốn không gian nhớ và thời gian xử lý), hơn nữa không phải mọi ngôn ngữ lập trình đều cho phép mã hóa giải thuật đệ quy (ví dụ: FORTRAN) .

Chương trình con đệ quy:

Chương trình con đệ quy là một chương trình con mà trong thân của nó có ít nhất một câu lệnh là lời gọi đến chính nó.

Chương trình con đệ quy phải có hai thành phần:

-        Thành phần không chứa đệ qui, đó là điều kiện để kết thúc quá trình đệ qui.

-        Thành phần có chứa đệ quy, sau mỗi bước, phạm vi của thành phần này phải thay đổi cho đến khi gặp điều kiện kết thúc.

@Lưu ý: Muốn giải một bài toán bằng giải thuật đệ qui việc đầu tiên ta phải đưa bài toán về một dạng tổng quát. Từ đây ta phải đi xác định cho được điều kiện suy biến của bài toán (tức điều kiện để kết thúc giải thuật đệ qui) và điều kiện gọi đệ qui.

Ví dụ bài toán tính n!

Ta có

n=0, 0!=1,

n=1, 1!=1x1 <=>0!x1

n=2, 2!=1x1x2<=>1!x2

n=3, 3!=1x1x2x3 <=>2!x3

=>n!=1x1x2x3x...x n<=>(n-1)! x n

Như vậy:

- Điều kiện suy biến  khi n=0, 0!=1

- Điều kiện gọi đệ qui n>0, n!=n x (n-1)!

Vậy, khi có được 0! =>1! =>2!=>3! ...=>n! 

Giải thuật tính n!

#include <stdio.h>

long int gthua(int n);

void main(void)

{

int n;

scanf(“%d”,&n);

printf(“Giai thừa của%d là: %d”,n,gthua(n));

}

int long gthua(int n)

{

if(n==0)

          return 1;

      elsse

         return(n*gthua(n-1));

}

-      Khi thực hiện lời gọi gthua(3) sẽ phát sinh lời gọi gthua(2), đồng thời phải lưu giữ thông tin về trạng thái xử lý chưa hoàn thành (return(3 * gthua(2))) vào Stack.

-      Gặp lời gọi gthua(2), tiếp tục làm phát sinh lời gọi gthua(1), đồng thời vẩn phải lưu trử thông tin về trạng thái xử lý còn dang dở (return( 2*gthua(1)))vào Stack.

-      Cứ như vậy cho tới khi gặp lời gọi của trường hợp suy biến (return(1))).

-      Khi gặp trường hợp suy biến, những thông tin được lưu tạm trong Stack sẽ được lấy ra xử lý (thông tin lấy ra theo kiểu lưu trữ của Stack, thông tin vào sau sẽ được lấy ra trước). Và như vậy, dùng kết quả của gthua(0) để tính gthua(1), dùng kết quả của gthua(1) để tính gthua(2), dùng kết quả của gthua(2) để tính gthua(3). Cuối cùng được kết quả của phép tính giai thừa.

Cụ thể thực hiện lấy và tính toán trong Stack như sau:

-      Lấy return(1*gthua(0)) để thực hiện gthua(1)=1*gthua(0)=1*1=1

-      Lấy return(2*gthua(1)) để thực hiện gthua(2)=2*gthua(1)=2*1=3

-      Lấy return(3*gthua(2)) để thực hiện gthua(3)=3*gthua(2)=3*2=6

 Bài tập thực hành

1. Sử dụng đệ qui để viết hàm tìm ước số chung lớn nhất của 2 số

2. Sử dụng đệ qui để viết hàm tính tổng S = 1+2+….+n.