recursionschemetail-recursionfoldfoldleft

How to make this Scheme function not tail recursive?


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))))

Solution

  • 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.