Đệ quy và lặp lại - Bàn về thuật tuán

Nội dung bài viết

Đệ quy và lặp lại đó là hai thuật toán mà có thể nói trong vòng đời của một developer hay programer cũng sẽ gặp ít nhất một lần trong đời. Sử dụng đệ quy và vòng lặp như thế nào thì tuỳ vào mỗi trưởng hợp hay mỗi cá nhân lập trình.

Còn ở bài viết này, chúng ta sẽ đi tìm hiểu giống và khác nhau giữa đệ quy và vòng lặp. Đệ quy và vòng lặp ảnh hưởng đến performance code của bạn như thế nào? Ở đây chỉ có bàn luận, chứ không thể kết luận. Vì chúng tôi biết, những con cá mập luôn ở dưới đáy, nhường chỗ cho những con cá lòng tong luôn hau háu nổi trên mặt nước(???).

Đệ quy - Vòng lặp

Đệ quy

Đệ quy và lặp lại cả hai đều xuất hiện rất nhiều trong các vấn đề giải quyết thuật toán lập trình. Nhưng trước hết để chúng ta hiểu thì chúng ta cần đi xem xét một ví dụ sau:

Tìm hiểu về đệ quy Example đệ quy và vòng lặp

Sau khi chúng ta xem xong ví dụ trên thì có thể thấy Đệ quy đơn giản là một method call trong đó phương thức được gọi giống như cuộc gọi thực hiện cuộc gọi trong khi lặp là khi một vòng lặp được lặp lại cho đến khi một điều kiện nhất định được đáp ứng. Hay nói cách khác là đệ quy chính là khi một câu lệnh trong hàm gọi chính nó và lặp đi lặp lại cho đến khi có một điều kiện được đáp ứng. đó chính là return n;

Theo ví dụ trên chúng ta có thể thấy, hoạt động của một đệ quy xảy ra khi lần lượt gọi chính nó để xử lý bài toán cho đến khi n = 1. là chấm dứt.

Note: Factorial không phải hầm hố gì đâu, nó chính là giai thừa. Giai thừa là một hoạt động nhân của một số tự nhiên, nhân cho số tự nhiên nhỏ hơn chính nó... bla..bla không biết định nghĩa có đúng không nữa, học lâu lắm rồi ... kakakaa

đệ quy

Vòng lặp (iterative)

Đối với iterative thì chúng ta đã quen hơn cho nên không cần giải thích nhiều nữa, Các câu lệnh lặp này thường có dạng:

  • for statement
  • for in statement
  • for of statement
  • while statement
  • do…while statement

Bên cạnh các câu lệnh lặp được đề cập ở trên, còn có các phương thức mảng lặp, chẳng hạn như:

  • forEach
  • map
  • filter
  • reduce

Khi sử dụng những methods này thi điều khác biệt đối với những statement trên đó là những phương thức này yêu cầu một function callbacks trong khi xử lý dữ liệu mà thôi. Đây là sự khác biệt cơ bản trong cách các phương thức mảng lặp này hoạt động so với các câu lệnh lặp truyền thống ở trên như chúng ta đã thấy.

Nói tóm lại: Khái niệm Recursion và Iteration là thực thi một bài toán mà có sự lặp đi lặp lại đến khi có một điều kiện để kết thúc vòng lặp đó. Sự khác biệt giữa chúng là đệ quy đơn giản là một method call trong đó method được gọi là chính là phương thức thực hiện ngay lúc đầu. Cả đệ quy và lặp đều phụ thuộc vào một điều kiện để biết khi nào nên dừng nhưng đệ quy chỉ đơn giản là một quá trình, luôn được áp dụng cho một hàm.


Code Exmaple

//iterative factorial by anonystick.com
const iterativeFactorial = n => {
	let res = 1;
  for(let i = n ; i > 0 ; i--){
  	res = res * i;
  }
  return res;
}

console.log(iterativeFactorial(5)); //120

// recursive Factorial by anonystick.com
const recursiveFactorial = n => {
	if(n === 1){
  	return n;
  }
  return n * recursiveFactorial(n - 1 );
}

console.log(recursiveFactorial(5)); //120

Sự khác nhau giữa Đệ quy - Vòng lặp

  • Trong đệ quy, một câu lệnh có điều kiện quyết định kết thúc quá trình, trong khi đó vòng lặp kết thúc khi các biến của vòng lặp quyết định.(điều này có vẻ không đúng với khi sử dụng while loop)
  • Sử dụng đệ quy vô hạn thì ảnh hưởng tới memomry system, còn vòng lăp - iterative ảnh hưởng tới CPU cycles
  • Đệ quy có thể tốn kém hơn lặp lại trong cả thời gian xử lý và không gian bộ nhớ.
  • Đệ quy có thể thấy là nhìn code rất gọn gàng, còn iterative thì trông dài dòng và luộn thuộm
  • Đệ quy có thể phù hợp hơn với functional programming, còn iterative thì chạy độc lập thì có vẻ ngon hơn

Như vậy thì qua bài viết trên thì chúng ta đã có một cái nhìn tổng thể và hiểu sự giống và khác nhau khi sử dụng đệ quy và vòng lặp rồi. Nhưng còn một điều nữa mà chúng ta chưa nói đến đó là khi nào nên sử dụng đệ quy thay cho vòng lặp?

Khi nào nên sử dụng hàm đệ quy.

Bài sau sẽ rõ.... kakaka

Thanks for reading!!!

Vì do đây là một định nghĩa rộng cho nên chúng tôi có tham khảo một số bài viết sau, chính vì vậy các bạn cũng nên tham khảo tạid đây:



https://medium.com/

https://softwareengineering.stackexchange.com

https://stackoverflow.com