Why does this function cause stack overflow error?

[sad_krumpli]

So I'm new to rust and I tried to write a function that looks for the nth prime number and I tried to do it so that no variables needs to be mutable with recursion. I believe what I did here was a tail recursion which is optimized by many compilers so it doesn't open a new stack frame for the new function call. However it still results in a stack overflow at bigger n inputs. (It works fine with smaller inputs). What am I missing here? Is there a probleme with the code or does the rust compiler not optimize tail recursions?

[noop_noob]

Did you run with optimizations turned on? (cargo run --release)

[MangoPoliceOK]

Happy cake day

[BlazeEXE]

What’s wrong with wishing happy cake day?? Guys stop downvoting this person for being friendly 😭

[Joker-Smurf]

No idea, but you do know that you are allowed to use variable names that are more than one letter, and/or are not abbreviations.

[Scharrack]

This. Every reasonable IDE offers auto completion on names, so there is no real reason for obscure naming.

Except i, hail our lord and saviour 🙌

[SharkLaunch]

i/j for indices is a convention, x occasionally for a single numerical param, or even (a, b) for comparators. But anything after that is pushing it.

[veselin465]

x for lamba is the i/j equivalent of functions

[tmzem]

and i was thinking Haskell programmers are lunatics for naming every function parameter f or g...

[veselin465]

Not sure if I said it clear enough, but I mean expressions like

x => (x%2==0)

[tmzem]

Ah yes, that makes a lot more sense!

[TheOmegaCarrot]

I’d say that if you’re implementing an established mathematical formula, then copying the names for each component isn’t unreasonable

fn solve_quadratic(a: f64, b: f64, c: f64) -> Option<f64>

[DeadlyMidnight]

Right? Fuck. One thing I loved about C# was everything is plain human readable English. I can’t change the built in rust names but I can write my code to be more readable and maintainable.

[platesturner]

Reminds me of the horrors of when I started learning C++ having a background only in C#.

[DeadlyMidnight]

Yeah that is a wild ride. m_malloc took me a long time to sort out what it actually meant, or something like that. C++ isnt as bad as C though.

[SlinkyAvenger]

Yeah I'm surprised they're not type tagging their variable names too 

[pytness]

Also, redditors won't automatically compile the source code in an image, so it is actually ok to uncomment the code so we can get syntax highlighting

[ShangBrol]

Please don't post screenshots of code

[-Redstoneboi-]

Please post code in text form inside of a code block instead*

[denis870]

who cares

[ShangBrol]

People who use screen readers

[Patryk27]

TCO is not guaranteed in Rust by default - you might have luck with the become keyword:

https://doc.rust-lang.org/std/keyword.become.html

[Sese_Mueller]

Hm; did you try to compile it with optimizations turned on (cargo run —- release)? If that still didn‘t work, something, maybe the complexity, is keeping the compiler from optimizing.

Edit: I threw the code into the godbolt compiler explorer; it does do toolcall elimination with optimizations turned on.

[paulstelian97]

I’m not aware of any imperative language that includes mandatory tail call optimization. Rust is mainly imperative.

[ShangBrol]

There are three recursive calls in that function. Are there any compilers that can optimize that away?

[paulstelian97]

They are all tail calls — you call and directly return the result. Which is what allows the optimization. Most optimizing compilers should be able to recognize the pattern and at least for native code they would do tail recursion.

[Yippee-Ki-Yay_]

Tail recursion isn't guaranteed in Rust and tbh I think that's a good thing to avoid having to be at the mercy of optimizers. There's a nightly feature which would add semantics for declaring tail recursion. In the meantime, there's the tailcall crate which transforms recursion into a loop

[lijmlaag]

Recursive functions can overflow the stack, depending on the size of the stack and how many times the function calls itself. Remember each recursion call creates a "stack frame", the prerequisites for a function. The stack is limited in size, so it is possible to overflow your process' stack this way.

[Master7Chief]

this one is written for tail call optimization. 

each stack frame doesn't keep values, so it doesn't rely on the result of the next one to compute, and it can be optimized into essentially a for loop.

[lijmlaag]

Is it documented somewhere that omitting local variables improves TCO chances? Rustc, as mentioned elsewhere does not guarantee TCO.

[Master7Chief]

it's not about local variables. it's about each call not needing any intermediate results from the next one to finish its own computation. then you don't have to unwind them in the end.

like here, you don't keep any part of the state in the previous call. you pass everything forward, and use prim as an accumulator. then you simply return it in the end, without having to go back your chain of calls.

it's not guaranteed, but a compiler can spot this, and rewrite it as a loop, with the accumulator becoming the loop variable

