Lập Trình C: Đệ Quy (Recursion) | V1Study

• Đào tạo Độ tuổi từ 5 - 11 Độ tuổi từ 12 - 17 Từ 18 tuổi
• Lập trình Python Lập trình C C++ Java C# - C Sharp Android Scratch Pascal Robot mBot
• Web ReactJS HTML5 CSS3 JavaScript Node.js JSP ASP.NET Core jQuery PHP
• FW-CMS Laravel AngularJS Flutter Magento Bootstrap VueJS CodeIgnitor WordPress Sass Drupal
• Video Video Python Video Lập trình C Video C# Video Java Video HTML5-CSS3-JavaScript Video SQL Server Video PHP Video jQuery Video Android Video C++ Video Scratch
• Video1 Video XML-JSON Video MySQL Video Excel Video Giải thuật và Lập trình Video Sức khỏe Video Drupal Video mBot Video Giáo dục - Khoa học
• Other Unity Giải thuật và lập trình Giải thuật và lập trình - C CCNA Mạng máy tính Design Patterns English Facebook SEO Git Tin học đại cương Japanese App-Uti Download
• Data SQL Server XML JSON MySQL
• News

≡ ≡ Lập trình C Bài học Danh sách bài học Bài 1. Giới thiệu Bài 2. Đặc điểm Bài 3. Hướng dẫn viết mã lệnh Bài 4. Hướng dẫn lập tư liệu nội bộ Bài 5. Quy tắc đặt tên Bài 6. Từ khoá (Keyword) Bài 7. Kiểu dữ liệu (Data type) Bài 8. Hằng (Constant) Bài 9. Biến (Variable) Bài 10. Định dạng, ký tự đặc biệt và bổ từ Bài 11. Lớp lưu trữ Bài 12. Phép toán số học Bài 13. Phép Gán (Assignment) Bài 14. Phép toán So sánh Bài 15. Phép toán Logic (Logical) Bài 16. Phép toán Logic nhị phân Bài 17. Độ ưu tiên phép toán Bài 18. printf() & scantf() Bài 19. Ép kiểu (Cast) Bài 20. if-else và ?: Bài 21. switch-case Bài 22. Vòng lặp for Bài 23. Vòng lặp while Bài 24. Vòng lặp do-while Bài 25. break; và continue; Bài 26. Hàm (Function) Bài 27. Lời gọi hàm (Call Function) Bài 28. Biến tổng thể và biến cục bộ Bài 29. Đệ quy (Recursion) Bài 30. Mảng (Array) một chiều Bài 31. Mảng hai chiều Bài 32. Chuỗi (String) Bài 33. Mảng chuỗi Bài 34. Hàm xử lý chuỗi (String) Bài 35. Con trỏ (Pointer) Bài 36. Cấp phát bộ nhớ Bài 37. Cấu trúc (Struct) Bài 38. Cơ bản về tập tin Bài 39. Quản lý tập tin văn bản Bài 40. Quản lý tập tin nhị phân Bài 41. Các hàm xử lý tập tin Ví dụ Giải phương trình bậc 1 Giải phương trình bậc 2 Nguyên hay thực Nguyên âm hay Phụ âm Số ngày trong tháng Tam giác vuông trái xuôi Cách nhập liệu cho mảng Cách xóa phần tử khỏi mảng Cách sắp xếp mảng Tìm Max, Min bằng phương pháp sắp xếp Tìm số nguyến tố trong mảng số thực Kiểm tra một số có phải số nguyên hay không Kiểm tra một số có phải số chính phương không Kiểm tra một số có phải số nguyên tố không Đếm số từ trong chuỗi Xóa phần tử mảng Tính điểm tổng kết môn học Lập trình C Tuổi cha và tuổi con Bài tập Bài tập cơ bản Bài tập phần điều kiện Bài tập phần vòng lặp (Loop) Bài tập phần mảng (Array) Bài tập phần hàm (function) Bài tập phần cấu trúc (struct) Bài tập phần tập tin (File) Quiz Tham khảo Hàm toán học (Math) Bảng mã ASCII Hệ thống nhớ máy tính Danh sách kiểu dữ liệu Phím tắt BorlandC Cách lấy kích thước mảng Chuyển từ kiểu int sang chuỗi Hàm hoán vị 2 số không cần dùng con trỏ Tìm kiếm nhị phân (Binary Search) Hướng dẫn sử dụng CodeBlocks bản nosetup 7 lý do bạn nên nắm được kiến thức C/C++ Sự khác biệt giữa mã định dạng %d và %i QuickSort Bài toán mã đi tuần Hàm xử lý ký tự (Character) Tích hợp C/C++ vào VS Code Videos Chỉnh sửa cơ bản Khung chương trình C Xác định nguyên hay thực Hoán vị hai số Xác định tính nguyên tố (prime) Demo giải phương trình bậc 1 Demo giải phương trình bậc 2 Phương trình bậc 2 - Tạo hàm Cách nhập liệu cho mảng một chiều Cách xóa phần tử khỏi mảng Cách sắp xếp mảng Tìm Max, Min bằng phương pháp sắp xếp Cách khai báo biến Xác định tính chính phương Kiểm tra số nguyên Kiểm tra tính chính phương Cách sắp xếp mảng 2 chiều Solutions Solution bài tập cơ bản Solution Bài tập phần điều kiện Solution bài tập phần vòng lặp Solution bài tập phần mảng số Tính tổng dãy số nguyên (không phải mảng) Đáp án tham khảo Bộ đề Đề 1 Đề 2 Đề 3 Đề 4 Đề 5 Đề 6 Đề 7 Đề 8 Đề 9 Đề 10 Đề 11 Đề 12 Đề 13 Đề 14 Đề 15 Đề 16 Đề 17 Đề 18 Đề 19 Đề 20 Đề 24 Taught Cơ sở lập trình - Buổi 1 Chữa bài tập 1 phần hàm Kiến thức phần hàm (function) Kiến thức phần mảng Mảng ký tự - Chuỗi Struct Lập trình C: Đệ quy (Recursion) Khóa học qua video: Lập trình Python All Lập trình C# All SQL Server All Lập trình C All Java PHP HTML5-CSS3-JavaScript Đăng ký Hội viên Tất cả các video dành cho hội viên

