Giới thiệu
Recursive (đệ quy) là một khái niệm khá đơn giản mà chúng ta đã tiếp xúc từ toán lớp 3:
Bây giờ chắc bạn cũng có thể mường tượng đệ quy là gì rồi phải không? Đây là một quyển sách toán lớp 3, ở trong bìa sách có ba học sinh, trong đó có một học sinh lại cầm một quyển sách toán lớp ba khác. Và trong quyển sách đó lại có ba học sinh, và cũng có một học sinh cầm một quyển sách lớp 3. Đây chính là ví dụ cho một khái niệm rất căn bản trong bất kỳ ngôn ngữ lập trình nào – khái niệm “đệ quy”.
Đệ quy là gì?
Trong Khoa học máy tính, hàm đệ quy là hàm gọi chính bản thân nó. Một hàm đệ quy sẽ có dạng như sau:
{ dosomething(); foo(); maybedosomething();
function
foo
()return
otherthing; }Code language:
JavaScript
(
javascript
)
Để hiểu rõ hơn mình sẽ ví dụ thực tế như sau:
Giáo viên thể dục yêu cầu lớp điểm danh từ 1 đến hết
Trình tự xảy ra sẽ như sau giả sử lớp có có 5 người:
1 2 3 4 5 Hết !!!!
Code:
{
function
diemdanh
(n
)for
(let
i =1
; i <= n; i++) {console
.log(i); }console
.log('Hết !!!!'
); } diemdanh(5
);Code language:
JavaScript
(
javascript
)
Nếu bạn không biết vị trí mình đang đứng là thứ mấy, bạn hỏi thằng đứng trước và thằng đó cũng không nhớ và tiếp tục hỏi thằng phía trước…. truyền nhau cho đến thằng đầu hàng và nó hô “1” và những đứa sau đó sẽ truyền thứ tự dần tới đến bạn.
Trình tự như sau:
Thằng đứng thứ 3: Ê tao đang đứng thứ mấy thế ???? Thằng đứng thứ 2: Ê tao đang đứng thứ mấy thế ???? Thằng đứng thứ 1: Tao đang đứng thứ 1 Thằng đứng thứ 2: Thế tao đứng thứ 2 Thằng đứng thứ 3: Thế tao đứng thứ 3
Code:
{
function
my_index
(n
)if
(n ==1
) {console
.log(`Thằng đứng thứ
${n}
: Tao đang đứng thứ 1`); }else
{console
.log(`Thằng đứng thứ
${n}
: Ê tao đang đứng thứ mấy thế ????`); my_index(n -1
);console
.log(`Thằng đứng thứ
${n}
: Thế tao đứng thứ${n}
`); } } my_index(3
);Code language:
JavaScript
(
javascript
)
Ví dụ về Đệ quy trong toán học
Đệ quy thường được áp dụng trong toán học như tính giá trị của một số trong 1 dãy như Fibonacci, giai thừa …. hoặc có thể số mũ.
Dãy Fibonacci
Mỗi phần tử mới trong dãy Fibonacci được tạo ra bằng cách cộng 2 phần tử trước đó. Bằng cách bắt đầu với 0 và 1, 10 phần tử đầu tiên sẽ là:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34,…
Nếu muốn tìm số thứ n của dãy này, đơn giản là gán 2 số đầu tiên của dãy là 0, 1 và tính tổng của số thứ n – 1 và số thứ n – 2.
Code:
{
function
fibo
(n
)if
(n <=1
)return
n;return
fibo(n -1
) + fibo(n -2
);console
.log(fibo(10
));Code language:
JavaScript
(
javascript
)
Kết quả:
88
Giai thừa
Giai thừa được định nghĩa như sau:
n! = n * (n – 1) * (n – 2) * … * 1
Ta có thể dễ dàng nhận ra công thức sau:
n! = n * (n – 1)!
Code:
{
function
factorial
(n
)if
(n ==1
) {return
1
; }return
n * factorial(n -1
);console
.log(factorial(5
));Code language:
JavaScript
(
javascript
)
Kết quả:
120
Số mũ
Công thức vẽ số mũ chắc mọi người đều biết rồi:
a ^ x = tích của x số a
Code:
{
function
pow
(a, x
)if
(a ==0
) && (x ==0
) {return
'Vô nghĩa'
; }else
if
(x ==0
) {return
1
; }else
if
(x ==1
) {return
a; }return
a * pow(a, x -1
);console
.log(pow(2
,5
));Code language:
JavaScript
(
javascript
)
Code chỉ áp dụng trong trường hợp a khác 0 và x thuộc N.
Kết luận
Qua bài viết, chúng ta rút ra bài học gì? Muốn giải 1 bài toán lớn khi lập trình, hãy bắt đầu giải từ những bài toán nhỏ hơn.
Tham khảo:
https://pymi.vn/blog/print-recursively/
https://medium.com/@tung491/recursive-function-v%C3%A0-m%E1%BB%99t-v%C3%A0i-v%C3%AD-d%E1%BB%A5-9a613e6eec27
Các bạn có thể tham khảo các bài viết hay về JavaScript tại đây.
Hãy tham gia nhóm Học lập trình để thảo luận thêm về các vấn đề cùng quan tâm.
Tóm Tắt
Chia sẻ
Bài viết liên quan
