Đệ quy là gì ?

Đệ quy là quy trình lặp đi lặp lại một thành phần theo và một bí quyết. Dưới đấy là một ví dụ minh họa tổng quát:

void tenhamdequi() tenhamdequi(); /* goi chinc no */int main() tenhamdequi();Ngôn ngữ xây dựng C hỗ trợ đệ quy, ví dụ, một hàm hoàn toàn có thể Hotline mang lại bao gồm nó. Nhưng khi chúng ta áp dụng hàm đệ quy, xây dựng viên cần được cẩn thận quan niệm ĐK ra khỏi hàm, phòng Lúc gặp gỡ phải vòng lặp vô hạn.

Bạn đang xem: Bài tập đệ quy c++

Hàm lặp đệ quy hết sức có ích nhằm giải quyết và xử lý những vấn đề vào tân oán học nlỗi tính toán thù giai vượt, tạo thành hàng Fibonacci, …

1. Bài tập C: Tính tổng n số thực hiện đệ quy

Đây là bài tập C tương đối đơn giản dễ dàng khiến cho bạn gọi giải pháp áp dụng đệ quy trong ngôn từ thiết kế C.

Cmùi hương trình C

Dưới đó là lịch trình C nhằm giải bài tập tính tổng n số thực hiện đệ quy trong C:

#includeint calculateSum(int);int main() int i, num; int result; printf("Nhap mot so bat ky: "); scanf("%d", &num); result = calculateSum(num); printf(" Tong cac so tu 1 toi %d la: %d", num, result); return (0);int calculateSum(int num) int res; if (num == 1) return (1); else res = num + calculateSum(num - 1); return (res);Biên dịch công tác C bên trên sẽ mang lại kết quả:

*

2. bài tập C: Tính giai vượt bởi vì sử dụng đệ quy

Giai quá của một số trong những n là tích những số từ là 1 tới n. Ví dụ, giai vượt của 4 là (4 * 3 * 2 * 1 = 24). Đây là bài tập C khá đơn giản dễ dàng khiến cho bạn có tác dụng quen thuộc cùng với giải pháp áp dụng đệ quy vào C.

Chương thơm trình C

Dưới đó là công tác C nhằm giải bài bác thói quen giai thừa do sử dụng đệ quy trong C:

#include int tinhgiaithua(unsigned int i) if(i 1) return 1; return i * tinhgiaithua(i - 1);int main() int i = 10; printf("Gia tri giai thua trận cua %d la %d ", i, tinhgiaithua(i)); printf(" =========================== "); printf("VietJaông chồng chuc cac ban hoc tot! "); return 0;Biên dịch với thực thi công tác C bên trên sẽ mang lại kết quả sau:

*

3. Những bài tập C: Giải bài bác toán thù Tháp thủ đô hà nội (Tower of Hanoi) áp dụng đệ quy

Trước lúc tò mò lời giải cho bài xích toán Tháp TP Hà Nội (Tower of Hanoi), mình xin nói lại một vài qui tắc của trò chơi tân oán Tháp Thành Phố Hà Nội này:

Tháp Hà Nội (Tower of Hanoi) là gì ?

Bài toán thù Tháp Hà Nội (Tower of Hanoi) là 1 trò chơi toán học tập bao gồm 3 cột với với số đĩa nhiều hơn 1.

Dưới đó là hình minch họa bài xích tân oán Tháp Hà Nội (Tower of Hanoi) cùng với trường thích hợp gồm 3 đĩa.

*

Các đĩa có kích thước khác biệt cùng xếp theo tự trường đoản cú tăng đột biến về kích cỡ từ bỏ trên xuống: đĩa nhỏ tuổi hơn ngơi nghỉ trên đĩa lớn hơn. Với số đĩa không giống nhau thì ta có những bài xích toán Tháp Thành Phố Hà Nội (Tower of Hanoi) khác biệt, mặc dù lời giải cho các bài xích tân oán này là tương tự nhau. Lời giải về tối ưu cho bài xích toán thù Tháp Thành Phố Hà Nội (Tower of Hanoi) là khi trò đùa chỉ bao gồm 3 cọc. Với số cọc to hơn thì lời giải bài toán vẫn không được khẳng định.

