Can anyone help me with this please?
(define f (lambda (x)
(cond
((null? x) 0)
(#t (+ (* (car x) (car x)) (f (cdr x)))))))
I couldn't understand if this function is tail recursive or not? If it is, what is the reason?
Asked
Active
Viewed 133 times
0
Svante
- 50,694
- 11
- 78
- 122
user2631892
- 25
- 1
- 1
- 7
-
http://stackoverflow.com/questions/33923/what-is-tail-recursion – Alexej Magura Jul 29 '13 at 21:29
-
1No, you have to keep the results of (* (car x) (car x)) on the stack while you wait for (f (cdr x)) to be evaluated. In a tail call you could throw it away and get the same answer. – WorBlux Jul 30 '13 at 00:55
1 Answers
4
It's not tail recursive because the last thing the function does before returning is to evaluate (+ ...). In order to be tail recursive the last operation before returning has to be the recursive call.
Making a function tail recursive usually involves a helper function which takes an accumulator parameter:
(define f0 (lambda (x acc)
(if (null? x)
acc
(f0 (cdr x) (+ acc (* (car x)(car x)))))))
(define f (lambda (x)
(f0 x 0)))
Ferruccio
- 98,941
- 38
- 226
- 299
-
Hey can you please provide the tail recursive code so i can understand it more easily. – user2631892 Jul 29 '13 at 22:02
-
You don't need an aculumulator per se, just some way to pass the state of the recursion along to the next call. – WorBlux Jul 30 '13 at 00:58