Viết lại một hàm đệ quy mà không sử dụng đệ quy

Question

Tôi đang viết lại một số mã hiện có trong một thiết lập nơi các cuộc gọi đệ quy không dễ triển khai cũng như mong muốn. (Và trong Fortran 77, nếu bạn phải biết.) Tôi đã nghĩ về việc tạo một ngăn xếp từ đầu để theo dõi các cuộc gọi cần thiết, nhưng điều này có vẻ kludgy, và tôi không muốn cấp phát bộ nhớ cho một mảng trong trường hợp đệ quy không sâu. (Tôi không tự tin rằng Fortran 77 cũng hỗ trợ kích thước mảng động.)

Bất kỳ đề xuất nào khác về cách thực hiện hàm đệ qui rõ ràng và viết lại nó không đệ quy mà không lãng phí không gian trên ngăn xếp?

Rất cám ơn, Cũ MCST

Answer 1

Nếu mã của bạn sử dụng đệ quy đuôi (có nghĩa là, hàm trả về kết quả của mỗi cuộc gọi đệ quy trực tiếp mà không cần bất kỳ chế biến khác) sau đó nó có thể viết lại chức năng phải nhất thiết mà không cần một chồng:

function dosomething(a,b,c,d) 
{ 
    // manipulate a,b,c,d 
    if (condition) 
    return dosomething(a,b,c,d) 
    else 
    return something; 
} 

Into:

function dosomething(a,b,c,d) 
{ 
    while (true) 
    { 
    // manipulate a,b,c,d 
    if (condition) continue; 
    else return something; 
    } 
} 

Không cần đệ quy đuôi, sử dụng ngăn xếp (hoặc lưu trữ trung gian tương tự) là giải pháp duy nhất.

Answer 2

Hầu hết các chức năng đệ quy có thể dễ dàng viết lại như vòng, như để lãng phí thời gian - điều đó phụ thuộc vào chức năng, vì nhiều (nhưng không phải tất cả) đệ quy thuật toán thực sự phụ thuộc vào loại đó lưu trữ (mặc dù, phiên bản vòng lặp thường là hiệu quả hơn trong những trường hợp này quá).

Answer 3

Chức năng đệ quy cổ điển có thể được viết như một vòng lặp là hàm Fibonacci:

function fib(n) 
{ 
    // valid for n >= 0 
    if (n < 2) 
     return n; 
    else 
     return fib(n-1) + fib(n-2); 
} 

Nhưng mà không memoization này mất O (exp^N) hoạt động với O (N) ngăn xếp không gian.

Nó có thể được viết lại:

function fib(n) 
{ 
    if (n < 2) 
     return n; 
    var a = 0, b = 1; 
    while (n > 1) 
    { 
     var tmp = a; 
     a = b; 
     b = b + tmp; 
     n = n - 1; 
    } 
    return b; 
} 

Nhưng điều này liên quan đến kiến ​​thức về cách các chức năng hoạt động, không chắc chắn nếu nó có thể được khái quát hóa một quá trình tự động.