c++ - 如何在特定时间后终止递归函数？

Question

我在 C++ 中有一个递归函数，我需要立即终止该函数，包括在特定时间后递归进行的所有调用，比如 60 秒。我尝试了以下但不起作用。takeTooLong 是一个全局变量，但如果它的值在一次调用中更改为 1，其他调用会一直将其视为 0。操作系统是Ubuntu 12.10。

main() 是这样的：

int main()
{
    takesTooLong = 0;
    startTime = clock();
    RecursiveFunction();
    endTime = clock();
    printf("Elapsed time: %f", CalculateElapsedTime(startTime, endTime));
    return 0;
}

我的递归函数：

void RecursiveFunction(Some Parameters)
{
    if (takesTooLong == 1)
        return;

    endTime = clock();
    differenceTime = CalculateElapsedTime(startTime, endTime);
    if (differenceTime > MAX_SECONDS)
    {
        takesTooLong = 1;
    }

    if (takesTooLong == 0)
    {
        for (i = 0; i < n && takesTooLong == 0; i++)
        {
            RecursiveFunction(Some Updated Parameters);
        }
    }   
}

Answer 1

退出未知数量的递归的最简单方法是抛出异常。由于您最多每 60 秒执行一次，这还不错。只需将其设置为 aclass TimeLimitExceeded : public std::runtime_error并在顶级包装器中捕获它†。

† 大多数递归函数不应直接调用，而应通过非递归包装器调用。递归函数的签名通常对调用者不方便，因为它包含与调用者无关的实现细节。

Answer 2

伪代码：

typedef ??? Time;//time type
Time getCurrentTime(); //returns time. Or ticks. Anything you could use to measure time.

void recursiveFunction(Time startTime){       
    ...//do something here
    Time currentTime = getCurrentTime();                
    if ((currentTime - startTime) > limit)
        return;
    recursiveFunction(startTime);
}

void recursiveFunction(){
     Time startTime = getCurrentTime();
     recursiveFunction(startTime);
}  

Answer 3

是的，您仍然需要展开堆栈，但替代方案都很丑陋，最好的可能是 longjmp。如果您需要比秒更高的分辨率，或者您想测量进程/内核时间而不是挂钟时间，请使用timer_create或setitimer.

void alarmHandler (int sig)
{
    timedOut = 1;
}


    signal(SIGALRM, alarmHandler);

    alarm(60);
    RecursiveFunction();
    alarm(0);

    if (timedOut)
    {
        //report something
        timedOut = 0;
    }


void RecursiveFunction(Some Parameters)
{
    if (timedOut)
        return;

    //........
}