Is such a function structure tail recursive?

Question

Is such a function structure tail recursive?

function foo(data, acc) {
    ...
    return foo(data, foo(data, x));
}

By definition a recursive function is tail recursive when recursive call is the last thing executed by the function. In this example, the last thing the function does is calling the foo and return its value, however before that it uses the return value of nested foo function. Thus I am confused.

Edit: Consider the scheme language and a simple function that multiplies the elements in a given list:

Example 1:

(define (foo list) (helper list 1) )

(define (helper list acc)
  (cond ((null? list) acc)
   ((not (pair? list)) (* list acc))
   ((list? (car list)) (helper (car list) (helper (cdr list) acc)))
   (else (helper (cdr list) (* acc (car list)))))
)

Example 2: Is this one pure tail-recursive?

(define (foo list) (helper list 1) )

(define (helper list acc)
    (cond ((null? list) acc)
    ((not (pair? list)) (* list acc))
    ((list? (car list)) (helper (cdr list) (* (foo (car list)) acc)))
    (else (helper (cdr list) (* acc (car list))))))

Based on the answer, I am assuming that first one is not pure tail recursive.

Answer 1

No, it is not tail-recursive because foo is called out of tail position -

function foo(data, acc) {
    ...
                     // foo not in tail position here
    return foo(data, foo(data, x));
}

Let's work through this using a concrete program like fibonacci -

const fibonacci = n =>
  n < 2
    ? n                   // non tail call!
    : fibonacci (n - 2) + fibonacci (n - 1)
    
console .log (fibonacci (10)) // 55

Above, the recursive fibonacci can spawn two calls to fibonacci, each which can spawn two more calls to fibonacci. Without rewriting it, it's impossible for both calls to be in tail position. We can get around the issue using a helper function that has an additional parameter, then below -

const helper = (n, then) =>
{ if (n < 2)
    return then (n)                // tail
  else 
    return helper (n - 2, a =>     // tail
             helper (n - 1, b =>   // tail
               then (a + b)        // tail
           ))
}

const fibonacci = n =>
{ return helper (n, x => x)        // tail
}
    
console .log (fibonacci (10)) // 55

Some languages allow you to specify default arguments, making it unnecessary to use a separate auxiliary function -

const identity = x =>
  x

const fibonacci = (n, then = identity) =>
{ if (n < 2)
    return then (n)                  // tail
  else 
    return fibonacci (n - 2, a =>    // tail
             fibonacci (n - 1, b =>  // tail
               then (a + b)          // tail
           ))
}

console .log (fibonacci (10))
// 55

fibonacci (10, res => console .log ("result is", res))
// result is: 55

Tail recursive or not, fibonacci above is an exponential process, making it terribly slow for even small values of n. A linear process is made possible by representing the state of our computation using additional parameters, a and b -

const fibonacci = (n, a = 0, b = 1) =>
  n === 0
    ? a                            // tail
    : fibonacci (n - 1, b, a + b)  // tail
  
console .log
  ( fibonacci (10)   // 55
  , fibonacci (20)   // 6765
  , fibonacci (100)  // 354224848179262000000
  )

Sometimes you'll need to use additional state parameters, sometimes you'll need to use helper functions or continuations like then.

We could probably write a more specific answer if you give us a specific problem using a specific language.

---

In your edited question, you include a Scheme program that can multiply a nested list of numbers. We show the then technique first

(define (deep-mult xs (then identity))
  (cond ((null? xs)
         (then 1))
        ((list? (car xs))
         (deep-mult (car xs) ;; tail
                    (λ (a)
                      (deep-mult (cdr xs) ;; tail
                                 (λ (b)
                                   (then (* a b)))))))
        (else
         (deep-mult (cdr xs) ;; tail
                    (λ (a)
                      (then (* a (car xs))))))))

