Chương 6 - Hàm( Tiếp *) - Kiến thức Lập trình

Tổ chức được mã nguồn dưới dạng các đơn vị để dễ quản lí và có thể tái sử dụng được

7. Hàm đệ quy

Hàm đệ quy (recursive) là hàm mà có thực hiện lời gọi đến chính nó. Loại hàm này được sử dụng phổ biến trong những tình huống mà chúng ta thực hiện cùng một thao tác nhưng trên các đối tượng khác nhau được phái sinh từ đối tượng trước đó.

Ví dụ:

Sử dụng hàm đệ quy để tính giai thừa của một số.

Công thức tính giai thừa:

0! = 1

n! = n x (n – 1)!; n > 0

Với một số n bất kỳ, việc tính giai thừa của n sẽ được thực hiện như thế nào?

Nếu n = 0 thì trả về kết quả là 1
Nếu n = 1 thì trả về kết quả là 1 (bởi vì 1! = 1 x 0!)
Nếu n = 2 thì trả về kết quả là 2 (bởi vì 2! = 2 x 1!)
…
Xét một cách tổng quát, bài toán tính n! sẽ được đưa về thành bài toán tính (n – 1)!

Hàm tính giai thừa của n có thể được triển khai đơn giản như sau:

1.	function factorial(n) {
2.	   if (n === 0) {
3.	       return 1;
4.	   }
5.	   return n * factorial(n - 1);
6.	}

Trong đoạn mã trên, chúng ta dễ dàng nhận thấy rằng hàm factorial() đã thực hiện lời gọi đến chính nó. Biểu thức n === 0 được gọi là điều kiện dừng (stopping condition) hoặc là trường hợp cơ sở (base case).

Lưu ý: Chúng ta hoàn toàn có thể sử dụng vòng lặp để tính giai thừa của một số. Ví dụ được nêu ra ở đây là để giúp chúng ta dễ hình dung về khái niệm hàm đệ quy.

Lưu ý: Cần rất thận trọng khi đặt điều kiện dừng, bởi vì nếu không có điều kiện dừng hoặc điều kiện dừng không đúng thì có thể dẫn đến tình huống là hàm sẽ được thực thi vô tận. Thử hình dung xem điều gì sẽ diễn ra nếu chúng ta loại bỏ khối lệnh if trong hàm factorial() ở trên.

Chúng ta sẽ còn quay lại làm việc với hàm đệ quy ở trong phần Thuật toán tìm kiếm nhị phân của Chương 7.

8. Bài thực hành

Bài 1: Chuyển đổi nhiệt độ

Mục tiêu:

Luyện tập xây dựng và sử dụng hàm.

Mô tả:

Xây dựng hàm để chuyển đổi từ độ F sang độ C theo công thức sau:

C = (F – 32)/1.8

Giao diện mẫu của ứng dụng như sau:

Hướng dẫn:

Bước 1: Thêm mã HTML tạo form

1.	<p>
2.	 <label>Fahrenheit</label>
3.	 <input id="inputFahrenheit" type="number" placeholder="Fahrenheit"
4.	 oninput="temperatureConverter(this.value)"
5.	 onchange="temperatureConverter(this.value)">
6.	</p>
7.	<p>Celsius: <span id="outputCelsius"></span></p>

Bước 2: Xây dựng hàm temperatureConverter()

Hàm sẽ nhận tham số đầu vào là giá trị cần chuyển đổi. Thực hiện chuyển đổi từ độ F sang C theo công thức C = (F– 32) /1.8

1.	function temperatureConverter(valNum) {
2.	       valNum = parseFloat(valNum);
3.	       document.getElementById("outputCelsius").innerHTML = (valNum-32) / 1.8;
4.	}

Mã nguồn hoàn chỉnh như sau:

