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