(deep-mult '((2) (3 (4) 5))) ;; 120

You can use a state parameter acc like we did in the second technique too, but because the input can be nested, we must use the then technique to flatten the potential two calls to deep-mult -

(define (deep-mult xs (acc 1) (then identity))
  (cond ((null? xs)
         (then acc)) ;; tail
        ((list? (car xs))
         (deep-mult (car xs) ;; tail
                    acc
                    (λ (result)
                      (deep-mult (cdr xs) result then)))) ;; tail
        (else
         (deep-mult (cdr xs) ;; tail
                    acc
                    (λ (result) then (* result (car xs)))))))

(deep-mult '((2) (3 (4) 5)))
;; 120

I don't like this version of the program as much because each technique only solves half of the problem, whereas before only one technique was used.

Perhaps a clever workaround for this particular problem is to use append in the case of a nested list

(define (deep-mult xs (acc 1))
  (cond ((null? xs)
         acc)
        ((list? (car xs))
         (deep-mult (append (car xs) ;; tail
                            (cdr xs))
                    acc))
        (else
         (deep-mult (cdr xs) ;; tail
                    (* acc (car xs))))))

(deep-mult '((2) (3 (4) 5))) 
;; 120

However, append is a costly list operation and this procedure could have bad performance for lists that are nested very deeply. Of course there are other solutions too. See what you can come up with and ask additional questions. I'll share a solution I think offers the most advantages and fewest disadvantages afterward.

Answer 2

I think what's tricky here is that there are two different ways of thinking about tail recursive functions.

First, there are purely tail recursive functions, which are functions whose only recursion is done using tail recursion. In the case of what you have above, your function is not purely tail recursive because the recursion branches, and pure tail recursion can't branch.

Second, there are functions for which some of the recursion can be eliminated by using tail call optimizations. These are functions which perform whatever sort of recursion they'd like to perform, but which have at least one recursive call that can be rewritten non-recursively using tail call optimization. The function you have does fall into this category, because the compiler could

1. have recursive call foo(data, x) be made using true recursion, but
2. recycle the stack space to evaluate foo(data, /* result of that call */).

So is your function purely tail recursive? No, because the recursion branches. But could a good compiler optimize away one of those recursive calls? Yes.

Answer 3

In general, convert your function into SSA form by naming all the interim entities, then see if each call to your foo is in tail position, i.e. the very last thing to do.

How can there be more than one tail positions, you ask? They can if each is in its own branch of a conditional, and that conditional is itself in a tail position.

About your edited lisp functions. Both aren't tail recursive, even the last one where helper calls foo in non-tail position, because foo will eventually call helper, too. Yes, to be fully tail-recursive it must be that no call in non-tail position leads back to calling the function itself. But if it was in tail position then it's OK. Tail call is a glorified goto, which is the goal here.

But you can code this tail-recursively, by traversing the input nested list nay tree data structure, as

(define (foo list) (helper list 1) )

(define (helper list acc)
  (cond 
    ((null? list)  acc)
    ((not (pair? list))  (* list acc))
    ((null? (car list))  (helper (cdr list) acc))
    ((not (pair? (car list)))  (helper (cdr list) (* (car list) acc)))
    (else  (helper (cons (caar list)
                     (cons (cdar list) (cdr list))) acc))))

Answer 4

It might be nit-picking, but as such the function is not said to be tail-recursive. If a procedure call can occurs in a tail context, that call is said to be a tail call.

In your example:

function foo(data, acc) {
    ...
    return foo(data, foo(data, x));
}

or

(define (foo data acc)
  (foo data (foo data x)))

There are two calls: the inner one (foo data x) is not in tail context, but the outer one (foo data ...) is.

For a specification of tail contexts in R5RS Scheme, see [1].

In summary: to check whether a specific call is a tail call is a syntactic check.

Is your function "tail recursive"? That depends on how you define "a tail recursive function". If you mean "all recursive calls must be tail calls" - then no. If you mean "all body evaluations end with a recursive call" - then yes.

Now also of importance is the runtime behaviour of the function. What kind of computational process will take place, when you evaluate a function call? The explanation is a bit involved, so I'll punt and just leave a reference to: [2] SICP "1.2 Procedures and the Processes They Generate.".

[1] http://www.dave-reed.com/Scheme/r5rs_22.html [2] https://mitpress.mit.edu/sites/default/files/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2