Bài 9: Đệ Qui - Thiết Kế Mạch Điện Tử

Trang chủ » Suy Biến Trong C Là Gì » Bài 9: Đệ Qui - Thiết Kế Mạch Điện Tử

Có thể bạn quan tâm

Tìm kiếm Logo Sign in Đăng nhập tài khoản Tài khoản mật khẩu của bạn Forgot your password? Get help Password recovery Khởi tạo mật khẩu email của bạn Mật khẩu đã được gửi vào email của bạn. Thứ Bảy, Tháng 2 28, 2026 Đăng nhập/Đăng ký FacebookInstagramTwitterVimeoYoutube Logo Tìm kiếm Trang Chủ Giáo Trình LẬP TRÌNH C Bài 9: Đệ qui
  • Giáo Trình
  • LẬP TRÌNH C
FacebookTwitterPinterestWhatsApp

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!=1×1 <=>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.

Chia sẻ:

  • Click to share on Twitter (Opens in new window)
  • Click to share on Facebook (Opens in new window)

BÀI VIẾT LIÊN QUANXEM THÊM

LẬP TRÌNH C

Bài 11: Mảng nhiều chiều

LẬP TRÌNH C

Bài 10: Mảng một chiều

LẬP TRÌNH C

Bài 8: Chương trình con – Hàm

Leave a ReplyCancel reply

100Người hâm mộThích0Người theo dõiKết nối1,000Người theo dõiĐăng Ký

DANH MỤC

  • VIDEO32
  • DỊCH VỤ30
  • VI ĐIỀU KHIỂN PIC29
  • ĐIỆN TỬ CƠ BẢN26
  • VI ĐIỀU KHIỂN 805121
  • VI ĐIỀU KHIỂN MSP 43011

Lịch

Tháng 2 2026
H B T N S B C
 1
2345678
9101112131415
16171819202122
232425262728  
« Th1    

Bài viết mới

Pure Sine Inverter 16F684

25 Tháng 1, 2016

Sửa lỗi OUT of ROM CCS Complier

25 Tháng 1, 2016

Demo giao tiếp Ethernet Pic

24 Tháng 1, 2016

Bài viết phổ biến

Virtual Serial Port Driver – Tạo cổng COM ảo

17 Tháng 12, 2015

Bài 2: Đại số Boole và ứng dụng

11 Tháng 1, 2016

TẢI CCS 5.015 Full

17 Tháng 12, 2015

Danh mục

  • VIDEO32
  • DỊCH VỤ30
  • VI ĐIỀU KHIỂN PIC29
  • ĐIỆN TỬ CƠ BẢN26
  • VI ĐIỀU KHIỂN 805121
  • VI ĐIỀU KHIỂN MSP 43011
  • VI ĐIỀU KHIỂN AVR11
  • LẬP TRÌNH C11
Logo

Giới thiệu

Điện Tử RDVIET Nhận Thiết Kế Mạch Theo Yêu Cầu, Nhận Lập Trình STM32, ARDUINO, PIC, NUVOTON..., Tự Động Hóa Trong Công Nghiệp.

Email: [email protected]

Kết nối

BloggerFacebookFlickrInstagramVKontakte

© RDVIET - Thiết Kế Mạch Điện Tử

Từ khóa » Suy Biến Trong C Là Gì