Nó có thể hầu như không thể thực hiện được.
Sử dụng thư viện coroutine. Với điều đó, bạn phân bổ stack của riêng bạn ra khỏi đống. Tái cơ cấu mã của bạn để theo dõi độ sâu của nó trong callstack của nó, và khi nó được sâu nguy hiểm, tạo ra một cothread mới và chuyển sang đó thay thế. Khi bạn hết bộ nhớ heap, đóng băng cothreads cũ và giải phóng bộ nhớ của họ. Tất nhiên, bạn tốt hơn hãy chắc chắn để giải phóng chúng đến cùng một địa chỉ - vì vậy tôi đề nghị bạn phân bổ ngăn xếp của mình mình ra khỏi đấu trường của riêng bạn mà bạn có thể kiểm soát. Trong thực tế nó có thể dễ dàng hơn để chỉ tái sử dụng cùng một phần của bộ nhớ cho ngăn xếp cothread và trao đổi chúng trong và ngoài cùng một lúc.
Thật dễ dàng để viết lại thuật toán của bạn là không đệ quy.
Đây có thể là một ví dụ về nó làm việc, hoặc nó chỉ có thể in câu trả lời đúng về tai nạn:
#include <stdio.h>
#include "libco.h"
//byuu's libco has been modified to use a provided stack; it's a simple mod, but needs to be done per platform
//x86.c:
////if(handle = (cothread_t)malloc(size)) {
//handle = (cothread_t)stack;
//here we're going to have a stack on disk and have one recursion's stack in RAM at a time
//I think it may be impossible to do this without a main thread controlling the coroutines, but I'm not sure.
#define STACKSIZE (32*1024)
char stack[STACKSIZE];
FILE* fpInfiniteStack;
cothread_t co_mothership;
#define RECURSING 0
#define EXITING 1
int disposition;
volatile int recurse_level;
int call_in_cothread(int (*entrypoint)(int), int arg);
int fibo_b(int n);
int fibo(int n)
{
if(n==0)
return 0;
else if(n==1)
return 1;
else {
int a = call_in_cothread(fibo,n-1);
int b = call_in_cothread(fibo_b,n-2);
return a+b;
}
}
int fibo_b(int n) { printf("fibo_b\n"); return fibo(n); } //just to make sure we can call more than one function
long filesize;
void freeze()
{
fwrite(stack,1,STACKSIZE,fpInfiniteStack);
fflush(fpInfiniteStack);
filesize += STACKSIZE;
}
void unfreeze()
{
fseek(fpInfiniteStack,filesize-STACKSIZE,SEEK_SET);
int read = fread(stack,1,STACKSIZE,fpInfiniteStack);
filesize -= STACKSIZE;
fseek(fpInfiniteStack,filesize,SEEK_SET);
}
struct
{
int (*proc)(int);
int arg;
} thunk, todo;
void cothunk()
{
thunk.arg = thunk.proc(thunk.arg);
disposition = EXITING;
co_switch(co_mothership);
}
int call_in_cothread(int (*proc)(int), int arg)
{
if(co_active() != co_mothership)
{
todo.proc = proc;
todo.arg = arg;
disposition = RECURSING;
co_switch(co_mothership);
//we land here after unfreezing. the work we wanted to do has already been done.
return thunk.arg;
}
NEXT_RECURSE:
thunk.proc = proc;
thunk.arg = arg;
cothread_t co = co_create(stack,STACKSIZE,cothunk);
recurse_level++;
NEXT_EXIT:
co_switch(co);
if(disposition == RECURSING)
{
freeze();
proc = todo.proc;
arg = todo.arg;
goto NEXT_RECURSE;
}
else
{
recurse_level--;
unfreeze();
if(recurse_level==0)
return thunk.arg; //return from initial level of recurstion
goto NEXT_EXIT;
}
return -666; //this should not be possible
}
int main(int argc, char**argv)
{
fpInfiniteStack = fopen("infinite.stack","w+b");
co_mothership = co_active();
printf("result: %d\n",call_in_cothread(fibo,10));
}
Bây giờ bạn chỉ cần để phát hiện bao nhiêu bộ nhớ trong hệ thống, bao nhiêu nó có sẵn , callstack lớn bao nhiêu, và khi callstack đã cạn kiệt, vì vậy bạn biết khi triển khai stack vô hạn. Đó không phải là công cụ dễ dàng cho một hệ thống, hãy để một mình làm điều đó một cách hợp lý. Nó có thể là tốt hơn để tìm hiểu làm thế nào ngăn xếp thực sự có nghĩa là để được sử dụng thay vì chiến đấu nó.
Không, không thể. Viết lại mà không đệ quy. – molbdnilo
Biến đệ quy thành lặp lại, giải quyết được vấn đề. –
Và không, bạn không thể mở rộng ngăn xếp cuộc gọi thành "đám mây". – molbdnilo