Is this Scheme function recursive?

Question

Given the following function, am I allowed to say that it is recursive? Why I ask this question is because the 'fac' function actually doesn't call itself recursively, so am I still allowed to say that it is a recursive function even though the only function that calls itself is fac-iter?

(define (fac n)

  (define (fac-iter counter result)
    (if (= counter 0)
        result
        (fac-iter (- counter 1) (* result counter))))

  (fac-iter n 1))

Answer 1

One problem with calling fac formally recursive is that fac-iter is liftable out of fac. You can write the code like this:

(define (fac-iter counter result)
  (if (= counter 0)
      result
      (fac-iter (- counter 1) (* result counter))))

(define (fac n)
  (fac-iter n 1))

fac is an interface which is implemented by a recursive helper function.

If the helper function had a reason to be inside fac, such as accessing the parent's local variables, then there would be more justification for calling fac formally recursive: a significant piece of the interior of fac, a local funcction doing the bulk of the work, is internally recursive, and that interior cannot be moved to the top level without some refactoring.

Informally we can call fac recursive regardless if what we mean by that is that the substantial bulk of its work is done by a recursive approach. We are emphasizing the algorithm that is used, not the details over how it is integrated.

If a homework problem states "please implement a recursive solution to the binary search problem", and the solution is required to take the form of a bsearch.scm file, then obviously the problem statement doesn't mean that the bsearch.scm file must literally invoke itself, right? It means that the main algorithmic content in that file is recursive.

Or when we say that "the POSIX utility find performs a recursive traversal of the filesystem" we don't mean that find forks and executes a copy of itself for every directory it visits.

There is room for informality: calling something recursive without meaning that the entry point of that thing which has that thing's name is literally calling itself.

On another note, in some situations the term "recursion" in the Scheme context is used to denote recursion that requires stack storage; tail calls that are required to be rewritten to express iteration aren't called recursion. That's just taking the point of view of the implementation; what the compiled code is doing. Tail calls are sometimes called "stackless recursion" as a kind of compromise. The situation is complicated because tail calls alone do not eliminate true recursion. There is a way of compiling programs such that all procedure calls become tail calls, namely transformation to CPS (continuation passing style). Yet if the source program performs true recursion that requires a stack, the CPS-transformed program will also, in spite of using nothing but tail calls. What will happen is that an ad hoc stack will emerge via a chain of captured lambda environments. A lambda being used as a continuation captures the previous continuation as a lexical variable. The previous continuation itself captures another such a continuation in its environment, and so on. A heap-allocated chain emerges which constitutes the de facto return stack for the recursion. For reasons like this we cannot automatically conclude that when we see tail calls, we have iteration and not recursion.

An example looks like this. The traversal of a binary tree is truly recursive, right? When we visit the left child, that visitation must return, so that we can then visit the right child. The right child visit can be a tail call, but the left one isn't. Under CPS, they can both be tail calls:

     (define (traverse tree contin)
       (cond
         [(null? tree) (contin)] ;; tail call to continuation
         [else (traverse (tree-left tree) ;; tail call to traverse
                         (lambda ()
                            (traverse (right tree) contin)))])) ;; ditto!

so here, when the left node is traversed, that is a tail call: the last thing our procedure does is call (traverse (tree-left tree) (lambda ...)). But it passes that lambda as a continuation, and that continuation contains more statements to execute when it is invoked, which is essentially the same as if control returned there via a procedure retun. If we take the point of view that tail calls aren't recursion then we are justified in saying that the function isn't recursive. Yet it has the recursive control flow structure, uses storage proportional to the left depth of the tree, and does so without appearing to maintain an explicit stack structure. As if that weren't enough, the following obviously recursive program can be automatically converted to the above:

     (define (traverse tree)
       (cond
         [(null? tree)] ;; return
         [else (traverse (tree-left tree))
               (traverse (tree-right tree))]))
 

The CPS transformation inserts the continuations and lambdas, turning everything into tail calls that pass a continuation argument.

Answer 2

fac is not recursive: it does not refer to its own definition in any way.

fac-iter is recursive: it does refer to its own definition. But in Scheme it will create an iterative process, since its calls to itself are tail calls.

(In casual speech I think people would often say that neither fac nor fac-iter is recursive in Scheme, but I think speaking more precisely the above is correct.)