有没有更好的方法来一次退出所有递归函数，而不是一个一个地退出？

Question

有没有更好的方法可以在满足 if(a == b) 条件后立即退出所有递归迭代，而不必以当前形式包含第 7 行和第 8 行？没有像现在这样的第 7 和第 8 行，它似乎只退出最后一次迭代。

bool recursive(int a, int b) {
    if(a == b)
        return true;

    for(int i = 0; i < count; i++)
        if(locked[b][i] == true)
            if(recursive(a, i) == true)
                return true;

    return false;
}

这不是很重要，但我想尽可能多一些。有什么想法吗？

Answer 1

是的。您可以使用名为 longjmp 的有点晦涩的 C 功能。它允许通过多个函数调用跳回堆栈。有点类似于C++中的throw.

首先，return 环境是用 setjmp() 创建的。它 returns 0 如果 to 是对 setjmp() 的第一次调用。否则它 return 是一个由 longjmp() 设置的值，在递归调用中调用得更深。

#include <stdio.h>
#include <setjmp.h>

void slowrec(int n) {
    if (n == 0) {
        puts("done");
    } else {
        puts("go down");
        slowrec(n - 1);
        puts("go up");
    }
}

jmp_buf env;

void fastrec(int n) {
    if (n == 0) {
        puts("done");
        longjmp(env, 1);
    } else {
        puts("go down");
        fastrec(n - 1);
        puts("go up");
    }
}

int main() {
    puts("-- slow recursion --");
    slowrec(5);

    puts("-- longjmp recursion --");
    if (setjmp(env) == 0) {
        fastrec(5);
    }

    return 0;
}

产生：

-- slow recursion --
go down
go down
go down
go down
go down
done
go up
go up
go up
go up
go up
-- longjmp recursion --
go down
go down
go down
go down
go down
done

对于原始问题，代码可能如下所示：

jmp_buf env;

void recursive_internal(int a, int b) {
    if (a == b) longjmp(env, 1); // true

    for(int i = 0; i < count; i++)
        if(locked[b][i])
            recursive_internal(a, i);
}

bool recursive(int a, int b) {
    if (setjmp(env) == 0) {
        recursive_internal(a, b);
        // left without triggering long jump
        return false;
    }
    // returned with longjmp
    return true;
}

请注意，recursive_internal 中没有 return 值，因为满足了 a==b 条件并且 longjmp 被采用，因为这是唯一的方法 true 可以 returned。否则，条件永远不会满足，算法通过 return false.

退出

Answer 2

我大概会这样写：

bool recursive(int a, int b) {
    bool result = (a == b);

    for (int i = 0; i < count && !result; i++) {
        result = (locked[b][i] && recursive(a, i));
    }

    return result;
}

引入一个变量来保存函数的工作结果允许测试结果作为执行循环迭代的条件的一部分。这样您就可以在结果从 false 翻转到 true 时立即终止循环，但您不需要任何代码来区分循环终止的两个可能原因。

有没有更好的方法来一次退出所有递归函数，而不是一个一个地退出？

Is there a better way to exit all recursive functions at once, rather than one by one?

c

recursion

boolean