1.	<!DOCTYPE html>
2.	<html lang="en">
3.	<head>
4.	   <meta charset="UTF-8">
5.	   <title>Title</title>
6.	</head>
7.	<body>
8.	 
9.	<form>
10.	   <p>
11.	       <label>Fahrenheit</label>
12.	       <input id="inputFahrenheit" type="number" placeholder="Fahrenheit"
13.	              oninput="temperatureConverter(this.value)"
14.	              onchange="temperatureConverter(this.value)">
15.	   </p>
16.	   <p>Celsius: <span id="outputCelsius"></span></p>
17.	</form>
18.	 
19.	<script>
20.	 
21.	   function temperatureConverter(valNum) {
22.	       valNum = parseFloat(valNum);
23.	       document.getElementById("outputCelsius").innerHTML = (valNum-32) / 1.8;
24.	   }
25.	 
26.	</script>
27.	</body>
28.	</html>

Bước 3: Chạy chương trình và quan sát kết quả

Bài 2: Tìm giá trị nhỏ nhất của mảng

Mục tiêu:

Luyện tập tạo và sử dụng hàm, truyền mảng vào hàm.

Mô tả:

Xây dựng hàm nhận vào một tham số là một mảng cho trước. Hàm thực hiện tìm giá trị nhỏ nhất trong mảng và trả về giá trị đó. Sử dụng hàm vừa xây dựng trên với mảng như sau:

arr1: [3, 5, 1, 8, -3, 7, 8]

arr2: [7, 12, 6, 9, 20, 56, 89]

arr3: []

arr4: [0, 0, 0, 0, 0, 0]

Hướng dẫn:

Bước 1: Xây dựng hàm

Các bước thực thi trong hàm:

Giả sử phần tử đầu tiên trong mảng là giá trị nhỏ nhất. Gán giá trị của phần tử này cho biến min.
Duyệt mảng từ phần tử tiếp theo. Kiểm tra nếu giá trị của phần tử tiếp theo trong mảng nhỏ hơn min thì gán min = arr[i] (với i ở vị trí của phần tử tiếp theo)
Kết thúc duyệt mảng, tìm được giá trị min trong mảng. Hàm trả về giá trị min đó.

Code mẫu như sau:

1.	function minArray(arr) {
2.	   let min = arr[0];
3.	   for(var i = 1; i < arr.length; i++){
4.	       if(arr[i] < min){
5.	           min = arr[i];
6.	       }
7.	   }
8.	   return min;
9.	}

Bước 2: Sử dụng hàm

1.	let arr1 = [3, 5, 1, 8, -3, 7, 8];
2.	let min = minArray(arr1);
3.	alert(min);

Bước 3: Chạy chương trình, quan sát kết quả.

Bước 4: Tương tự với mảng được khởi tạo các phần tử mặc định

arr2: [7, 12, 6, 9, 20, 56, 89]

arr3: []

arr4: [0, 0, 0, 0, 0, 0]

Bước 5: Với mảng không có phần tử nào sửa lại hàm minArray để kiểm tra số phần tử trong mảng.

Nếu độ dài mảng bằng 0. Thì trả về -1.

1.	function minArray(arr) {
2.	   if(arr.length == 0)
3.	       return -1;
4.	   let min = arr[0];
5.	 
6.	   for(let i = 1; i < arr.length; i++){
7.	       if(arr[i] < min){
8.	           min = arr[i];
9.	       }
10.	   }
11.	   return min;
12.	}

Vậy khi hàm trả về giá trị -1 ta hiểu rằng mảng này đang rỗng.

Hỏi nhanh:

Tuy nhiên có trường hợp xảy ra là nếu trong mảng có phần tử -1 là phần tử nhỏ nhất thì sẽ xử lý thế nào?

9. Bài tập

Bài 1: Kiểm tra số nguyên tố

Hãy xây dựng chương trình để kiểm tra xem một số nguyên bất kỳ có phải là số nguyên tố hay không. Sau đó tìm tất cả các số nguyên tố nhỏ hơn 10000 và hiển thị ra màn hình.

Lưu ý: Số nguyên tố là số tự nhiên khác 0 chỉ có hai ước số dương phân biệt là 1 và chính nó.

Do số 1 chỉ có một ước số dương là chính nó, nên số 1 không phải là số nguyên tố.

Ví dụ, các số sau đây là số nguyên tố:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97…