Cho ví dụ về một giải thuật đệ quy

Bài viết được sự cho phép của tác giả Nguyễn Việt Hưng

Làm sao để in ra từ 1 đến 10 bằng hàm đệ quy?

Recursive function [hàm đệ quy] là function mà nó tự gọi chính nó. Phần định nghĩa function trông như thế này:

def foo[]: dosomething[] foo[] # gọi chính nó maybedosomething[] return otherthing

Recursion là một lối suy nghĩ, một cách lập trình rất phổ biến trong functional programming [lập trình hàm] nhưng ở thế giới còn lại, nó không thực sự phổ biến hay có vẻ quen thuộc. Quan điểm về viết recursive function cũng khác nhau, có người bảo dễ, có người mãi không hiểu gì. Và nếu bạn thuộc nhóm không hiểu gì, thì không phải do bạn dốt, chỉ là chưa quen thôi.

  10 Bí quyết tuyển dụng giúp bạn tăng tỉ lệ nhận offer tức thì!

  3 chỉ số quan trọng đánh giá quy trình tuyển dụng

Đề bài: Cho số nguyên dương N, viết function in ra màn hình từ 1 đến N.

Lời giải:

Cách bình thường:

def lprint[n]: ''' Prints from 1 to n the loop way ''' for i in range[1, n+1]: print[i] lprint[3]

Còn đây cách đệ quy:

def rprint[n]: ''' Prints from 1 to n recursive way ''' if n == 0: return else: rprint[n-1] print[n] rprint[3]

Output:

1 2 3

Nếu bạn không hiểu đoạn code trên thực sự làm gì qua từng bước, hãy xem phiên bản chỉnh sửa một chút để in ra giải thích sau:

INPUT = 10 def rprint2[n]: pad = 3 * ' ' * [INPUT - n] print['%sInside function with %d' % [pad, n]] if n == 0: return else: print['%s calling rprint2[%d]' % [pad + '|' + '_', n-1]] rprint2[n-1] print['%s| printing %d' % [pad, n]] print[n] return rprint2[INPUT]

Output:

Inside function with 10 |_ calling rprint2[9] Inside function with 9 |_ calling rprint2[8] Inside function with 8 |_ calling rprint2[7] Inside function with 7 |_ calling rprint2[6] Inside function with 6 |_ calling rprint2[5] Inside function with 5 |_ calling rprint2[4] Inside function with 4 |_ calling rprint2[3] Inside function with 3 |_ calling rprint2[2] Inside function with 2 |_ calling rprint2[1] Inside function with 1 |_ calling rprint2[0] Inside function with 0 | printing 1 1 | printing 2 2 | printing 3 3 | printing 4 4 | printing 5 5 | printing 6 6 | printing 7 7 | printing 8 8 | printing 9 9 | printing 10 10

Hãy đọc từ trên xuống dưới, chậm rãi, để hiểu chuyện gì đã xảy ra. Nếu vẫn chưa hiểu?

Hãy đọc lại từ đầu!

Ví dụ trên chỉ nhằm minh hoạ recursive function làm việc như thế nào, chứ không có lợi ích gì khi viết hàm recursive trong trường hợp này.

Recursive function sẽ trở nên rất hữu dụng nếu vấn đề được định nghĩa theo cách đệ quy [các hàm toán học], giải bài toán Tháp Hà Nội, hay chỉ đơn giản là muốn tiến gần hơn một bước đến Functional programming.

Link Jupyter notebook

Bài viết gốc được đăng tải tại pymi.vn

Có thể bạn quan tâm:

Xem thêm Việc làm Developer hấp dẫn trên TopDev

Đệ quy [Recursion] là một trong những giải thuật khá quen thuộc trong lập trình, mở rộng ra là trong toán học [thường được gọi với tên khác là “quy nạp”]. Có một số bài toán, buộc phải sử dụng đệ quy mới giải quyết được, chẳng hạn như duyệt cây.

Đệ quy là gì?

Một đối tượng được mô tả thông qua chính nó được gọi là mô tả đệ quy.

Một bài toán mang tính chất đệ quy khi nó có thể được phân rã thành các bài toán nhỏ hơn nhưng mang cùng tính chất với bài toán ban đầu, các bài toán nhỏ lại được phân rã thành các bài toán nhỏ hơn nữa theo cùng tính chất đó.

Trong đời sống, cũng thường xuyên thấy một số hiện tượng đệ quy, ví dụ như hai chiếc gương đặt đối diện nhau, vòng xoắn ốc [trong vòng xoắn ốc có vòng xoắn ốc nhỏ hơn].

Trong ảnh có ảnh trong ảnh...

Hàm đệ quy

Trong lập trình, một hàm được gọi là đệ quy khi nó gọi chính nó trong thân hàm.

Ví dụ:

void recusion[] { recusion[]; }

Hàm đệ quy không thể gọi tới nó mãi, cần phải có một điểm dừng [còn gọi là điểm neo] tại một trường hợp đặc biệt, gọi là trường hợp suy biến [degenerate case].

* Đọc thêm bài Memory Segment để nắm được nguyên lý sâu hơn - khi một hàm được gọi, nó sẽ được đưa vào Stack, hàm đệ quy cũng vậy, mỗi lần gọi chính nó thì nó lại được đưa vào Stack, nếu như không có điểm dừng, hoặc gọi mãi mà chưa tới điểm dừng, sẽ dễ xảy ra tình trạng tràn bộ nhớ Stack.

Thành phần của một hàm đệ quy

Hàm đệ quy gồm 2 phần:

• Phần cơ sở: Điều kiện thoát khỏi đệ quy.
• Phần đệ quy: Thân hàm có chứa lời gọi đệ quy.

