Chương 6: Các hàm trả lại kết quả

Trở về Mục lục cuốn sách

6.1 Các giá trị được trả về

Một số hàm dựng sẵn mà ta đã dùng, như các hàm toán học, đều trả lại kết quả. Việc gọi hàm sẽ tạo ra một giá trị, mà chúng ta thường gán vào một biến hoặc sử dụng như một phần của một biểu thức.

e = math.exp(1.0)
height = radius * math.sin(radians)

Tất cả các hàm chúng ta đã viết đều là hàm rỗng; chúng chỉ in ra thông tin hoặc di chuyển con rùa, nhưng kết quả mà chúng trả về là None.

Trong chương này, (cuối cùng thì) chúng ta (cũng) viết những hàm có trả lại kết quả. Ví dụ đầu tiên là area, có nhiệm vụ tính diện tích của một hình tròn với bán kính cho trước:

def area(radius):
    temp = math.pi * radius**2
    return temp

Ta đã thấy câu lệnh return từ trước rồi, nhưng trong một hàm trả lại kết quả, lệnh return bao gồm một biểu thức. Câu lệnh này có nghĩa là: “Lập tức trở về chương trình chính và dùng biểu thức bên cạnh để làm giá trị để trả lại”. Vì biểu thức có thể phức tạp tù ý nên chúng ta có thể viết hàm trên gọn lại như sau:

def area(radius):
    return math.pi * radius**2

Tuy vậy, sự có mặt của các biến tạm thời như temp thường làm việc gỡ lỗi được dễ dàng hơn.

Đôi khi ta cần có nhiều câu lệnh return, mỗi lệnh ở một nhánh của lệnh điều kiện:

def absolute_value(x):
    if x < 0:
        return -x
    else:
        return x

Vì các lệnh return này ở các nhánh điều kiện độc lập với nhau, luôn chỉ có một trong số đó được thực hiện.

Ngay khi một lệnh return được thực hiện, hàm sẽ kết thúc ngay mà không thực hiện bất cứ lệnh nào tiếp sau nó. Mã lệnh xuât hiện sau dòng lệnh return, hay nói chung, trong bất cứ chỗ nào khác của chương trình mà không nằm trong luồng thực hiện thì được gọi là mã lệnh chết.

Trong một hàm có trả lại kết quả, ta nên đảm bảo rằng mỗi luồng thực hiện khả dĩ đều dẫn tới một lệnh return. Chẳng hạn:

def absolute_value(x):
    if x < 0:
        return -x
    if x > 0:
        return x

Chương trình này không chính xác vì nếu chẳng may x bằng 0 thì không có điều kiện nào được thoả mãn, và hàm sẽ kết thúc mà không gặp phải lệnh return nào. Nếu dòng thực hiện đến được cuối của hàm thì giá trị trả về sẽ là None, không phải là giá trị tuyệt đối của 0.

>>> print absolute_value(0)
None

Tiện thể cũng lưu ý các bạn rằng Python có sẵn một hàm tên là abs để tính giá trị tuyệt đối.

Bài tập 1

Viết một hàm tên là compare (so sánh) để trả lại 1 nếu x > y, 0 nếu x == y, và -1 nếu x < y.

6.2 Phát triển tăng dần

Khi bạn viết các hàm lớn hơn, có thể bạn sẽ dành nhiều thời gian để gỡ lỗi.

Để giải quyết các chương trình với mức độ phức tạp ngày càng cao, bạn có thể thử một quy trình gọi là phát triển tăng dần. Mục tiêu của phát triển tăng dần là tránh mất thời gian gỡ lỗi bằng cách mỗi lúc chỉ thêm vào và thử nghiệm một đoạn mã lệnh rất ngắn.

Ở ví dụ này, bạn cần tìm khoảng cách giữa hai điểm cho bởi các toạ độ (x₁, y₁) và (x₂, y₂). Theo định lý Py-ta-go, khoảng cách sẽ là:

distance = √((x₂ – x₁)² + (y₂ – y₁)²)
Bước đầu tiên là cân nhắc xem một hàm distance trong Python sẽ trông như thế nào. Nói cách khác, các số liệu đầu vào (tham số) và kết quả (giá trị trả lại) là gì?

Trong trường hợp này, số liệu đầu vào mô tả hai điểm; ta có thể biểu thị chúng bằng bốn số. Giá trị cần trả về là khoảng cách, tức là một giá trị số có phần thập phân.

Bạn đã có thể phác thảo ngay ra hàm như sau:

def distance(x1, y1, x2, y2):
    return 0.0

Dĩ nhiên là mã lệnh trên chưa tính được khoảng cách; nó luôn trả về số không. Nhưng về mặt cú pháp thì nó đúng, và nó chạy được, nghĩa là bạn có thể thử nghiệm nó trước khi làm cho nó phức tạp thêm.

Để thử nghiệm hàm mới viết, hãy gọi nó với các tham số ví dụ:

>>> distance(1, 2, 4, 6)
0.0

Sở dĩ tôi chọn các tham số này vì khoảng cách ngang sẽ là 3 và khoảng cách dọc là 4, theo đó thì kết quả sẽ bằng 5 (cạnh huyền của một tam giác có các cạnh là 3-4-5). Khi thử nghiệm một hàm, bạn nên biết trước kết quả đúng.

Đến lúc này, chúng ta có thể khẳng định rằng hàm đã đúng về mặt cú pháp, và chúng ta sẽ thêm mã lệnh vào phần thân. Một bước làm hợp lí tiếp theo là tính các hiệu số x₂ - x₁ và y₂ - y₁. Đoạn mã tiếp theo sẽ lưu giữ các giá trị trên vào các biến tạm thời và hiển thị chúng.

def distance(x1, y1, x2, y2):
    dx = x2 - x1
    dy = y2 - y1
    print 'dx bằng', dx
    print 'dy bằng', dy
    return 0.0

Nếu hàm số hoạt động được, nó sẽ hiển thị 'dx bằng 3' và 'dy bằng 4'. Nếu vậy, chúng ta biết rằng hàm đã nhận các đối số đúng và thực hiện chính xác phép tính đầu tiên. Nếu không, chúng ta chỉ cần phải kiểm tra một só ít các dòng lệnh.

Tiếp theo chúng ta tính tổng các bình phương của dx và dy:

def distance(x1, y1, x2, y2):
    dx = x2 - x1
    dy = y2 - y1
    dsquared = dx**2 + dy**2
    print 'd bình phương bằng: ', dsquared
    return 0.0

Một lần nữa, bạn có thể chạy đoạn mã này và kiểm tra kết quả thu được (nó phải bằng 25). Cuối cùng, bạn có thể dùng math.sqrt để tính toán và trả lại kết quả:

def distance(x1, y1, x2, y2):
    dx = x2 - x1
    dy = y2 - y1
    dsquared = dx**2 + dy**2
    result = math.sqrt(dsquared)
    return result

Nếu đoạn mã trên hoạt động tốt, bạn đã giải quyết xong. Nếu không, bạn có thể sẽ cần phải in giá trị của result trước câu lệnh return.

Mã lệnh trên là phiên bản cuối cùng của hàm; nó không hiển thị gì khi được chạy mà chỉ trả lại một giá trị. Các câu lệnh print mà chúng ta thêm vào chỉ hữu ích khi gỡ lỗi, nhưng một khi đã viết được hàm rồi thì ta cần phải bỏ chúng đi. Các câu lệnh thêm vào như vậy còn có tên là dàn giáo vì nó có ích cho việc xây dựng chương trình nhưng lại không phải là một phần trong sản phẩm cuối cùng.

Khi mới tập lập trình, mỗi lúc bạn chỉ nên viết thêm một hoặc hai dòng lệnh. Sau này khi đã có kinh nghiệm, bạn sẽ viết và gỡ lỗi những khối lệnh lớn hơn. Dù theo cách nào đi nữa, việc phát triển tăng dần sẽ giúp bạn tiết kiệm nhiều thời gian dành cho gỡ lỗi.

Các điểm cơ bản của quy trình này là:

1. Bắt đầu với một chương trình chạy được và thêm vào những thay đổi nhỏ. Bất cứ lúc nào khi gặp lỗi, bạn sẽ phát hiện được ngay lỗi đó ở đâu.
2. Dùng các biến tạm để lưu giữ các giá trị trung gian, từ đó bạn có thể hiển thị và kiểm tra chúng.
3. Một khi chương trình đã hoạt động, bạn có thể dỡ bỏ các đoạn mã “dàn giáo”, hoặc rút gọn nhiều câu lệnh về một biểu thức phức hợp, nếu việc này không làm cho chương trình trở nên khó đọc hơn.

Bài tập 2

Hãy dùng cách phát triển tăng dần để viết một hàm tên là hypotenuse để trả lại chiều dài của cạnh huyền trong một tam giác vuông khi biết các đối số là chiều dài hai cạnh góc vuông. Hãy ghi lại từng bước phát triển trong quá trình làm.

6.3 Hàm hợp

Đến bây giờ, bạn có thể trông đợi việc gọi một hàm từ bên trong một hàm khác, Việc này được gọi là hợp các hàm.

Với ví dụ dưới đây, ta sẽ viết một hàm nhận vào hai điểm là tâm của đường tròn và một điểm trên đường tròn đó, rồi tính diện tích của hình tròn.

Giả sử như toạ độ của tâm điểm được lưu trong các biến xc và yc, toạ độ điểm trên đường tròn là xp và yp. Bước đầu tiên sẽ là tìm bán kính của đường tròn, vốn là khoảng cách giữa hai điểm đó. Ta vừa mới viết một hàm, distance, để làm việc này:

radius = distance(xc, yc, xp, yp)

Bước tiếp theo là tìm diện tích của một đường tròn có bán kính đó; chúng ta cũng vừa viết một hàm thực hiện điều này:

result = area(radius)

Kết hợp hai bước này vào trong cùng một hàm, ta thu được:

def circle_area(xc, yc, xp, yp):
    radius = distance(xc, yc, xp, yp)
    result = area(radius)
    return result

Các biến tạm thời radius và result có ích cho việc phát triển và gỡ lỗi chương trình, nhưng một khi chương trình đã hoạt động tốt, ta có thể rút gọn nó lại bằng cách kết hợp các lời gọi hàm:

def circle_area(xc, yc, xp, yp):
    return area(distance(xc, yc, xp, yp))

Các hàm có thể trả lại giá trị Boole, vốn rất tiện dụng cho việc ẩn giấu các phép kiểm tra phức tạp vào trong một hàm. Chẳng hạn:

def is_divisible(x, y):
    if x % y == 0:
        return True
    else:
        return False

Một cách làm thông thường là đặt tên các hàm Boole cho giống với các câu hỏi có/không. Chẳng hạn (tiếng Anh: có chia hết) is_divisible trả lại True hoặc False để chỉ định rằng x có chia hết cho y hay không.

Sau đây là một ví dụ:

>>>   is_divisible(6, 4)
False
>>>   is_divisible(6, 3)
True

Kết quả của toán tử == là một giá trị Boole, vì vậy ta có thể viết hàm gọn lại bằng cách trả lại giá trị trực tiếp như sau:

def is_divisible(x, y):
    return x % y == 0

Các hàm Boole thường được dùng trong các câu lệnh điều kiện:

if is_divisible(x, y):
    print 'x chia hết cho y'

Có thể bạn sẽ muốn viết:

if is_divisible(x, y) == True:
    print 'x is divisible by y'

Nhưng phép so sánh thêm là hoàn toàn thừa.

Bài tập 3

Hãy viết một hàm is_between(x, y, z) trả lại True nếu x ≤ y ≤ z hoặc False trong trường hợp còn lại.

6.4 Nói thêm về đệ quy

Chúng ta mới chỉ tìm hiểu một phần nhỏ của Python, nhưng bạn có thể muốn biết rằng liệu phần nhỏ này có phải là một ngôn ngữ lập trình đầy đủ hay không, có nghĩa là dùng nó có thể diễn giải được mọi bài toán hay không. Bất kì chương trình máy tính nào cũng có thể được viết lại chỉ dùng những đặc điểm ngôn ngữ mà chúng ta đã xét đến (thực ra, bạn cần thêm một số lệnh để điều khiển các thiết bị như bàn phím, chuột, ổ đĩa, v.v…, nhưng đó là tất cả những điều cần thiết).

Việc chứng minh nhận định đó là một bài toán khó, lần đầu được Alan Turing đưa ra.¹ Tương ứng với bài toán này là “luận án Turing”. Để tìm hiểu cặn kẽ về luận án Turing, bạn nên đọc quyển sách Introduction to the Theory of Computation (tạm dịch: “Nhập môn lí thuyết tính toán”) của Michael Sipser.

Để cụ thể hoá tác dụng của những kiến thức lập trình mà bạn vừa được học, chúng ta hãy cùng lập một số hàm toán học theo cách đệ quy. Một định nghĩa đệ quy giống như việc định nghĩa vòng quanh; điểm tương đồng là trong phần định nghĩa lại có tham chiếu đến sự vật được định nghĩa. Nhưng cách định nghĩa vòng quanh thực sự thì không mấy có tác dụng:

frabjous:

Một tính từ được dùng để miêu tả một sự vật frabjous.

Bạn hẳn sẽ bực mình khi thấy một định nghĩa kiểu như vậy trong cuốn từ điển. Ngược lại, khi bạn xem định nghĩa về giai thừa (được kí hiệu bằng dấu !) trong toán học, có thể bạn sẽ thấy:

0! = 1
n! = n(n - 1)!

Định nghĩa này phát biểu rằng giai thừa của 0 là 1, và giai thừa của bất kì một giá trị nào khác, n, thì bằng n nhân với giai thừa của n - 1.

Theo đó, 3! bằng 3 nhân với 2!, vốn lại bằng 2 nhân với 1!, vốn bằng 1 nhân với 0!. Gộp tất cả lại, ta có 3! bằng 3 nhân 2 nhân 1 nhân 1, tức là bằng 6.

Nếu bạn có thể phát biểu một định nghĩa có tính đệ quy cho một hàm nào đó thì bạn cũng có thể viết một chương trình Python để tính nó. Bước đầu tiên là xác định các tham số. Trong trường hợp này rõ ràng factorial nhận vào một số nguyên:

def factorial(n):

Nếu tham số bằng 0, chúng ta chỉ cần trả lại giá trị 1:

def factorial(n):
    if n == 0:
        return 1

Nếu điều đó không xảy ra (đây chính là phần hay nhất), chúng ta thực hiện lời gọi đệ quy để tính giai thừa của n - 1 và sau đó nhân nó với n:

def factorial(n):
    if n == 0:
        return 1
    else:
        recurse = factorial(n-1)
        result = n * recurse
        return result

Luồng thực hiện của chương trình này cũng giống như của chương trình countdown trong Mục “đệ quy”. Nếu ta gọi factorial với giá trị 3:

Vì 3 khác 0 nên ta chọn nhánh thứ hai và tính giai thừa của n-1…

Vì 2 khác 0 nên ta chọn nhánh thứ hai và tính giai thừa của n-1…

Vì 1 khác 0 nên ta chọn nhánh thứ hai và tính giai thừa của n-1…

Vì 0 bằng 0 nên ta chọn nhánh thứ nhất và trả lại giá trị 1 và không gọi đệ quy thêm lần nào nữa.

Giá trị được trả về, 1, được nhân với n, vốn bằng 1, và kết quả được trả lại.

Giá trị được trả về (1) được nhân với n, vốn bằng 2, và kết quả được trả lại.

Giá trị được trả về (2) được nhân với n, vốn bằng 3, và kết quả, 6 trở thành giá trị trả về của hàm ứng với lúc bắt đầu gọi đệ quy.

Sau đây là nội dung của biểu đồ ngăn xếp khi một loạt các hàm được gọi:

Các giá trị trả lại như ở đây được chuyển về ngăn xếp. Ở mỗi khung, giá trị trả lại chính là giá trị của result, vốn là tích của n và recurse.

Ở khung cuối cùng, các biến địa phương recurse và result đều không tồn tại, vì nhánh tạo ra chúng không được thực hiện.

6.5 Niềm tin

Việc dõi theo luồng thực hiện của chương trình là một cách đọc mã lệnh, nhưng bạn sẽ nhanh chóng lạc vào mê cung. Một cách làm khác mà tôi gọi là “niềm tin” như sau. Khi bạn dò đến một lời gọi hàm, thay vì việc đi theo luồng thực hiện, hãy coi như là hàm đó hoạt động tốt và trả lại kết quả đúng.

Thật ra, bạn đã từng có “niềm tin” này khi dùng các hàm dựng sẵn. Mỗi khi gọi math.cos hay math.exp, bạn không kiểm tra nội dung bên trong các hàm này. Bạn chỉ việc giả sử rằng chúng chạy được vì những người lập trình ra các hàm đó đều giỏi.

Cũng như vậy khi bạn gọi các hàm riêng của mình. Chẳng hạn, trong Mục 6.4, chúng ta đã viết một hàm tên là is_divisible để xác định xem một số có chia hết cho một số khác không. Một khi chúng ta tự thuyết phục rằng hàm này đã viết đúng—bằng cách kiểm tra và thử mã lệnh—chúng ta có thể sử dụng hàm mà không cần phải xem lại phần thân hàm nữa.

Điều tương tự cũng đúng với các chương trình đệ quy. Khi bạn đến điểm gọi đệ quy, thay vì đi theo luồng thực hiện, bạn cần phải coi rằng lời gọi đệ quy hoạt động tốt (tức là cho kết quả đúng) và sau đó tự hỏi mình “Giả dụ như ta đã tìm được giai thừa của n - 1, liệu ta có tính được giai thừa của n không?” Trong trường hợp này, rõ ràng là ta sẽ tính được, bằng cách nhân với n.

Dĩ nhiên là sẽ có chút kì lạ trong việc ta giả sử rằng hàm hoạt động tốt khi chưa viết xong nó, nhưng chính vì vậy mà ta gọi đó là niềm tin!

6.6 Thêm một ví dụ

Sau factorial, một ví dụ thông dụng khác về hàm toán học được định nghĩa theo cách đệ quy là fibonacci. Hàm này được xác định như sau: ²

fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2); 

Theo ngôn ngữ của Python, nó có dạng:

def fibonacci (n):
    if n == 0:
        return 0
    elif  n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

Nếu bạn thử gắng theo luồng thực hiện ở đây, ngay cả với các giá trị nhỏ của n, bạn sẽ đau đầu ngay. Nhưng bằng niềm tin, nếu bạn coi rằng cả hai lời gọi đệ quy đều hoạt động tốt, thì rõ ràng bạn sẽ thu được kết quả đúng khi cộng chúng lại với nhau.

6.7 Kiểm tra kiểu

Điều gì sẽ xảy ra nếu ta gọi factorial với đối số bằng 1.5?

>>> factorial(1.5)
RuntimeError: Maximum recursion depth exceeded

Dường như đó là đệ quy vô hạn. Nhưng sao có thể xảy ra điều này? Có một trường hợp cơ bản—khi n == 0. Nhưng nếu n không phải là số nguyên, chúng ta có thể lỡ mất trường hợp cơ bản và đệ quy diễn ra mãi mãi.

Ở lời gọi đệ quy thứ nhất, giá trị của n bằng 0.5. Ở lần tiếp theo, n bằng  - 0.5. Từ đó, nó ngày càng nhỏ hơn (càng âm), nhưng sẽ không bao giờ bằng được 0.

Chúng ta có hai sự lựa chọn. Một là thử khái quát hoá hàm factorial để làm việc được với các số có phần thập phân, hoặc ta có thể để factorial kiểm tra kiểu đối số của nó. Lựa chọn thứ nhất gắn với việc gọi hàm gamma³ và nó phần nào đã vượt ra ngoài phạm vi quyên sách này. Vì vậy ta sẽ xét đến cách thứ hai.

Ta có thể dùng hàm dựng sẵn isinstance để thẩm định kiểu của đối số. Khi đã dùng nó rồi, có thể khẳng định rằng đối số là số dương:

def factorial (n):
    if not isinstance(n, int):
        print 'Factorial chỉ được định nghĩa cho số nguyên.'
        return None
    elif n < 0:
        print 'Factorial chỉ được định nghĩa cho số nguyên dương.'
        return None
    elif n == 0:
        return 1
    else:
        return n * factorial(n-1)