Ngôn ngữ C cho phép hàm gọi đến chính nó, người ta gọi phương pháp này là phương pháp đệ quy hoặc quay lui (xem thêm bài viết Đệ quy và giải thuật đệ quy).

Cú pháp:

Kiểu_trả_về Tên_hàm(Danh_sách_tham_số){ if(Điều_kiện_dừng_thỏa) return Giá_trị; else return Tên_hàm(Danh_sách_đối_số) Phép_toán Tên_đối_số; }

* Thường những hàm có kiểu dữ liệu trả về khác kiểu void mới sử dụng được đệ quy (trừ trường hợp ta muốn lặp lại các lệnh tuần tự của hàm thì ta mới dùng đến kiểu void).

* Trong giải thuật này phải có một Điều_kiện_dừng_thỏa để đệ quy kết thúc (dừng quay lui).

* Phép_toán ở đây là một phép toán bất kỳ phù hợp với bài toán của bạn.

* Chương trình sử dụng đệ quy thì dễ hiểu nhưng hao tốn tài nguyên CPU, dẫn đến làm giảm thời gian chạy chương trình đi nhiều nếu số lần đệ quy của hàm lớn.

Ví dụ 1:

Tính tổng các số chia hết cho 5 nằm trong đoạn [0,N] với N được nhập từ bàn phím.

Phân tích: Điều kiện dừng thỏa ở đây ta có thể thấy được ngay là khi giá trị của đối số bằng 0 (nếu ta chạy ngược giảm dần từ N) hoặc bằng N (nếu ta chạy xuôi tăng dần từ 0). Vì chỉ tính tổng các số chia hết cho 5 nên cứ mỗi lần đệ quy thì ta lại giảm (hoặc tăng) giá trị của đối số 5 đơn vị rồi tiến hành cộng dồn.

Chương trình được viết như sau:

#include<stdio.h> long tinhTong(int N) { if(N<=0) //nếu N==0 return 0; //thì dừng đệ quy else //nếu không thì return tinhTong(N-1) + N; //tiếp tục đệ quy } main() { int N; do { //tiến hành nhập N printf("\nMoi nhap N: "); scanf("%d", &N); }while(N<1); //N phải là từ 1 trở lên mới hợp lệ printf("\nTong cac so tu 1 den %d la: %ld", N, tinhTong(N)); //tiến hành đệ quy return 0; }

Kết quả:

Ví dụ 2:

Ta có thể lập trình tính giai thừa theo phương pháp đệ quy, vì n!=1*2*3*…(n-1)*n hay n!=n*(n-1)*(n-2)*…*1 --> Giá trị sau chính là giá trị trước cộng thêm 1 (hoặc là giá trị trước trừ đi 1), giá trị kết thúc =1.

Sau đây là phần demo:

#include <stdio.h> long giaiThua(int n) { if(n==0) //điều kiện dừng thỏa return 1; //vì 0!=1 nên n==0 là vị trí kết thúc của đệ quy return n*giaiThua(n - 1); //kiểu n*(n-1)*(n-2)…*1 } //hoặc: giaiThua(n-1)*n với kiểu 1*2*3*…*n main() { int n; printf("Nhap n: "); scanf("%d", &n); printf("Giai thua cua %d la %ld", n, giaiThua(n)); return 0; }

Ví dụ 3:

In ra n phần tử đầu tiên của dãy Fibonanci (1 1 2 3 5 8 13 21 34 …).

Phân tích: Hai phần tử đầu tiên của dãy là hai phần tử khởi tạo (1 1), bắt đầu từ phần tử thứ ba trở đi sẽ tuân theo quy tắc là phần tử sau bằng tổng của hai phần tử ngay trước nó cộng lại (ví dụ 13=5+8). Công thức: n= (n-1) + (n-2). Như vậy có nghĩa ta sẽ sử dụng được phương pháp đệ quy vì nó tuân theo cú pháp đệ quy.

Chương trình được viết như sau:

#include<stdio.h> int fibo(int n) { if(n==0 || n==1) //nếu là hai phần tử đầu tiên của dãy (điều kiện dừng thỏa) return 1; //thì sẽ có giá trị là 1 return fibo(n-1) + fibo(n-2); //nếu không thì tính giá trị của phần tử đó } main() { int n, i; float; printf("\nNhap so phan tu can xem cua day Fibonacci: "); scanf("%d", &n); printf("\n%d phan tu dau tien cua day la:\n\n", n); for(i=0; i<n; i++) printf("%d ", fibo(i)); return 0; }

Kết quả:

» Tiếp: Mảng (Array) một chiều « Trước: Biến tổng thể và biến cục bộ Khóa học qua video: Lập trình Python All Lập trình C# All SQL Server All Lập trình C All Java PHP HTML5-CSS3-JavaScript Đăng ký Hội viên Tất cả các video dành cho hội viên Khóa học qua video: Lập trình Python All Lập trình C# All SQL Server All Lập trình C All Java PHP HTML5-CSS3-JavaScript Đăng ký Hội viên Tất cả các video dành cho hội viên Copied !!! Copy linkCopied link!

Bạn muốn tìm kiếm điều gì?

×