Cơ Bản Về đệ Qui (Recursion) Trong Cấu Trúc Dữ Liệu Và Giải Thuật

Có thể bạn quan tâm

Cấu trúc dữ liệu và giải thuật
Giới thiệu
Cấu trúc dữ liệu là gì ?
Cài đặt môi trường

Một số khái niệm về Giải thuật
Giải thuật là gì ?
Giải thuật tiệm cận - Asymptotic Algorithms
Giải thuật tham lam - Greedy Algorithms
Giải thuật chia để trị - Divide and Conquer
Giải thuật qui hoạch động - Dynamic Programming
Giải thuật định lý thợ - Master Theorem

Cấu trúc dữ liệu mảng (Array)
Cấu trúc dữ liệu mảng (Array)

Danh sách liên kết - Linked Lists
Danh sách liên kết - Linked List
Danh sách liên kết đôi - Doubly Linked List
Danh sách liên kết vòng - Circular Linked List

Ngăn xếp & Hàng đợi
Cấu trúc dữ liệu ngăn xếp - Stack
Cấu trúc dữ liệu hàng đợi - Queue

Một số Giải thuật tìm kiếm
Tìm kiếm tuyến tính - Linear Search
Tìm kiếm nhị phân - Binary Search
Tìm kiếm nội suy - Interpolation Search
Cấu trúc dữ liệu Hash Table

Một số Giải thuật sắp xếp
Giải thuật sắp xếp
Sắp xếp nổi bọt - Bubble Sort
Sắp xếp chèn - Insertion Sort
Sắp xếp chọn - Selection Sort
Sắp xếp trộn - Merge Sort
Giải thuật Shell Sort
Sắp xếp nhanh - Quick Sort
Quay lui - Back Tracking

Cấu trúc dữ liệu đồ thị (Graph)
Cấu trúc dữ liệu đồ thị
Tìm kiếm theo chiều sâu - Depth First Traversal
Tìm kiếm theo chiều rộng - Breadth First Traversal

Cấu trúc dữ liệu cây
Cấu trúc dữ liệu cây
Duyệt cây - Tree Traversal
Cây tìm kiếm nhị phân - Binary Search Tree
Cây AVL - AVL Tree
Cây Slay - splay Tree
Giải thuật Cây khung - Spanning Tree
Cấu trúc dữ liệu Heap

Đệ qui (Recursion)
Khái niệm cơ bản về Đệ qui
Bài toán Tháp Hà Nội - Tower of Hanoi
Dãy Fibonacci

Tài liệu tham khảo
Học lập trình C
Học lập trình C++
Học lập trình Java

Khái niệm cơ bản về đệ qui (Recursion) Trang trước Trang sau

Đệ qui (Recursion) là gì ?

Một số ngôn ngữ lập trình cho phép việc một module hoặc một hàm được gọi tới chính nó. Kỹ thuật này được gọi là Đệ qui (Recursion). Trong đệ qui, một hàm a có thể: gọi trực tiếp chính hàm a này hoặc gọi một hàm b mà trả về lời gọi tới hàm a ban đầu. Hàm a được gọi là hàm đệ qui.

Ví dụ: một hàm gọi chính nó

int function(int value) { if(value < 1) return; function(value - 1); printf("%d ",value); }

Ví dụ: một hàm mà gọi tới hàm khác mà trả về lời gọi tới hàm ban đầu

int function(int value) { if(value < 1) return; function(value - 1); printf("%d ",value); } Quảng cáo

Đặc điểm của hàm đệ qui

Một hàm đệ qui có thể tiếp tục diễn ra vô số lần giống như một vòng lặp vô hạn. Để tránh điều này, bạn phải ghi nhớ hai thuộc tính sau của hàm đệ qui:

Điều kiện cơ bản: phải có ít nhất một điều kiện để khi mà gặp điều kiện này thì việc gọi chính hàm đó (gọi đệ qui) sẽ dừng lại.
Tiệm cận: mỗi khi hàm đệ qui được gọi thì nó càng tiệm cận tới điều kiện cơ bản.

Sự triển khai hàm đệ qui

Nhiều ngôn ngữ lập trình triển khai sự đệ qui theo cách thức của các ngăn xếp (stack). Nói chung, mỗi khi một hàm (hàm gọi – caller) gọi hàm khác (hàm được gọi – callee) hoặc gọi chính nó (callee), thì hàm caller truyền điều khiển thực thi tới callee. Tiến trình truyền này cũng có thể bao gồm một số dữ liệu từ caller tới callee.

So sánh đệ qui và vòng lặp

Ai đó có thể nói rằng tại sao lại sử dụng đệ qui trong khi sử dụng vòng lặp cũng có thể làm được các tác vụ tương tự. Lý do đầu tiên là đệ qui làm cho chương trình dễ đọc hơn và với các hệ thống CPU cải tiến ngày nay thì đệ qui là hiệu quả hơn rất nhiều khi so với các vòng lặp.

Độ phức tạp thời gian (Time complexity) của hàm đệ qui

Với vòng lặp, chúng ta lấy số vòng lặp để tính độ phức tạp thời gian. Tương tự với đệ qui, giả sử mọi thứ là hằng số, chúng ta tính thời gian một lời gọi đệ qui được tạo ra. Một lời gọi được tạo ra tới một hàm sẽ là Ο(1), Do đó với n là thời gian một lời gọi đệ qui được tạo ra thì độ phức tạp thời gian hàm đệ qui sẽ là Ο(n).

Độ phức tạp bộ nhớ (Space complexity) của hàm đệ qui

Độ phức tạp bộ nhớ được ước lượng dựa vào lượng bộ nhớ cần thêm cho một module được thực thi. Với vòng lặp, trình biên dịch hầu như không cần thêm bộ nhớ. Trình biên dịch sẽ tự cập nhật giá trị của biến được sử dụng ngay trong vòng lặp. Nhưng với đệ qui, hệ thống cần lưu giữ các bản ghi động mỗi khi một lời gọi đệ qui được tạo. Do đó có thể nói rằng, độ phức tạp bộ nhớ của hàm đệ qui là cao hơn so với vòng lặp.

👉 Giải bài nhanh với AI Hay:

Đã có app VietJack trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng....miễn phí. Tải ngay ứng dụng trên Android và iOS. Theo dõi chúng tôi miễn phí trên mạng xã hội facebook và youtube:

Follow fanpage của team https://www.facebook.com/vietjackteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.vietjack để tiếp tục theo dõi các loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile.... mới nhất của chúng tôi.

Bài học Cấu trúc dữ liệu và giải thuật phổ biến tại vietjack.com: