Giai thừa sử dụng ngăn xếp trong python

Hàm giai thừa Python

import math

def factorial(x):
    return math.factorial(x)

print(factorial(5))

0 được xác định cho một số nguyên

import math

def factorial(x):
    return math.factorial(x)

print(factorial(5))

1. Cái này tính tích của tất cả các số hạng từ

import math

def factorial(x):
    return math.factorial(x)

print(factorial(5))

1 đến

import math

def factorial(x):
    return math.factorial(x)

print(factorial(5))

3.

import math

def factorial(x):
    return math.factorial(x)

print(factorial(5))

4 được coi là

import math

def factorial(x):
    return math.factorial(x)

print(factorial(5))

3

Vì vậy, chức năng là

factorial(n) = n * (n-1) * (n-2) * .. * 1, n >= 1
factorial(n) = 1, n = 0

Do đó, giai thừa(4) = 4 * 3 * 2 * 1 = 24

Hãy phân tích cách chúng ta có thể viết hàm toán học này bằng Python

Sử dụng toán học. yếu tố()

Chúng ta có thể trực tiếp sử dụng chức năng giai thừa của mô-đun

import math

def factorial(x):
    return math.factorial(x)

print(factorial(5))

6 để thực hiện công việc sử dụng

import math

def factorial(x):
    return math.factorial(x)

print(factorial(5))

đầu ra

120

Chúng tôi cũng sẽ xem xét việc tìm chức năng này bằng các phương pháp khác. bây giờ chúng ta hãy sử dụng một quy trình lặp đi lặp lại

Sử dụng thủ tục lặp

Chúng ta có thể lặp trực tiếp tất cả các số từ 1 đến n và nhân trực tiếp tích

import math

def factorial(x):
    return math.factorial(x)

print(factorial(5))

0

đầu ra

import math

def factorial(x):
    return math.factorial(x)

print(factorial(5))

1

Bây giờ chúng ta hãy xem xét sử dụng một phương thức đệ quy cho hàm giai thừa Python

---

Sử dụng thủ tục đệ quy

Chúng ta có thể sử dụng đệ quy, để tính hàm này. Về cơ bản, chúng tôi rút gọn chức năng này thành một bài toán con nhỏ hơn. Sau khi chúng tôi tính toán các bài toán con, chúng tôi có thể kết hợp các kết quả để đưa ra câu trả lời cuối cùng

Vì cấu trúc bài toán là tích giảm dần nên chúng ta có thể lập mô hình đệ quy theo cách sau

import math

def factorial(x):
    return math.factorial(x)

print(factorial(5))

2

Dòng cuối cùng là trường hợp cơ sở. Đây là điểm dừng đệ quy và chúng ta có thể nhận được sản phẩm cuối cùng khi đệ quy kết thúc

Chúng tôi sẽ viết hàm Python tương ứng cho việc này

import math

def factorial(x):
    return math.factorial(x)

print(factorial(5))

3

đầu ra

import math

def factorial(x):
    return math.factorial(x)

print(factorial(5))

1

Điều đó có vẻ đúng. Hãy phân tích những gì thực sự xảy ra trong các cuộc gọi đệ quy

Bất cứ khi nào các cuộc gọi đệ quy được sử dụng, sẽ có một ngăn xếp cuộc gọi, liên tục lưu trữ trạng thái của chương trình, cho đến khi đạt đến trường hợp cơ sở. Các phần tử ngăn xếp cuối cùng được bật ra từng cái một sau khi một giá trị được trả về bởi khối tương ứng, khi đệ quy kết thúc từ

import math

def factorial(x):
    return math.factorial(x)

print(factorial(5))

7

Toàn bộ quá trình được giải thích trong hình bên dưới, để tìm

import math

def factorial(x):
    return math.factorial(x)

print(factorial(5))

8. Phần đầu tiên của toàn bộ quy trình là xây dựng ngăn xếp trong đó mỗi lệnh gọi đệ quy đó được xếp chồng lên nhau cho đến khi hàm trả về 1

Khi hàm không thể gọi đệ quy nữa, hàm sẽ bắt đầu tính giai thừa như minh họa bên dưới

ngăn xếp đệ quy

Khi các chức năng trở lại, các phần tử ngăn xếp lần lượt xuất hiện, từ trên xuống. Cuối cùng, khi nó đến ngăn xếp

import math

def factorial(x):
    return math.factorial(x)

print(factorial(5))

9, chức năng cuối cùng đã hoàn thành và chúng ta có giá trị của mình, giá trị này là

120

0

---

Các cuộc gọi đệ quy đuôi

Mặc dù chương trình của chúng tôi hoạt động tốt, nhưng vấn đề với chức năng đệ quy của chúng tôi là kích thước ngăn xếp tăng lên nhiều như kích thước đầu vào

Vì vậy, nếu

import math

def factorial(x):
    return math.factorial(x)

print(factorial(5))

1 là một số rất lớn, thì ngăn xếp đệ quy của chúng ta có thể rất lớn, điều đó có thể khiến ngăn xếp bị tràn. Để tránh điều này, chúng ta sẽ sử dụng một cách tiếp cận khác để mã hóa một hàm đệ quy, được gọi là thủ tục đệ quy đuôi

Lời gọi thủ tục đuôi nhằm thực hiện lời gọi đệ quy sau khi tính kết quả trung gian. Vì vậy, thay vì tăng kích thước ngăn xếp, chương trình có thể sử dụng cùng một ngăn xếp cho toàn bộ quá trình. Nó chỉ cần được cập nhật

Điều này có nghĩa là lời gọi đệ quy của chúng ta phải luôn ở cuối. Đây là lý do tại sao nó là một "cuộc gọi đuôi"

import math

def factorial(x):
    return math.factorial(x)

print(factorial(5))

0

Vì chúng tôi không thể trực tiếp thực hiện cuộc gọi đệ quy ở cuối, nên chúng tôi thực hiện điều đó với một hàm trợ giúp khác, tính toán thực tế đó cho chúng tôi. Hàm trợ giúp này lưu trữ một

120

2, lưu trữ giá trị hiện tại của hàm

Mẹo nhỏ là chuyển bộ tích lũy làm tham số cho hàm đệ quy và cập nhật nó, sử dụng

120

3. Bằng cách này, chúng tôi sẽ lưu trữ trạng thái trung gian trong một biến và do đó, chỉ trong một khung ngăn xếp

đầu ra

import math

def factorial(x):
    return math.factorial(x)

print(factorial(5))

1

Bạn nhận được đầu ra giống như trước đây. Bây giờ, bạn cũng đã đảm bảo rằng chương trình chỉ sử dụng một khung ngăn xếp, do đó, về cơ bản nó tương đương với quy trình lặp. Điều đó không tốt sao?

---

Phần kết luận

Trong bài viết này, chúng ta đã tìm hiểu về cách chúng ta có thể triển khai hàm giai thừa theo nhiều cách khác nhau, bằng cách sử dụng mô-đun toán học, cũng như thông qua cả phép lặp và phép đệ quy

Cách tính giai thừa bằng cách sử dụng ngăn xếp?

Công thức cho giai thừa trong Python là gì?

Bạn có thể sử dụng giai thừa trong Python không?

Làm cách nào để tìm giai thừa của một số trong Python bằng vòng lặp for?