recursionschemepseudocodetail-recursion

Is such a function structure tail recursive?


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.


Solution

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