Đệ quy
Đệ quy rất hữu ích trong việc phân chia và giải quyết vấn đề. Bản thân mỗi lời gọi đệ quy sẽ tách ra khỏi các lệnh gọi đệ quy khác. Trọng tâm của một hàm đệ quy là hai loại trường hợp:trường hợp cơ sở, cho biết khi nào thì kết thúc đệ quy và trường hợp đệ quy gọi hàm của chúng. Thuật toán giai thừa đệ quy có hai trường hợp:trường hợp cơ sở khi n =0 và trường hợp đệ quy khi n> 0.
Bẻ khóa ngược
Backtracking là một thuật toán chung để tìm kiếm giải pháp cho một số vấn đề tính toán, từng bước xây dựng các lựa chọn cho các giải pháp và từ chối việc tiếp tục xử lý các dấu vết dẫn đến các giải pháp bất khả thi. Bẻ khóa ngược cho phép chúng tôi hoàn tác các lựa chọn trước đó nếu chúng là sai lầm.
Cách triển khai giai thừa điển hình như sau -
Ví dụ
def factorial(n): #test for a base case if n==0: return 1 # make a calculation and a recursive call f= n*factorial(n-1) print(f) return(f) factorial(4)
Đoạn mã này in ra các chữ số 1, 2, 4, 24. Để tính giai thừa 4 cần bốn lần gọi đệ quy cộng với lần gọi mẹ ban đầu.