Mảng là một dữ liệu có kích thước cố định, đồng nhất, và cơ cấu sử dụng rộng rãi.
Đồng nhất, chúng có nghĩa là nó bao gồm các thành phần đó là tất cả cùng loại, loại yếu tố gọi là hay kiểu cơ sở.
Cố định kích thước, chúng có nghĩa là số lượng các thành phần là không đổi, và vì vậy không thay đổi trong suốt thời gian tồn tại của cấu trúc dữ liệu đó.
LB=Lower Bound U=Upper Bound
Địa chỉ của các phần tử của hàng thứ i và cột thứ j:
addr(a[i, j]) = ((i−LB1)*(UB2−LB2+1)*size)+((j−LB2)*size)
Hàm đệ quy là một hàm gọi chính nó. Nó có 2 pha cơ bản là Winding và Unwinding
-Winding: hàm đệ quy gọi lại sự tồn tại của hàm đệ quy bằng cách tạo 1 vài điều kiện để gọi lại hàm đệ quy. Winding chấm dứt khi 1 trong những lần gọi hàm dẫn đến điều kiện chấm dứt. Điều kiện xác định chấm dứt pha mà tại đó một hàm đệ quy phải trả lại thay vì làm một cuộc gọi đệ quy. Mỗi chức năng đệ quy phải có ít nhất một điều kiện chấm dứt, nếu không, pha Winding không bao giờ chấm dứt.
-Unwinding: bắt đầu khi pha Winding kết thúc. Điều kiện trước được thực hiện theo chiều ngược lại. Pha sẽ tiếp tục cho đến khi chương trình gốc gọi trở về.
Example 1: Factorial n!.
F(n) = n* F(n-1)
If( n > 1) F(n) = 1
If( n = 1 or n = 0) Compute F(4) = ?
Winding Phase
F(4) = 4 * F(3)
F(3) = 3 * F(2)
F(2) = 2 * F(1)
F(1) = 1
UnWinding Phase
F(4) = 4 * 6 = 24
F(3) = 3 * 2 = 6
F(2) = 2 * 1 = 2
F(1) = 1
Hàm đệ quy được cho là đệ quy đuôi nếu tất cả các cuộc gọi đệ quy trong nó là đệ quy đuôi.
Một cuộc gọi đệ quy là đệ quy đuôi khi nó là lệnh cuối cùng sẽ được thực hiện trong cơ thể của một hàm và giá trị trả về của nó không phải là một phần của biểu thức.
Hàm đệ quy đuôi có đặc tính là không có gì làm trong pha Unwinding.(đặc tính quan trọng)
Example 2: Compute n!
F(n, a) = F(n-1, n*a)
If (n>1) F(n,a) = a
if (n = 1 or n = 0) Compute F(4,1) = ?
Winding Phase
F(4,1) = F(3,4)
F(3,4) = F(2,12)
F(2,12) = F(1,24)
F(1,24) = 24
UnWinding Phase
(Nothing to do)
Quay lui là một cách có hệ thống để đi qua tất cả các cấu hình có thể của một không gian tìm kiếm.
Đệ quy có thể được sử dụng để thực hiện quay lui dễ dàng.
