0

I want to calculate prime numbers with a recursive function called primzahlenRekursiv, but I get a StackOverflowException in the function istPrimzahl, where I check if the current number is prime.

 static void Main(string[] args)
    {
        primzahlenRekursiv(2);
    }

    static void primzahlenRekursiv(int primzahl) 
    {
        if (istPrimzahl(primzahl, 2)) { Console.Writeline(primzahl); }
        primzahlenRekursiv(primzahl + 1);
    }

    static bool istPrimzahl(int primzahl, int zahl) 
    {
        if (primzahl % zahl != 0) { istPrimzahl(primzahl, zahl + 1); }
        if (primzahl == zahl) { return true; }
        return false;
    }
15ee8f99-57ff-4f92-890c-b56153
  • 36,786
  • 7
  • 62
  • 114
Lukas F.
  • 55
  • 8
  • 4
    First thing to note: any time you're calling `istPrimzahl` and not using the result, that's a bug... – Jon Skeet Dec 09 '16 at 13:52
  • 1
    You want to find all prime numbers in the universe this will not happen. Where is the end of your recursion ? – mybirthname Dec 09 '16 at 13:53
  • Usually, when a recursive function calls itself, it passes a new parameter value to the child call instead of its own exact parameter value. Otherwise, how will the child call do anything the parent call didn't? – 15ee8f99-57ff-4f92-890c-b56153 Dec 09 '16 at 13:54
  • i want to go as far as i can – Lukas F. Dec 09 '16 at 13:54
  • Maybe if you are using big numbers you need to avoid recursion or change your [stack size](http://stackoverflow.com/questions/4513438/c-sharp-recursion-depth-how-deep-can-you-go) – ganchito55 Dec 09 '16 at 13:54
  • 1
    What part of your code you think prevents it from running infinitely? – BartoszKP Dec 09 '16 at 13:54
  • Check the answer here: http://stackoverflow.com/questions/15976333/stack-overflow-caused-by-recursive-function and get rid of the recursive function call. The language is different but the principle is the same. – diidu Dec 09 '16 at 13:58

1 Answers1

1

You have nothing in your recursive code that will ultimately end the recursion:

static void primzahlenRekursiv(int primzahl) 
{
    if (istPrimzahl(primzahl, 2)) { Console.Writeline(primzahl); }
    primzahlenRekursiv(primzahl + 1);
}

primzahlenRekursiv always calls itself without any condition to stop it. Since any method call needs space on the stack, your algorithm will run until your stack runs out. Hence your exception.

In fact there is no need to run your algorthim recursively:

for (var kandidat = 2; ; kandidat++) {
    if (istPrimzahl(kandidat, 2)) { Console.Writeline(kandidat); }
}

This will run your code in an endless loop and not use up your stack that quickly. But be careful, eventually you will still run into a stack overflow exception if your candidate is getting high enough (you are still running recursion in istPrimzahl), just later. Therefore you better constrain your number set (in this example to 10000):

for (var kandidat = 2; kandidat < 10000; kandidat++) {
    if (istPrimzahl(kandidat, 2)) { Console.Writeline(kandidat); }
}

Also, in your code your recursion is not running correctly because of another error:

if (primzahl % zahl != 0) { istPrimzahl(primzahl, zahl + 1); }

...does not use the result of the recursive call. You are probably meaning to return the result of the recursive call at this spot.

Another solution would of course be a tail call, but C# doesn't support that (althogh IL would).

Sefe
  • 13,731
  • 5
  • 42
  • 55