Trường hợp cơ bản thứ nhất xử lý các số không nguyên; trường hợp thứ hai bắt lỗi các số nguyên âm. Trong cả hai trường hợp, chương trinh đều in ra thông báo lỗi và trả về None để biểu thị rằng có điều gì sai đã xảy ra:

>>> factorial('fred')
Factorial chỉ được định nghĩa cho số nguyên.
None
>>> factorial(-2)
Factorial chỉ được định nghĩa cho số nguyên dương.
None

Nếu vượt qua được cả hai lần kiểm tra, thi n chắc chắn là một số nguyên dương, và ta có thể chứng minh rằng lời gọi đệ quy sẽ kết thúc.

Chương trình này minh hoạ cho một dạng lập trình đôi khi được gọi là chốt bảo vệ. Hai lệnh điều kiện đầu có vai trò bảo vệ đoạn mã lệnh tiếp theo khỏi những giá trị có thể gây ra lỗi. Những chốt bảo vệ này giúp ta chứng minh được tính đúng đắn của mã lệnh.

6.8 Gỡ lỗi

Việc chia nhỏ một chương trình lớn thành những hàm con tự nó đã tạo ra những điểm kiểm soát để gỡ lỗi. Nếu một hàm không hoạt động, có thể có ba khả năng cần xét đến:

• Các đối số mà hàm nhận vào có vấn đề; một điều kiện đầu bị vi phạm.
• Bản thân hàm có vấn đề; một trạng thái sau bị vi phạm.
• Giá trị trả lại hoặc cách dùng giá trị này có vấn đề.

Để loại trừ khả năng thứ nhất, bạn có thể thêm vào một câu lệnh print tại điểm đầu của hàm để hiển thị các giá trị của đối số (và có thể cả kiểu của chúng nữa). Hoặc bạn có thể viết các đoạn mã kiểm tra những điều kiện đầu này một cách tường minh.

Nếu các tham số có vẻ tốt, hãy thêm một lệnh print vào trước mỗi lệnh return để hiển thị các giá trị được trả lại. Nếu có thể, hãy kiểm tra các kết quả theo cách thủ công. Cân nhắc việc gọi hàm với các giá trị mà ta dễ dàng kiểm tra kết quả (như ở Mục “phát triển tăng dần”).

Nếu hàm số dường như hoạt động tốt, hãy xem lời gọi hàm để chắc rằng giá trị trả lại được dùng và dùng đúng.

Việc thêm các lệnh print vào đầu và cuối một hàm có thể giúp cho luông thực hiện được rõ ràng hơn. Chẳng hạn, sau đây là một dạng của hàm factorial với các lệnh print.

def factorial(n):
    space = ' ' * (4 * n)
    print space, 'giai thừa', n
    if n == 0:
        print space, 'trả lại 1'
        return 1
    else:
        recurse = factorial(n-1)
        result = n * recurse
        print space, 'trả lại', result
        return result

space là một chuỗi các kí tự trắng để điều khiển mức độ thụt đầu dòng của chữ cần in ra. Sau đây là kết quả của factorial(5) :

                     giai thừa 5
                 giai thừa 4
             giai thừa 3
         giai thừa 2
     giai thừa 1
 giai thừa 0
 trả lại 1
     trả lại 1
         trả lại 2
             trả lại 6
                 trả lại 24
                     trả lại 120

Kiểu in kết quả này có thể sẽ rất tốt nếu bạn bị lẫn khi tìm luồng thực hiện. Để dựng các “dàn giáo” một cách hiệu quả cũng cần chút thời gian, nhưng thêm dàn giáo có thể giúp giảm thiểu việc gỡ lỗi.

6.9 Thuật ngữ

biến tạm thời:

Biến dùng để lưu một giá trị trung gian trong phép tính phức tạp.

đoạn mã chết:

Phần chương trình không bao giờ được thực hiện, thường là do nó xuất hiện sau một câu lệnh return.

None:

Giá trị đặc biệt được trả về từ các hàm không chứa câu lệnh return hoặc một câu lệnh return mà không kèm theo đối số.

phát triển tăng dần:

