4 ms·
A true production quality implementation should always use recursion. func isOdd(n int) bool { switch { case n == 0: return false case n >
by flakes 3y ago
A true production quality implementation should always use recursion.
func isOdd(n int) bool {
switch {
case n == 0:
return false
case n > 0:
return !isOdd(n-1)
default:
return !isOdd(n+1)
}
}
- make3 3y agothis is truely evil :)
- grishka 3y agoThis will cause a stack overflow. You can convert that into a loop and make your own stack on the heap if you need very deep recursion.
- oldsecondhand 3y agoIn a language with tail-call optimization, it won't.
- dmurray 3y agoIt will. The negations are only being applied on the way back up the call stack. The mutual recursion version in a sibling post can be made to work though.
- ufo 3y agoSurprisingly, some compilers can automatically turn that to a loop too! Try it on clang and gcc :)
- grishka 3y agoGCC does eliminate one of the recursive calls but retains the other: https://godbolt.org/z/dof4T4vYv https://godbolt.org/z/dof4T4vYv But it also does some magic that I don't quite understand (what do the two `sub` instructions do before the `call`? Do they prepare the stack?) because x86 assembly is so confusing to me sometimes.
- jeroenhd 3y agoIf you can keep the local variables down, a simple ulimit -s 60000000 should be able to get that stack limit nice and big! You may need to call setrlimit with an appropriate RLIMIT_STACK, but I think the FFI compatibility should be able to pull that off, right?
- someplaceguy 3y ago> This will cause a stack overflow. You can convert that into a loop and make your own stack on the heap if you need very deep recursion. Doesn't Go allocate / extend stacks using dynamic allocation rather than having a static limit (e.g. like C)?
- deleted 3y ago[deleted]
- myaccountonhn 3y agoYou can also use beautiful mutual recursion a la ocaml let rec isEven n = if n = 0 then true else isOdd (n-1) and isOdd n = not (isEven n)
- paulddraper 3y agoFYI ES2015 added tail-call optimization, allowing JS to finally have an elegant isOdd function.
- webstrand 3y agoOnly Safari supports it, though