0

I'm a programming rookie who has not yet started. I just learned recursion and there are some problems with the use of recursion. There is a homework is judge prime numbers ：using int prime（int x）; and return boolean value.

Initially I found that because the variable is initialized and assigned inside the function，the program can't achieve self-increment. Because every time it enters a new level of recursion, the variable will be reassigned. Even if you write a variable auto-increment statement, it will only auto-increase the variables stored in the current recursive stack. Once the variable enters a new recursive level, the variable is only initialized according to the definition and cannot be continuously auto-incremented.

The solution to the failure is as follows：

#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);
}

When asking questions, I found a successful solution:

#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);

}

But I can't understand why using static to modify the variable can make the variable correctly increment when entering a new layer of recursion instead of executing the previous int low=2;

Ask the master to solve the confusion for me, what happened to the two in the memory space?

In addition, there seems to be another solution, which seems to be to set a flag variable, but I did not understand it. Can someone provide other solutions?

marc_s
  • 732,580
  • 175
  • 1,330
  • 1,459
CHAOSYD
  • 15
  • 1
  • 5
  • 2
    Does this answer your question? [What does "static" mean in C?](https://stackoverflow.com/questions/572547/what-does-static-mean-in-c) – Retired Ninja Aug 02 '21 at 23:11
  • Note that with `static int low = 2;`, you can only reliably call the function once. After that, the value of `low` will avoid testing divisors such as 2, 3 and 5. So, using that `static` is a very poor way to do the job. Also, AFAICS, your function never recurses. Each branch of the `if / else if / else` contains `return` so `prime` is never called for the tail recursion. You should have `return prime(x);` to return a value — but since the call isn't made, it doesn't matter much at the moment. – Jonathan Leffler Aug 02 '21 at 23:32
  • Since you have just learned recursion, now is the correct time to learn that recursion should be avoided whenever possible. Of course there are situation where it's fine to use, but more often than not it will cause headaches. – Cheatah Aug 03 '21 at 07:59
  • Sorry，this is my mistake.I corrected my code. – CHAOSYD Aug 03 '21 at 08:15
  • Testing for prime numbers is not a very good use of recursion in the first place. Here are some *good*, appropriate problems for experimenting with and learning about recursion: • Do an inorder traversal of a binary tree; • print out a singly-linked list in reverse order; •write `itoa`; • compute the greatest common denominator. – Steve Summit Aug 18 '21 at 16:31

1 Answers1

1

In a nutshell, ordinary variables (int low;) get created for each function call independently, while static (static int low = 2;) are created once and shared between all the functions.

However, static is not the best approach to use in such cases, because different function calls may need to have different values of high/low.

Instead, you may add explicit parameters to the function, something like this (the algorithm is wrong, but it's the general principle):

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);
  }
}
IMil
  • 1,391
  • 13
  • 17