[Chủ đề thảo luận] Đệ quy

Trong buổi offline sắp tới (08/01/2017), chúng ta sẽ thảo luận về Thuật toán Đệ quy.

Để buổi thảo luận được diễn ra tốt hơn, các bạn nên tìm hiểu về Thuật toán Đệ quy trước buổi offline.

Một số nguồn tài liệu tham khảo về thuật toán đệ quy:

  1. https://www.stdio.vn/articles/read/111/giai-thuat-de-quy
  2. http://vietjack.com/lap_trinh_c/de_qui_trong_c.jsp

Một số bài tập về đệ quy cơ bản

Các bạn có thể tham khảo và tự code lại để hiểu hơn về thuật toán đệ quy. Đệ quy là một thuật toán khó và mình tin đây là một trong những thuật toán “bước ngoặt” của các bạn trong lập trình. 😀

Bài tập 1: Tìm phần tử Fibonacci thứ n (bài toán Fibonacci)

Như chúng ta đã biết, dãy Finonacci là dãy f có tính chất như sau:

  • f(0) = 0.
  • f(1) = 1.
  • f(2) = 1.
  • f(n) = f(n-1) + f(n-2) với n > 2.

Đó là dãy Fibonacci và các số hạng trong dãy được gọi là các số Fibonacci.

Để viết chương trình đệ quy tìm phần tử thứ n trong dãy Fibonacci, ta có thể xây dựng một hàm trả về số nguyên thứ n như sau:

 

Bài tập 2: Tính X lũy thừa n

Chương trình tính X mũ n với X là số thực, n là số nguyên:

 

Bài 3: Tính n giai thừa

Chương trình tính n! được định nghĩa đệ quy như sau:

 

Tài liệu tham khảo:

The following two tabs change content below.