Thiết kế giải thuật đệ quy

Thực hiện 3 bước sau:

1. Tham số hóa bài toán [xác định các tham số cần truyền và lấy ra].
2. Phân tích trường hợp chung: đưa bài toán về bài toán nhỏ hơn cùng loại, dần dần tiến tới trường hợp suy biến.
3. Tìm trường hợp suy biến [điểm dừng].

Ưu và nhược điểm

Đệ quy có ưu điểm là thuận lợi cho việc biểu diễn bài toán, đồng thời làm gọn chương trình. Tuy nhiên cũng có nhược điểm, đó là không tối ưu về mặt thời gian [so với sử dụng vòng lặp], gây tốn bộ nhớ và có thể tràn stack nếu không kiểm soát tốt độ sâu của đệ quy.

Một số loại đệ quy

Đệ quy tuyến tính [Linear Recursion]

Mỗi lần thực thi chỉ gọi đệ quy một lần

Một ví dụ rất quen thuộc là hàm tính giai thừa:

int factorial[int n] { if [n == 0] return 1; else return n * factorial[n - 1]; // Linear Recursion }

Đệ quy nhị phân [Binary Recursion]

Mỗi lần thực thi có thể gọi đệ quy 2 lần

Ví dụ: Tính tổ hợp chập K của N bằng đệ quy:

int combine[int n, int k] { if [k == 0 || k == n] return 1; else return combine[n - 1, k] + combine[n - 1, k - 1]; // Binary Recursion }

Đệ quy lồng [Nested Recursion]

Tham số trong lời gọi đệ quy là một lời gọi đệ quy, đệ quy lồng chiếm bộ nhớ rất nhanh.

Ví dụ về hàm Ackerman

int ackerman[int m, int n] { if [m == 0] return [n + 1]; else if [n == 0] return ackerman[m - 1, 1]; else return ackerman[m - 1, ackerman[m, n - 1]]; // Nested Recursion }

Đệ quy hỗ tương [Mutual Recursion]

Các hàm gọi đệ quy lẫn nhau

Ví dụ xét tính chẵn lẻ của một số nguyên dương bằng đệ quy.

bool isEven[unsigned int n] { if [n == 0] return true; else return isOdd[n - 1]; } bool isOdd[unsigned int n] { if [n == 1] return true; else return isEven[n - 1]; }

Để sử dụng đệ quy tương hỗ, cần phải khai báo function prototype vì thứ tự hiện thực hàm.

Quay lui [Backtracking]

Trong lập trình, có một chiến lược giải bài toán một cách đầy đủ nhất, đảm bảo đủ mọi trường hợp bằng phương pháp Thử và Sai [Try and Error].

Nét đặc trưng của phương pháp này là ở chỗ các bước đi đến lời giải hoàn toàn bằng cách làm thử. Nếu có một lựa chọn được chấp nhận thì ghi nhớ các thông tin cần thiết các bước thử tiếp theo. Trái lại, nếu không có một lựa chọn nào thích hợp thì làm lại bước trước, xoá bớt các ghi nhớ và quay về chu trình thử với các lựa chọn còn lại. Hành động này được gọi là quay lui [Back tracking] và các giải thuật thể hiện phương pháp này gọi là các giải thuật quay lui.

Việc quay lui để thử tất cả các tổ hợp có thể có để đạt được lời giải cuối cùng.

Bài toán điển hình là liệt kê các cấu hình, mỗi cấu hình được xây dựng bằng cách xây dựng từng phần tử, mỗi phần tử được chọn bằng cách thử tất cả các khả năng.

Để cho dễ hiểu, xét bài toán cụ thể sau:

Bài toán N-Hậu [N-Queen]

Đặt N quân hậu lên trên một bàn cờ có kích thước NxN ô, sao cho không quân hậu nào ăn được quân hậu nào. Hay nói cách khác là không có hai quân hậu bất kì nào trên cùng một hàng, một cột hoặc một đường chéo.

Sử dụng đệ quy quay lui để giải bài toán như sau:

//N-Queen Problem in C++ Program #include using namespace std; #define QUEEN_SIGN 'Q' #define BLANK_SIGN '_' #define N 8 // Set a Board with all Blank void setBoardBlank[char Board[N][N]] { for [int i = 0; i < N; i++] for [int j = 0; j < N; j++] Board[i][j] = BLANK_SIGN; } // Print a Board to screen void printBoard[char Board[N][N]] { for [int i = 0; i < N; i++] for [int j = 0; j < N; j++] cout = 0]; i--, j--] if [Board[i][j] == QUEEN_SIGN] return false; for [int i = RowIndex, j = ColumnIndex; [i < N] && [j < N]; i++, j++] if [Board[i][j] == QUEEN_SIGN] return false; // Check safe at second diagonal for [int i = RowIndex, j = ColumnIndex; [i >= 0] && [j < N]; i--, j++] if [Board[i][j] == QUEEN_SIGN] return false; for [int i = RowIndex, j = ColumnIndex; [i < N] && [j >= 0]; i++, j--] if [Board[i][j] == QUEEN_SIGN] return false; return true; } // Solve N-Queen Problem, Backtracking here! bool solveNQueenProblem[char Board[N][N], int RowIndex] { if [RowIndex >= N] return true; for [int j = 0; j < N; j++] if [isQueenSafeAtPosition[Board, RowIndex, j] == true] { Board[RowIndex][j] = QUEEN_SIGN; if [solveNQueenProblem[Board, RowIndex + 1] == true] return true; else Board[RowIndex][j] = BLANK_SIGN; } return false; } // Entry Point int main[] { char Board[N][N]; setBoardBlank[Board]; if [solveNQueenProblem[Board, 0] == false] cout