Ghi nhớ kết quả không dùng đệ quy

Trong bài học trước, chúng ta đã tìm hiểu về kỹ thuật ghi nhớ kết quả (memoization) và cách kỹ thuật này giúp cải thiện độ phức tạp thời gian của các lời giải đệ quy. Trong bài học này, chúng ta sẽ khám phá cách dùng đệ quy với kỹ thuật ghi nhớ kết quả để giải quyết vấn đề hiệu quả hơn.

Đệ quy là một kỹ thuật lập trình, trong đó một hàm gọi chính nó để giải quyết vấn đề. Lời giải đệ quy có thể rất tinh tế và trực quan, nhưng cũng có thể kém hiệu quả, đặc biệt khi cùng một hàm được gọi nhiều lần với cùng các đối số. Đây là lúc kỹ thuật ghi nhớ kết quả phát huy tác dụng. Bằng cách lưu kết quả của những lần gọi hàm trước, chúng ta có thể tránh các phép tính dư thừa và cải thiện đáng kể hiệu suất của lời giải đệ quy.