I can't figure out how can I make this tail recursive Scheme function not tail recursive anymore. Anyone can help me?
(define (foldrecl f x u)
(if (null? x)
u
(foldrecl f (cdr x) (f (car x) u))))
left folds are inheritly iterative, but you can easily make them recursive by adding a continuation. eg.
(let ((value expresion-that-calculates))
value)
So in your case:
(define (foldrecl f x u)
(if (null? x)
u
(let ((result (foldrecl f (cdr x) (f (car x) u))))
result)))
While this looks promising it does not guarantee that a smart Scheme implementation figures out that result
is just returned and make it a tail call instead. Right folds are easier since they are inherently recursive:
(define (fold-right proc tail lst)
(if (null? lst)
tail
(proc (car lst)
(fold-right proc tail (cdr lst)))))
Here you clearly see the recursive part needs to become a argument to cons
and thus never in tail position unless it is the base case.
Also notice it's slightly simpler to see what arguments goes where when the procedure is called proc
, the tail of the result tail
and the list argument lst
. You don't even need to read my code to know how to use it, but yours I have no idea what x
and u
and ti doesn't help that the argument order doesn't follow any fold
implementations known in Scheme.