Menu
I've written Collatz conjecture in Scheme:
(define C
(lambda (n)
(cond
((eq? n 1) 1)
((even? n) (C (/ n 2)))
(else (C (+ (* n 3) 1))))))
This is a tail recursive call, yet I get stack overflow when I call (C 121):
guile> (trace C)
(C)
guile> (C 121)
[C 121]
[C 364]
[C 182]
[C 91]
[C 274]
[C 137]
[C 412]
[C 206]
[C 103]
[C 310]
[C 155]
[C 466]
[C 233]
[C 700]
[C 350]
[C 175]
[C 526]
[C 263]
[C 790]
[C 395]
[C 1186]
ERROR: Stack overflow
ABORT: (stack-overflow)
Why is proper tail recursion causing an overflow? As you can see, I'm using Guile as a Scheme interpreter (version 1.8.7).
905
Tail Recursion. Tail recursion is a recursion of a function where it does not consumes stack space and hence prevents stack overflow.
No. Go for readability. Many computations are better expressed as recursive (tail or otherwise) functions. The only other reason to avoid them would be if your compiler does not do tail call optimizations and you expect you might blow the call stack.
Recursion is a term used to describe a procedure that calls itself, directly or indirectly. In Scheme, simple program repetition/iteration can be achieved via recursion by having a function call itself. Most programs are tail recursive, where the recursive call is the last action that occurs.
What Is Tail Recursion? In tail recursion, there is no other operation to perform after executing the recursive function itself; the function can directly return the result of the recursive call. In simple words, in tail recursion, the recursive function is called last. So it is more efficient than non-tail recursion.
The procedure as defined works fine in Racket. It seems like a bug to me, or something very specific to your environment.
Almost certainly not related to your problem, but a bit of nit-picking: use the comparison (= n 1) for numbers instead of (eq? n 1).
110
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
