Đệ quy là gì?

Đệ quy vào C là quy trình trong kia một thủ tục gọi lại chính nó một phương pháp liên tiếp. Một cách thức trong C gọi lại chủ yếu nó được hotline là thủ tục đệ quy.

Cú pháp:


Bạn đang xem: Bài tập đệ quy có lời giải

kieu_tra_ve tenhamdequi() // your code tenhamdequi(); /* goi lai chinh no */int main() tenhamdequi();
ngữ điệu lập trình C cung ứng đệ quy, ví dụ, một hàm có thể gọi đến bao gồm nó. Nhưng khi chúng ta sử dụng hàm đệ quy, lập trình sẵn viên nên phải cảnh giác định nghĩa đk thoát khỏi hàm, phòng khi chạm mặt phải vòng lặp vô hạn.

Hàm đệ quy rất có ích để giải quyết các sự việc trong toán học như đo lường và thống kê giai thừa, chế tạo dãy Fibonacci, …


bài xích tập Đệ quy trong C

Dưới đây là các bài xích tập C khiến cho bạn hiểu kỹ năng và kiến thức cơ phiên bản về Đệ quy trong C:

Tính hàng số Fibonacci sử dụng đệ quy

Ví dụ lịch trình C tra cứu 10 số Fibonacci trước tiên sử dụng phương pháp đệ quy:


Chạy lịch trình C bên trên cho công dụng như sau:

*

Tính giai thừa áp dụng đệ quy

Ví dụ công tác tính giai quá trong C gồm sử dụng phương pháp đệ quy:


return giai thua kém cua so n */long tinhGiaithua(int n) if (n > 0) return n * tinhGiaithua(n - 1); else return 1; /** * đê mê main */int main() int a = 5; int b = 0; int c = 10; printf("Giai thua trận cua %d la: %d ", a, tinhGiaithua(a)); printf("Giai thất bại cua %d la: %d ", b, tinhGiaithua(b)); printf("Giai thảm bại cua %d la: %d", c, tinhGiaithua(c));
Chạy công tác C bên trên cho tác dụng như sau:

*

kiếm tìm USCLN và BSCNN của 2 số a cùng b áp dụng đệ quy

Ví dụ sau đây sử dụng giải thuật Euclid để xử lý bài toán tìm mong số chung lớn nhất (USCLN) với bội số chung bé dại nhất (BSCNN) của hai số nguyên dương a và b:


/** * Chuong trinh tim uoc thông thường lon nhat (USCLN) * va boi so thông thường nho nhat (BSCNN) cua 2 so a cùng b * *
author dulongky.com */#include /** * Tim uoc so tầm thường lon nhat (USCLN) */int USCLN(int a, int b) if (b == 0) return a; return USCLN(b, a % b); /** * Tim boi so phổ biến nho nhat (BSCNN) */int BSCNN(int a, int b) return (a * b) / USCLN(a, b); /** * si main */int main() int a, b; printf("Nhap so nguyen duong a = "); scanf("%d", &a); printf("Nhap so nguyen duong b = "); scanf("%d", &b); // tinh USCLN cua a với b printf(" USCLN cua %d va %d la: %d", a, b, USCLN(a, b)); // tinh BSCNN cua a cùng b printf(" USCLN cua %d va %d la: %d", a, b, BSCNN(a, b));

Xem thêm: Xem Tử Vi 2017 Tuổi Canh Thân Nam Mạng 1980, Nữ Mạng,, Tử Vi Tuổi Canh Thân Nam Mạng Năm 2017

Chạy lịch trình C trên cho hiệu quả như sau:

*

Tính tổng n số áp dụng đệ quy

Ví dụ lịch trình tổng của n số vào C gồm sử dụng cách thức đệ quy:


/** * Chuong trinh tong cua n so tu nhien * *
author dulongky.com */#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);
Chạy lịch trình C trên cho tác dụng như sau:

*

bài toán Tháp hà thành (Tower of Hanoi) thực hiện đệ quy

Trước khi tìm hiểu lời giải cho việc Tháp hà nội (Tower of Hanoi), bản thân xin đề cập lại một số trong những qui tắc của trò đùa toán Tháp tp. Hà nội này:

Tháp thành phố hà nội (Tower of Hanoi) là gì ?

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

Dưới đây là hình minh họa vấn đề Tháp thủ đô hà nội (Tower of Hanoi) với trường hợp tất cả 3 đĩa.

*

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

Qui tắc trò chơi toán học tập Tháp thành phố hà nội (Tower of Hanoi)

trách nhiệm của trò nghịch là dịch rời các đĩa tất cả kích cỡ khác biệt sang cột khác làm thế nào để cho vẫn bảo vệ thứ tự ban sơ của những đĩa: đĩa nhỏ tuổi nằm trên đĩa lớn. Dưới đấy là một số qui tắc đến trò chơi toán học tập Tháp hà nội thủ đô (Tower of Hanoi):

Mỗi lần chỉ có thể di gửi một đĩa từ bỏ cột này lịch sự cột khác. Chỉ được dịch chuyển đĩa nằm trên thuộc (không được dịch rời các đĩa ở giữa). Đĩa có kích thước lớn hơn thiết yếu được đặt lên đĩa bao gồm kích thước bé dại hơn.

Dưới đó là hình minh họa phương pháp giải việc Tháp tp hà nội (Tower of Hanoi) với ngôi trường hợp gồm 3 đĩa.

*

Bài toán Tháp hà nội thủ đô (Tower of Hanoi) cùng với số đĩa là n hoàn toàn có thể được giải cùng với số cách tối thiểu là 2n−1. Vì đó, với trường hợp 3 đĩa, vấn đề Tháp tp. Hà nội (Tower of Hanoi) rất có thể được giải sau 23−1 = 7 bước.

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

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


/** * Chuong trinh giai bai toan Thap Ha Noi * *
author dulongky.com */#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);
Chạy công tác C bên trên cho hiệu quả như sau:

*

bài bác tập C - thay đổi chuỗi thành chữ thường trong C
bài xích tập C - cùng hai số bởi sử dụng con trỏ vào C