Hàm đệ quy: Giai thừa

Thuộc phần Logic và luồng điều khiển trong hành trình Dart của Coddy. Bài học 49 trên 65.

Giai thừa của một số là phép toán kinh điển trong toán học, rất phù hợp để minh họa đệ quy (recursion). Giai thừa của số nguyên dương n (viết là n!) là tích của tất cả các số nguyên dương từ 1 đến n. Ví dụ, 5! = 5 × 4 × 3 × 2 × 1 = 120.

Điều khiến giai thừa rất phù hợp với đệ quy là bài toán này tự nhiên phân tách thành những bài toán nhỏ hơn nhưng giống hệt nhau. Để tính 5!, bạn có thể nghĩ rằng 5! bằng 5 × 4!. Còn 4! chỉ là 4 × 3!, và cứ tiếp tục như vậy. Quy luật này tiếp diễn cho đến khi bạn đạt đến 1!, bằng 1.

int factorial(int n) {
  if (n <= 1) {
    return 1; // Trường hợp cơ sở
  }
  
  return n * factorial(n - 1); // Bước đệ quy
}

Trường hợp cơ sở dừng đệ quy khi n <= 1 và trả về 1. Bước đệ quy nhân số hiện tại với giai thừa của số nhỏ hơn tiếp theo. Khi bạn gọi factorial(5), hàm trả về 5 * factorial(4), giá trị này trả về 5 * 4 * factorial(3), và cứ tiếp tục như vậy cho đến khi đạt đến trường hợp cơ sở.

Cách tiếp cận này cho thấy đệ quy giải quyết vấn đề một cách tinh tế bằng cách rút gọn chúng thành những phiên bản đơn giản hơn của cùng một vấn đề, giúp các phép tính phức tạp trở nên tự nhiên và trực quan.

Thử thách

Dễ

Tạo một chương trình tính giai thừa của nhiều số bằng đệ quy. Chương trình sẽ minh họa hàm giai thừa đệ quy bằng cách xử lý một danh sách số và tính giai thừa của từng số.

Đọc chuỗi đầu vào chứa các số được phân tách bằng dấu phẩy (ví dụ: "3,5,0,7")
Tách chuỗi đầu vào thành các số riêng lẻ và chuyển từng số thành số nguyên
Tạo một hàm đệ quy có tên factorial, nhận tham số số nguyên n
Hàm factorial cần thực hiện logic sau:

Trường hợp cơ sở: Nếu n nhỏ hơn hoặc bằng 1, trả về 1
Bước đệ quy: Trả về n nhân với factorial(n - 1)

Với mỗi số trong danh sách đầu vào, hãy tính giai thừa bằng hàm đệ quy của bạn
Hiển thị kết quả, gồm mỗi số và giai thừa tương ứng
Tính và hiển thị tổng của tất cả các kết quả giai thừa

Ví dụ, nếu đầu vào là "4,3,2", chương trình của bạn sẽ in ra:

Factorial Calculator
====================
Processing numbers: [4, 3, 2]
====================
Factorial Results:
4! = 24
3! = 6
2! = 2
====================
Sum of all factorials: 32
Calculation completed successfully

Nếu đầu vào là "5,0,1", chương trình của bạn sẽ in ra:

Factorial Calculator
====================
Processing numbers: [5, 0, 1]
====================
Factorial Results:
5! = 120
0! = 1
1! = 1
====================
Sum of all factorials: 122
Calculation completed successfully

Nếu đầu vào là "6", chương trình của bạn sẽ in ra:

Factorial Calculator
====================
Processing numbers: [6]
====================
Factorial Results:
6! = 720
====================
Sum of all factorials: 720
Calculation completed successfully

Chương trình cần triển khai hàm đệ quy factorial, hàm này tự gọi lại với các giá trị giảm dần cho đến khi đạt trường hợp cơ sở. Hàm cần minh họa cách đệ quy chia phép tính giai thừa thành các bài toán con nhỏ hơn nhưng giống nhau. Dùng nội suy chuỗi để định dạng kết quả giai thừa thành "$n! = $result". Hãy nhớ rằng 0! bằng 1 theo định nghĩa toán học, và trường hợp cơ sở cần xử lý đúng điều này.

Tự làm thử

import 'dart:io';

// TODO: Tạo hàm (function) tính giai thừa bằng đệ quy tại đây

void main() {
  // Đọc chuỗi đầu vào chứa các số phân tách bằng dấu phẩy
  String? input = stdin.readLineSync();
  
  // Tách đầu vào và chuyển thành các số nguyên
  List<int> numbers = input!.split(',').map((str) => int.parse(str.trim())).toList();
  
  // TODO: Viết code bên dưới để:
  // 1. Xử lý từng số bằng hàm tính giai thừa
  // 2. Tính tổng các giai thừa
  // 3. Hiển thị kết quả theo định dạng yêu cầu
  
  print("Factorial Calculator");
  print("====================");
  print("Processing numbers: $numbers");
  print("====================");
  print("Factorial Results:");
  
  // TODO: Tính và hiển thị kết quả giai thừa tại đây
  
  print("====================");
  // TODO: Hiển thị tổng các giai thừa
  print("Calculation completed successfully");
}