Đệ Qui Và Một Số Bài Toán đệ Qui ( Cấu Trúc Dữ Liệu Và Giải Thuật)

Trang chủ » Cấu Trúc Dữ Liệu Và Giải Thuật đệ Quy » Đệ Qui Và Một Số Bài Toán đệ Qui ( Cấu Trúc Dữ Liệu Và Giải Thuật)

Có thể bạn quan tâm

Sign in Sign in Welcome!Log into your account your username your password Forgot your password? Password recovery Recover your password your email Search Wednesday, December 17, 2025
  • Sign in / Join
Sign in Welcome! Log into your account your username your password Forgot your password? Get help Password recovery Recover your password your email A password will be e-mailed to you. sinhvientot.net sinhvientot.net sinhvientot.net sinhvientot.net Home Lập trình C/C++ Đệ qui và một số bài toán đệ qui ( Cấu trúc... Facebook Twitter Pinterest WhatsApp

Trong lĩnh vực lập trình, một chương trình máy tính gọi là đệ qui nếu trong chương trình có lời gọi chính nó. Điều này nghe có vẻ vô lý, nhưng chương trình không thể gọi mãi chính nó vì sẽ tạo ra vòng lập vô hạn. Trên thực tế, khi viết một chương trình đệ qui thì bao giờ người lập trình cũng có một thao tác gọi là điều kiện dừng. Nói ngắn gọn thì một chương trình đệ qui thường có các đặc điểm sau:

Chương trình có thể gọi lại chính nó.

Khi chương trình gọi lại chính nó, mục đích giải quyết là giải quyết vấn đề tương tự nhưng nhỏ hơn.

Vấn đề nhỏ hơn này cho tới một lúc nào đó sẽ đơn giản đến mức mà chương trình có thể tự giải quyết được mà không cần gọi lại nữa.

Điều kiện để viết một chương trình đệ qui: Ngoài việc chương trình phải có dạng đệ qui thì để viết được chương trình đệ qui thì: ngôn ngữ viết chương trình phải hỗ trợ đệ qui, có hỗ trợ hàm và thủ tục, nhờ đó có một thủ tục hoặc hàm có thể có lời gọi đến chính hàm đó và quan trọng hơn là tư duy người lập trình phải xem xét và nhận ra đó là đệ qui.

Thiết kế giải thuật đệ qui cho một số bài toán

  1. Chương trình tính hàm n!  Nhận thấy: điểm dừng của giải thuật này là khi n=0. Khi đó, giá trị của hàm sẽ có thể tính ngày mà không cần phải đệ qui. Nếu điều kiện dừng không thỏa mãn, sẽ có lời gọi đệ qui hàm giai thừa với tham số là n-1, nhỏ hơn tham số ban đầu một đơn vị. Code :

    int giaithua(int n) { if (n == 0) return 1; else { return giaithua(n - 1)*n; } }
  2. Chương trình hàm tìm ước chúng lớn nhất của 2 số nguyên dương a, b. Nhận xét: Điểm dừng của giải thuật là khi b=0. Khi đó ước chung lớn nhất( UCLN) của a và b chính là 0 vì 0 chia hết cho mọi số. Khi b khác 0 thì sẽ lời gọi đệ qui sẽ là UCLN(a, a%b). Sau mỗi lần gọi đệ qui, các tham số sẽ nhỏ đần di và sau 1 số hữu hạn lời gọi tham số nhỏ hơn sẽ bằng 0. Đó chính là điểm dừng của giải thuật. Code:

    int UCLN(int a,int b) { if (b == 0) return a; else { return UCLN(a, a%b); } }

    Trên đây là khái niệm đơn giản về đệ qui và một số ví dụ về giải thuật của các bài toán có dạng đệ qui. Các ví dụ trên đây khá cơ bản, các bạn có thể tìm hiểu thêm một số bài toán đệ qui kinh điển như Tháp Hà Nội, bài toán 8 hậu,… Trong quá trình tìm hiểu nếu có vấn đề các bạn có thể để lại bình luận để được giúp đỡ. Hẹn gặp lại ở các bài viết sau ở chủ đề Cấu trúc dữ liệu và giải thuật. Chúc các bạn thành công!

RELATED ARTICLESMORE FROM AUTHOR

C/C++

Sự khác nhau giữa Inline function và Macro trong C

C/C++

Trong ngôn ngữ C/C++ có bao nhiêu vùng nhớ (Memory layout)

C/C++

Cấu trúc dữ liệu danh sách nhân viên

C/C++

Tổng quan File trong C

C/C++

Cấu trúc kiểu dữ liệu sinh viên

C/C++

Cấu trúc mô tả một điểm trên tọa độ xOy

LEAVE A REPLY Cancel reply

Log in to leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Danh sách các bài học

Các kiểu dữ liệu cơ bản trong ngôn ngữ C/C++

Mr Good - April 16, 2016 0

Hướng dẫn Tạo Project Visual C++ trong Visual Studio 2012

April 16, 2016

Biến-Hằng-Câu lệnh và biểu thức trong C/C++

April 16, 2016

Cấu trúc IF-ELSE

April 16, 2016

Cấu trúc switch – case

April 16, 2016

Vòng lặp For

April 16, 2016

Cấu trúc While, Do-while

April 16, 2016

Cách sử dụng hàm trong lập trình

April 16, 2016

Mảng một chiều

April 16, 2016 Load more

Bài viết mới nhất

Download

Download Cisco Packet Tracer

Windows 10

Hướng dẫn cài đặt webserver trên localhost để chạy wordpress

HPE

Hướng dẫn cấu hình IP ILO máy chủ HP DL380 Gen10

CentOS

CentOS 8 – Giới thiệu về hệ điều hành Linux (P1)

Load more © Copyright 2016, All Rights Reserved. Donations are always appreciated! MEW: 0x296f1a39d5Ca3cb83C76724eA38af3B90B90109D MORE STORIES

Hướng dẫn bảo mật hai lớp tài khoản trên Gmail

Lê Bảo Hoàng - August 24, 2016 0

Santander đưa ra ứng dụng Ripple-Powered ở 4 quốc gia

Nam Nguyen - February 4, 2018 0

Từ khóa » Cấu Trúc Dữ Liệu Và Giải Thuật đệ Quy