Is this Scheme function recursive?-CodePudding

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

CodePudding user response：

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

CodePudding user response：

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-iter, 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.