Tính đa thức bằng đệ quy

Danh sách A=[a0,a1,...,an] lưu hệ số theo **số mũ tăng dần**. A[0] là hệ số tự do, A[1] đi với x, A[2] đi với $x^2$. Ví dụ A=[2,−3,4] biểu diễn $F(x)=2-3x+4x^2$. Tại x=2, giá trị là $2-3\times2+4\times2^2=12$. Không đọc A theo thứ tự hệ số của cách viết $4x^2-3x+2$ từ trái sang phải, vì quy ước danh sách đã gắn chỉ số với số mũ.

Tải mã luyện tập, mở terminal tại thư mục chứa tệp và chạy bằng Python3: ```text python3 g11-cs-luyen-tap-de-quy.py 13 ``` Cần nhận xâu nhị phân 1101, danh sách [1,1,0,1] và giá trị đổi lại 13. Tệp có hàm decimal(s,n) tính giá trị n kí tự đầu theo công thức đã học; bộ mẫu dùng nó trên xâu 0/1 hợp lệ vừa tạo. Dãy [4,1,4,2] phải giữ nguyên sau khi đếm; hai bản đếm đều cho 3. Đa thức hệ số [2,−3,4] tại x=2 phải cho 12. Chạy lại với 0 để kiểm xâu `'0'`, danh sách [0] và giá trị đổi lại 0. Mẫu nhận n từ 0 đến 4095 để giữ dữ liệu thử nhỏ; nhập số âm, chữ hoặc số ngoài mẫu phải báo lỗi. Phần sắp xếp chèn dùng lại hàm sap_xep_chen trong tệp thiết kế đệ quy đã có: thử A=[4,1,4,2], gọi với k=len(A)−1, cần nhận A=[1,2,4,4]. Thử thêm rỗng, một phần tử, đã xếp và thứ tự giảm. Đây là thao tác sửa A tại chỗ; đếm nghịch đảo của dữ liệu gốc trước khi sắp xếp nếu cần giữ kết quả đếm. Đệ quy giúp cách viết bám sát quy tắc dùng bài toán nhỏ hơn, như chuyển chồng đĩa hoặc tổng hợp phần đầu. Tuy nhiên, chương trình có chi phí gọi hàm và giới hạn độ sâu; những phần tính lặp lại cũng có thể làm tăng công việc. Cần xét thuật toán và dữ liệu cụ thể khi so sánh với vòng lặp, thay vì kết luận tốc độ chỉ từ độ ngắn của mã.