Kế hoạch phát triển chương trình trong đó tránh gỡ lỗi bằng việc mỗi lúc chỉ thêm vào và kiểm thử một đoạn mã lệnh ngắn.

dàn giáo:

Mã lệnh được dùng trong giai đoạn phát triển chương trình nhưng bị bỏ đi ở phiên bản chương trình cuối.

chốt bảo vệ:

Dạng lập trình trong đó có dùng một câu lệnh điều kiện để kiểm tra và xử lý các trường hợp có thể gây ra lỗi.

6.10 Bài tập

Bài tập 4

Vẽ biểu đồ ngăn xếp cho chương trình dưới đây. Chương trình sẽ in ra cái gì?

def b(z):
    prod = a(z, z)
    print z, prod
    return prod

def a(x, y):
    x = x + 1
    return x * y

def c(x, y, z):
    sum = x + y + z
    pow = b(sum)**2
    return pow

x = 1
y = x + 1
print c(x, y+3, x+y)

Bài tập 5

Hàm Ackermann, A(m, n), được định nghĩa là⁴:

Viết một hàm có tên là ack để tính hàm Ackermann. Sau đó dùng hàm đã viết để tính ack(3, 4), kết quả đúng là 125. Điều gì sẽ xảy ra với các giá trị m và n lớn hơn?

Bài tập 6

Một từ đối xứng là từ đọc xuôi ngược đều như nhau, chẳng hạn “noon” và “redivider”. Theo cách đệ quy, một từ sẽ là đối xứng nếu các chữ cái đầu và cuối là như nhau và phần giữa cũng là một từ đối xứng.

Dưới đây là các hàm nhận vào một đối số chuỗi và trả lại các chữ cái đầu, cuối và giữa:

def first(word):
    return word[0]

def last(word):
    return word[-1]

def middle(word):
    return word[1:-1]

Chúng ta sẽ xét bản chất của chúng trong Chương “Chuỗi kí tự”.

1. Hãy chép lại các hàm trên vào trong file có tên là palindrome.py và sau đó thử chúng. Điều gì sẽ xảy ra khi bạn gọi middle với một chuỗi chỉ có 2 chữ cái? 1 chữ cái? và chuỗi trống không có chữ cái nào (được viết là '' )
2. Viết một hàm có tên là is_palindrome nhận vào một đối số chuỗi và trả lại True nếu đó là một từ đối xứng và False nếu không phải. Hãy nhớ rằng bạn có thể dùng hàm dựng sẵn len để biết độ dài của chuỗi.

Bài tập 7

Một số, a, là lũy thừa của b nếu nó chia hết cho b và a / b cũng là một lũy thừa của b. Hãy viết một hàm có tên là is_power nhận vào các đối số a và b rồi trả lại True nếu a là lũy thừa của b.

Bài tập 8

Ước số chung lớn nhất (GCD, greatest common divisor) của a và b là số lớn nhất mà cả a và b đều chia hết cho nó.⁵

Một cách tìm GCD của hai số là thuật toán Euclid, vốn dựa trên nhận xét rằng nếu như r là số dư của phép chia a cho b, thì gcd(a, b) = gcd(b, r). Với trường hợp cơ bản, ta có thể coi gcd(a, 0) = a.

Hãy viết một hàm có tên gcd nhận vào hai tham số a và b, sau đó trả lại ước số chung lớn nhất của chúng. Nếu bạn cần gợi ý, hãy xem http://vi.wikipedia.org/wiki/Thu%E1%BA%ADt_to%C3%A1n_Euclid.

---

1. Turing là một trong những nhà khoa học máy tính đầu tiên (có người cho rằng ông là một nhà toán học, song cũng có nhiều nhà khoa học máy tính thời sơ khai bấy giờ xuất thân từ toán học). ↩
2. Xem vi.wikipedia.org/wiki/Số_Fibonacci. ↩
3. Xem wikipedia.org/wiki/Gamma_function. ↩
4. Xem vi.wikipedia.org/wiki/Hàm_số_Ackermann. ↩
5. Bài tập này dựa theo một ví dụ từ cuốn sách Structure and Interpretation of Computer Programs của Abelson and Sussman. ↩