C语言 如何增加递归?递归判断质数的一个例子

Question

我是一个还没有开始的编程新手。我刚学了递归，递归的使用有一些问题。有一个作业是判断质数:使用int prime（int x）;并返回布尔值。

最初我发现，因为变量是在函数内部初始化和赋值的，程序不能实现自增。因为每次它进入一个新的递归级别时，变量都会被重新赋值。即使您编写了变量自动递增语句，它也只会自动递增存储在当前递归堆栈中的变量。一旦变量进入一个新的递归层，该变量就只能根据定义初始化，不能继续自动递增。

故障的解决方法如下:

#include <math.h>
#define false 0
#define true  1
int prime(int x){
double high=sqrt(x);
int low=2;
if((x%low==0 && x!=2) || low>high){
return false;
}
else if(x<2){
return false;
}
else{
return true;
}
low++;
return prime(x);
}

在提出问题的时候，我找到了一个成功的解决方案:

#include <math.h>
#define false 0
#define true  1
int prime(int x){
double high=mysqrt(x);
static int low=2;
if((x%low==0 && x!=2)||low>high){
return false;
}
else if(x<2){
return false;
}
else{
return true;
}
low++;
return prime(x);
}

但是我不明白为什么使用静态来修改变量可以使变量在进入一个新的递归层时正确地增加，而不是执行以前的int low=2;

请大师为我解惑，两个内存空间怎么了?

此外，似乎还有另一种解决方案，似乎是设置一个标志变量，但我不明白。有人能提供其他解决方案吗?

Answer 1

简而言之，普通变量(int low;)为每个函数调用独立创建，而静态变量(static int low = 2;)创建一次并在所有函数之间共享。

然而，static不是在这种情况下使用的最佳方法，因为不同的函数调用可能需要具有不同的high/low值。

相反，您可以向函数添加显式参数，类似于这样(算法是错误的，但这是一般原则):

int prime(int x) { return prime_impl(x, 2, sqrt(x)); }
int prime_impl(int x, int low, double high) {
if(x<2) {
return false;
}
else if((x%low==0 && x!=2)||low>high) {
return true;
}
else {
return prime_impl(x, low+1, high);
}
}