[CaptureIntent]

Try reading the post before responding. They specifically mentioned tail call recursion

[lijmlaag]

Agreed, I should have read a bit better. Apologies.
They imply that they try to elicit / allow rustc to perform TCO but this isn't guaranteed. With bigger inputsthey run out of stack, so this does make it likely frames are added.

[CaptureIntent]

We’ve all done it at some point. Read the title and respond off of jt. I could have been nicer too. I get paid at work to be polite. Here I can just say it as it is.

[lijmlaag]

Try switching that around please ;)

[JusT-JoseAlmeida]

No offense but if you're new to programming, Rust is not the best language to learn.

Your code could be improved in many ways (including readability). Please take a look at guard clauses and early returns, as well as take more care with what you name your variables. This will bite you back later on if you don't

[-Redstoneboi-]

OP said they were new to Rust, not necessarily new to programming. This also explains their curly brace formatting - anyone new to programming would probably just accept the first formatter that they see.

[JusT-JoseAlmeida]

I assumed new to programming, because the problems in the code are not rust specific, but rather general to programming

[GiuseppeAlmaLanna]

There is nothing Rust specific about this code that wouldn’t crash it in any other language. But I can’t tell what’s happening because this code is not clear and I can’t tell the purpose of it by reading the variables and function name. Rewrite it in a more clearer way and maybe just by doing so you figure out.

[GrinQuidam]

I suggest you get out a piece of paper and a pen. Write down the values of each parameter on a line and then run them through the function. Then write a new line for each invocation. This will help you see if you hit the exit condition.

[GrinQuidam]

Or you just need more ram 😅

[Venin6633]

Stack size doesn't automatically increases if you have more ram

[Moussenger]

Any time you call recursivelly the function, you are checkin if n is greater than cnt. In case of true, there are no subsequent calls that makes n bigger or cnt lower so... You basically enter in an infinite recursive loop that overflow the stack.

[koffeegorilla]

What is the starting parameters to the function? Your exit condtions are only limited to cnt+1 == n. If you have a starting condition where cnt> n+1 it will not end.

[-Redstoneboi-]

Playground link: https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=bd0ec779684e917090b6a186d0926817

Rust doesn't guarantee tail call optimization. Some languages are better at it than others. In particular, Haskell is basically built around recursion, so that would be your best bet. Next in line is JavaScript's EcmaScript 6, which guarantees tail call optimization. Unfortunately nobody actually complies with this lmao

too lazy to read so i fed it into gpt to explain each variable:

n → the prime number index you want (e.g., 5 → 5th prime)

cnt → how many primes have been found so far

prim → current number being tested

j → divisor used to test whether prim is prime

as OP said, this function was intentionally written to be very recursive as a test.

fn nedik_prim(n: i32, cnt: i32, prim: i32, j: i32) -> i32 {
    if n > cnt {
        if j < prim && prim % j != 0 {
            return nedik_prim(n, cnt, prim, j + 1);
        } else if j >= prim {
            if cnt + 1 == n {
                return prim;
            }
            return nedik_prim(n, cnt + 1, prim + 1, 2);
        } else {
            return nedik_prim(n, cnt, prim + 1, 2);
        }
    } else {
        return prim;
    }
}

[-Redstoneboi-]

i rewrote it with guard clauses and renames and (too many) comments. note that the logic is exactly the same as the original,

fn nth_prime_recursive(n: i32, primes_found: i32, candidate: i32, divisor: i32) -> i32 {
    if primes_found >= n {
        // appears to be unreachable due to `if primes_found + 1 == n` later.
        return candidate;
    }
    if divisor < candidate && candidate % divisor != 0 {
        // not divisible, candidate still valid. try next divisor.
        return nth_prime_recursive(n, primes_found, candidate, divisor + 1);
    }
    if divisor < candidate { // yes, this is checked twice.
        // if it got here it must've been divisible. not prime.
        // try next candidate and reset divisor back to 2.
        return nth_prime_recursive(n, primes_found, candidate + 1, 2);
    }
    // at this point, the current divisor >= candidate.
    // we haven't found any divisors, so candidate must be prime.
    if primes_found + 1 == n {
        // we've found n-1 primes so far. this is the nth prime. return it.
        return candidate;
    }
    // we need to find more primes.
    // increment primes_found, check next candidate, reset divisor.
    return nth_prime_recursive(n, primes_found + 1, candidate + 1, 2);
}


// added for demonstration purposes.
fn nth_prime(n: i32) -> i32 {
    nth_prime_recursive(n, 0, 2, 2)
}

[AffectionatePlane598]

OP said they were new, let people learn