Qui tắc trò chơi toán học tập Tháp TP Hà Nội (Tower of Hanoi)

Nhiệm vụ của trò chơi là dịch rời các đĩa gồm kích cỡ khác biệt lịch sự cột khác làm sao để cho vẫn bảo đảm an toàn thiết bị từ bỏ lúc đầu của các đĩa: đĩa nhỏ tuổi nằm trong đĩa Khủng. Dưới đây là một số qui tắc đến trò nghịch toán thù học tập Tháp Hà Nội Thủ Đô (Tower of Hanoi):

Mỗi lần chỉ rất có thể di chuyển một đĩa từ bỏ cột này lịch sự cột không giống.Chỉ được di chuyển đĩa nằm trong cùng (ko được di chuyển những đĩa ở giữa).Đĩa tất cả form size to hơn thiết yếu được đặt lên trên đĩa có form size nhỏ tuổi rộng.

Dưới đó là hình minch họa phương pháp giải bài toán Tháp thủ đô (Tower of Hanoi) cùng với ngôi trường đúng theo gồm 3 đĩa.

*

Bài toán thù Tháp thủ đô (Tower of Hanoi) cùng với số đĩa là n rất có thể được giải cùng với số bước buổi tối thiểu là 2n−1. Do đó, với trường phù hợp 3 đĩa, bài xích tân oán Tháp TP Hà Nội (Tower of Hanoi) rất có thể được giải sau 23−1 = 7 bước.

Phần tiếp sau đây mình trình diễn nhị cách giải: thực hiện đệ quy và KHÔNG thực hiện đệ quy vào C.

Chương trình C: thực hiện đệ quy

Dưới đây là lịch trình C nhằm giải bài toán Tháp thủ đô hà nội (Tower of Hanoi) sử dụng đệ quy vào C vào C:

#includevoid TOH(int num, char x, char y, char z);int main() int num; printf(" Nhap so dia:"); scanf("%d", &num); TOH(num - 1, "A", "B", "C"); return (0);void TOH(int num, char x, char y, char z) if (num > 0) TOH(num - 1, x, z, y); printf(" %c -> %c", x, y); TOH(num - 1, z, y, x); Biên dịch công tác C trên vẫn cho kết quả:

*

Những bài tập C: In dãy Fibonacci thực hiện đệ quy

Dãy Fibonacci là dãy số được chế tạo bằng cách: số kế tiếp bởi tổng của nhị số liền trước. Dãy Fibonacci bắt đầu từ hai số F0 & F1. Giá trị thuở đầu của F0 & F1 rất có thể khớp ứng là 0, 1 hoặc 1, 1.

Xem thêm: Cách Chỉnh Loa Laptop Win 7 Win 10, Phần Mềm Tăng Âm Lượng Loa Máy Tính Laptop

Điều khiếu nại của dãy Fibonacci có thể tổng quát lại nhỏng sau:

Fn = Fn-1 + Fn-2Dưới đấy là ví dụ hai Fibonacci

F8 = 0 1 1 2 3 5 8 13

hoặc:

F8 = 1 1 2 3 5 8 13 21

Trong chương này bọn họ đã giải bài xích tập C này vì áp dụng khái niệm đệ quy. Mời chúng ta quan sát và theo dõi công tác C tiếp sau đây.

Cmùi hương trình C

Dưới đó là lịch trình C để giải bài bác tập in hàng Fibonacci thực hiện đệ quy trong C:

#include int day_fibonaci(int i) if(i == 0) return 0; if(i == 1) return 1; return day_fibonaci(i-1) + day_fibonaci(i-2);int main() int i; for (i = 0; i 10; i++) printf("%d %n", day_fibonaci(i)); printf(" =========================== "); printf("VietJachồng chuc cac ban hoc tot! "); return 0;Biên dịch và tiến hành công tác C bên trên đã mang lại công dụng sau: