Reputation: 9875
Can a recursion with nested calls in tail position be tail recursion?
Can a recursion with nested calls in tail position be tail recursion?
For example, I have the following function in Racket that is intended to convert a binary tree, defined as a nested struct below, to a list,
where, at least in the apperance, only roughly half of the recursive calls are in tail positions while the other half are not.
(define-struct node (key left right))
;; postorder traversal which converts a Binary Search Tree to an ascending list
(define (bst->list-help b acc)
(cond
[(empty? b) acc]
[else (bst->list-help (node-left b)
(cons (node-key b)
(bst->list-help (node-right b) acc)))]))
(define (bst->list b)
(bst->list-help b empty))
Is bst->list-help tail recursive?
Upvotes: 3
Views: 207
Answers (4)
Reputation: 71109
A function is tail-recursive if every function call in it, which, directly or indirectly, may cause it to be called further down the execution path, is in tail position.
A call is in tail position in a function if it is the very last thing that function is doing, and all that's left for that function to do after the call returns a value, is to return that value.
As such your example function is not tail-recursive, since a value returned from the nested call to itself, is not being returned right away, but rather is used as an argument to another call. That that call is again a recursive call i.e. a call to itself, it immaterial.
Only the recursive calls in tail position can receive TCO, no others can. You can transform your code into CPS, then every call becomes in tail position, at the cost of creating more and more continuation objects (closures, usually) in the "heap" i.e. dynamic memory.
Some implementations (e.g. Racket, reportedly) use heap memory for control stack anyway, so it doesn't change much there, really. Except that CPS code makes the order of evaluation to be explicit in code itself.
Some more remarks.
Your code does "reversed inorder" traversal, visiting the right branch first, then the node's value, then the left branch. When it creates 0123456789 list it does so in the right-to-left order, by visiting 9 first and 0 last, building the result list bottom-up, placing the leftmost element in the result list last.
The usual definition of inorder traversal visits 0 first, and 9 last, and would place them into the result array in the left-to-right, or "top-down" order, placing the leftmost element in the result array first.
Your code behaves this way because Scheme's cons is eager. Where the cons to be lazy, the order would indeed be left-->node-->right, with the lazy list being filled top-down.
Or we could build the result list as a normal eager list in top-down manner too, by maintaining and modifying the pointer to the growing list's last cons cell, using set-cdr!, implementing what the TRMC optimization would do.
As to the question of how to make it tail-recursive, see about the "gopher" trick by John McCarthy in my answers, or specifically this answer of mine for a general approach to this kind of thing (it's about flattening nested lists, but car-cdr lists are trees anyway).
Now, what about your function? Writing in a free-hand equational pattern-matching visually-oriented case-by-case pseudocode, you have
g E acc = acc
g {lt x rt} acc = g lt [x, ...g rt acc]
Here ... means splicing in place.
Trying it out on paper with some sample input (taken from Mulan's answer),
myTree = { {{{E 0 E} 1 {E 2 E}} 3 {E 4 E}} -- lt
5 -- val
{{E 6 E} 7 {{E 8 E} 9 E}} } -- rt
--- linear: right-to-left:
g { {{{E 0 E} 1 {E 2 E}} 3 {E 4 E}} 5 {{E 6 E} 7 {{E 8 E} 9 E}} } []
= g {{{E 0 E} 1 {E 2 E}} 3 {E 4 E}} [5, ...g {{E 6 E} 7 {{E 8 E} 9 E}} []]
= g {{{E 0 E} 1 {E 2 E}} 3 {E 4 E}} [5, ...g {E 6 E} [7, ...g {{E 8 E} 9 E} []]]
= g {{{E 0 E} 1 {E 2 E}} 3 {E 4 E}} [5, ...g {E 6 E} [7, ...g {E 8 E} [9, ...g E []]]]
= g {{{E 0 E} 1 {E 2 E}} 3 {E 4 E}} [5, ...g {E 6 E} [7, ...g {E 8 E} [9, ...[]]]]
= g {{{E 0 E} 1 {E 2 E}} 3 {E 4 E}} [5, ...g {E 6 E} [7, ...g {E 8 E} [9]]]
= g {{{E 0 E} 1 {E 2 E}} 3 {E 4 E}} [5, ...g {E 6 E} [7, ...g E [8, ...g E [9]]]]
= g {{{E 0 E} 1 {E 2 E}} 3 {E 4 E}} [5, ...g {E 6 E} [7, ...g E [8, ...[9]]]]
= g {{{E 0 E} 1 {E 2 E}} 3 {E 4 E}} [5, ...g {E 6 E} [7, ...g E [8, 9]]]
= g {{{E 0 E} 1 {E 2 E}} 3 {E 4 E}} [5, ...g {E 6 E} [7, ...[8, 9]]]
= g {{{E 0 E} 1 {E 2 E}} 3 {E 4 E}} [5, ...g {E 6 E} [7, 8, 9]]
= g {{{E 0 E} 1 {E 2 E}} 3 {E 4 E}} [5, ...g E [6, ...g E [7, 8, 9]]]
= g {{{E 0 E} 1 {E 2 E}} 3 {E 4 E}} [5, ...g E [6, ...[7, 8, 9]]]
= g {{{E 0 E} 1 {E 2 E}} 3 {E 4 E}} [5, ...g E [6, 7, 8, 9]]
= g {{{E 0 E} 1 {E 2 E}} 3 {E 4 E}} [5, ...[6, 7, 8, 9]]
= g {{{E 0 E} 1 {E 2 E}} 3 {E 4 E}} [5, 6, 7, 8, 9]
= g {{E 0 E} 1 {E 2 E}} [3, ...g {E 4 E} [5, 6, 7, 8, 9]]
= g {{E 0 E} 1 {E 2 E}} [3, ...g E [4, ...g E [5, 6, 7, 8, 9]]]
= g {{E 0 E} 1 {E 2 E}} [3, ...g E [4, ...[5, 6, 7, 8, 9]]]
= g {{E 0 E} 1 {E 2 E}} [3, ...g E [4, 5, 6, 7, 8, 9]]
= g {{E 0 E} 1 {E 2 E}} [3, ...[4, 5, 6, 7, 8, 9]]
= g {{E 0 E} 1 {E 2 E}} [3, 4, 5, 6, 7, 8, 9]
= g {E 0 E} [1, ...g {E 2 E} [3, 4, 5, 6, 7, 8, 9]]
= g {E 0 E} [1, ...g E [2, ...g E [3, 4, 5, 6, 7, 8, 9]]]
= g {E 0 E} [1, ...g E [2, ...[3, 4, 5, 6, 7, 8, 9]]]
= g {E 0 E} [1, ...g E [2, 3, 4, 5, 6, 7, 8, 9]]
= g {E 0 E} [1, ...[2, 3, 4, 5, 6, 7, 8, 9]]
= g {E 0 E} [1, 2, 3, 4, 5, 6, 7, 8, 9]
= g E [0, ...g E [1, 2, 3, 4, 5, 6, 7, 8, 9]]
= g E [0, ...[1, 2, 3, 4, 5, 6, 7, 8, 9]]
= g E [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
= [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
This is just for illustration, under the conditions of ASCII-based art. In reality, in Scheme, only the innermost parts are evaluated, – those to the right of the rightmost g on each line – and all the outer parts which are shown here in each re-write are left behind, above the current point in the control stack. Imagine them greyed-out, here, creating a jagged triangular structure, as usual in stack-based eager evaluation.
With some equational reasoning, a few shortcut cases can be added to the definition, for quicker evaluation, at the cost of more efforts being spent at pattern recognition:
g E acc = acc
g {lt x rt} acc = g lt [x, ...g rt acc]
==
g E acc = acc
g {E x E } acc = g E [x, ...g E acc]
= g E [x, ...acc]
= [x, ...acc]
g {E x rt} acc = g E [x, ...g rt acc]
= [x, ...g rt acc]
g {lt x E } acc = g lt [x, ...g E acc]
= g lt [x, ...acc]
g {lt x rt} acc = g lt [x, ...g rt acc]
so that the execution sequence becomes
g { {{{E 0 E} 1 {E 2 E}} 3 {E 4 E}} 5 {{E 6 E} 7 {{E 8 E} 9 E}} } []
= g {{{E 0 E} 1 {E 2 E}} 3 {E 4 E}} [5, ...g {{E 6 E} 7 {{E 8 E} 9 E}} []]
= g {{{E 0 E} 1 {E 2 E}} 3 {E 4 E}} [5, ...g {E 6 E} [7, ...g {{E 8 E} 9 E} []]]
= g {{{E 0 E} 1 {E 2 E}} 3 {E 4 E}} [5, ...g {E 6 E} [7, ...g {E 8 E} [9]]]
= g {{{E 0 E} 1 {E 2 E}} 3 {E 4 E}} [5, ...g {E 6 E} [7, ...[8, ...[9]]]]
= g {{{E 0 E} 1 {E 2 E}} 3 {E 4 E}} [5, ...g {E 6 E} [7, 8, 9]]
= g {{{E 0 E} 1 {E 2 E}} 3 {E 4 E}} [5, ...[6, ...[7, 8, 9]]]
= g {{{E 0 E} 1 {E 2 E}} 3 {E 4 E}} [5, 6, 7, 8, 9]
= g {{E 0 E} 1 {E 2 E}} [3, ...g {E 4 E} [5, 6, 7, 8, 9]]
= g {{E 0 E} 1 {E 2 E}} [3, ...[4, ...[5, 6, 7, 8, 9]]]
= g {{E 0 E} 1 {E 2 E}} [3, 4, 5, 6, 7, 8, 9]
= g {E 0 E} [1, ...g {E 2 E} [3, 4, 5, 6, 7, 8, 9]]
= g {E 0 E} [1, ...[2, ...[3, 4, 5, 6, 7, 8, 9]]]
= g {E 0 E} [1, 2, 3, 4, 5, 6, 7, 8, 9]
= [0, ...[1, 2, 3, 4, 5, 6, 7, 8, 9]]
= [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
g E acc = acc
g {E x E } acc = [x, ...acc]
g {E x rt} acc = [x, ...g rt acc]
g {lt x E } acc = g lt [x, ...acc]
g {lt x rt} acc = g lt [x, ...g rt acc]
Again, this is illustrative, showing the left-behind parts on each re-write line. They appear on each line only as a reminder of the control stack frames above the execution point.
But actually, this gives us the idea of re-arranging all the "noise" characters, really leaving only one g on each line, the very first one, making the execution indeed control stack–free:
g { { { {E 0 E} 1 {E 2 E}} 3 {E 4 E}} 5. {{E 6 E} 7 {{E 8 E} 9 E}} } []
= g { { { { {E 0 E} 1 {E 2 E}} 3 {E 4 E}} 5 {E 6 E}} 7. {{E 8 E} 9 E} } []
= g { { { { { {E 0 E} 1 {E 2 E}} 3 {E 4 E}} 5 {E 6 E}} 7 {E 8 E}} 9.E } []
= g { { { { {E 0 E} 1 {E 2 E}} 3 {E 4 E}} 5 {E 6 E}} 7. {E 8 E}} [9]
= g {{{ { { {E 0 E} 1 {E 2 E}} 3 {E 4 E}} 5 {E 6 E}} 7 E} 8.E } [9]
= g {{ { { {E 0 E} 1 {E 2 E}} 3 {E 4 E}} 5 {E 6 E}} 7. E} [8,9]
= g { { { {E 0 E} 1 {E 2 E}} 3 {E 4 E}} 5. {E 6 E}} [7,8,9]
= g {{{ { {E 0 E} 1 {E 2 E}} 3 {E 4 E}} 5 E} 6.E } [7,8,9]
= g {{ { {E 0 E} 1 {E 2 E}} 3 {E 4 E}} 5. E} [6,7,8,9]
= g { { {E 0 E} 1 {E 2 E}} 3. {E 4 E}} [5,6,7,8,9]
= g {{{ {E 0 E} 1 {E 2 E}} 3 E} 4.E } [5,6,7,8,9]
= g {{ {E 0 E} 1 {E 2 E}} 3. E} [4,5,6,7,8,9]
= g { {E 0 E} 1.{E 2 E}} [3,4,5,6,7,8,9]
= g {{{E 0 E} 1 E} 2.E } [3,4,5,6,7,8,9]
= g {{E 0 E} 1.E} [2,3,4,5,6,7,8,9]
= g {E 0.E} [1,2,3,4,5,6,7,8,9]
= g E [0,1,2,3,4,5,6,7,8,9]
= [0,1,2,3,4,5,6,7,8,9]
The dot marks the root.
Here the tree itself, being re-arranged, rotated to the left, serves as the data stack replacement for the original control stack. And when the right branch isEmpty, the root element is the rightmost element in the tree, so we take it off and continue with the left branch.
This should be translatable into the proper Scheme with relative ease.
This approach implements the "gopher" trick mentioned above, only instead of "burrowing" into the left end, it does so into the right, to serve Scheme's cons better. In conj-based languages which create their arrays from the left, we'd rotate the tree to the right.
Upvotes: 1
Reputation: 350771
A nested call is never in tail position, because its return value is then still used as an argument for that other call in which it is nested. Only the final call, which must not be a nested one, can benefit from tail call optimisation, if it is indeed the very last thing that the function is doing.
Upvotes: 1
Reputation: 135367
Using a binary search tree with your node struct -
(define my-tree
(node 5
(node 3
(node 1
(node 0 empty empty)
(node 2 empty empty))
(node 4 empty empty))
(node 7
(node 6 empty empty)
(node 9
(node 8 empty empty)
empty))))
Running your program, as you describe, converts the tree to an ascending list,
(bst->list my-tree)
'(0 1 2 3 4 5 6 7 8 9)
With one small exception, this in an inorder traversal, not postorder -
You can see preorder and postorder here -
(define (preorder b)
(define (loop b acc)
(if (empty? b)
acc
(cons (node-key b)
(loop (node-left b)
(loop (node-right b)
acc)))))
(loop b empty))
(define (postorder b)
(define (loop b acc)
(if (empty? b)
acc
(loop (node-left b)
(loop (node-right b)
(cons (node-key b)
acc)))))
(loop b empty))
(preorder my-tree)
(postorder my-tree)
'(5 3 1 0 2 4 7 6 9 8)
'(0 2 1 4 3 6 8 9 7 5)
To use the technique from the Ocaml post, we start with inorder -
(define (inorder b)
(define (loop b acc)
(if (empty? b)
acc
(loop (node-left b)
(cons (node-key b)
(loop (node-right b)
acc)))))
(loop b empty))
We add the return argument to our function, initialized to the identity function -
(define (inorder b)
(define (loop b acc return)
(if (empty? b)
(return acc)
(loop (node-right b)
acc
(lambda (r)
(loop (node-left b)
(cons (node-key b) r)
return)))))
(loop b empty (lambda (x) x)))
Now you can see loop is always in tail position. Our program still works as expected -
(inorder my-tree)
'(0 1 2 3 4 5 6 7 8 9)
Using the pen & paper technique, we can trace the evaluation of inorder to verify that it does not grow the stack
(inorder my-tree)
; (loop b empty (lambda (x) x))
(loop (node 5
(node 3
(node 1
(node 0 empty empty)
(node 2 empty empty))
(node 4 empty empty))
(node 7
(node 6 empty empty)
(node 9
(node 8 empty empty)
empty)))
empty
(lambda (x) x))
; (loop (node-right b)
; acc
; (lambda (r)
; (loop (node-left b)
; (cons (node-key b) r)
; return)))))
(loop (node 7
(node 6 empty empty)
(node 9
(node 8 empty empty)
empty))
empty
(lambda (r)
(loop (node 3
(node 1
(node 0 empty empty)
(node 2 empty empty))
(node 4 empty empty))
(cons 5 r)
(lambda (x) x))))
(loop (node 9
(node 8 empty empty)
empty)
empty
(lambda (r)
(loop (node 6 empty empty)
(cons 7 r)
(lambda (r)
(loop (node 3
(node 1
(node 0 empty empty)
(node 2 empty empty))
(node 4 empty empty))
(cons 5 r)
(lambda (x) x))))))
(loop empty
empty
(lambda (r)
(loop (node 8 empty empty)
(cons 9 r)
(lambda (r)
(loop (node 6 empty empty)
(cons 7 r)
(lambda (r)
(loop (node 3
(node 1
(node 0 empty empty)
(node 2 empty empty))
(node 4 empty empty))
(cons 5 r)
(lambda (x) x))))))))
; (return acc)
((lambda (r)
(loop (node 8 empty empty)
(cons 9 r)
(lambda (r)
(loop (node 6 empty empty)
(cons 7 r)
(lambda (r)
(loop (node 3
(node 1
(node 0 empty empty)
(node 2 empty empty))
(node 4 empty empty))
(cons 5 r)
(lambda (x) x))))))) empty)
(loop (node 8 empty empty)
(cons 9 empty)
(lambda (r)
(loop (node 6 empty empty)
(cons 7 r)
(lambda (r)
(loop (node 3
(node 1
(node 0 empty empty)
(node 2 empty empty))
(node 4 empty empty))
(cons 5 r)
(lambda (x) x))))))
(loop empty
'(9)
(lambda (r)
(loop empty
(cons 8 r)
(lambda (r)
(loop (node 6 empty empty)
(cons 7 r)
(lambda (r)
(loop (node 3
(node 1
(node 0 empty empty)
(node 2 empty empty))
(node 4 empty empty))
(cons 5 r)
(lambda (x) x))))))))
((lambda (r)
(loop empty
(cons 8 r)
(lambda (r)
(loop (node 6 empty empty)
(cons 7 r)
(lambda (r)
(loop (node 3
(node 1
(node 0 empty empty)
(node 2 empty empty))
(node 4 empty empty))
(cons 5 r)
(lambda (x) x))))))) '(9))
(loop empty
(cons 8 '(9))
(lambda (r)
(loop (node 6 empty empty)
(cons 7 r)
(lambda (r)
(loop (node 3
(node 1
(node 0 empty empty)
(node 2 empty empty))
(node 4 empty empty))
(cons 5 r)
(lambda (x) x))))))
((lambda (r)
(loop (node 6 empty empty)
(cons 7 r)
(lambda (r)
(loop (node 3
(node 1
(node 0 empty empty)
(node 2 empty empty))
(node 4 empty empty))
(cons 5 r)
(lambda (x) x))))) '(8 9))
(loop (node 6 empty empty)
(cons 7 '(8 9))
(lambda (r)
(loop (node 3
(node 1
(node 0 empty empty)
(node 2 empty empty))
(node 4 empty empty))
(cons 5 r)
(lambda (x) x))))
(loop empty
'(7 8 9)
(lambda (r)
(loop empty
(cons 6 r)
(lambda (r)
(loop (node 3
(node 1
(node 0 empty empty)
(node 2 empty empty))
(node 4 empty empty))
(cons 5 r)
(lambda (x) x))))))
((lambda (r)
(loop empty
(cons 6 r)
(lambda (r)
(loop (node 3
(node 1
(node 0 empty empty)
(node 2 empty empty))
(node 4 empty empty))
(cons 5 r)
(lambda (x) x))))) '(7 8 9))
(loop empty
(cons 6 '(7 8 9))
(lambda (r)
(loop (node 3
(node 1
(node 0 empty empty)
(node 2 empty empty))
(node 4 empty empty))
(cons 5 r)
(lambda (x) x))))
((lambda (r)
(loop (node 3
(node 1
(node 0 empty empty)
(node 2 empty empty))
(node 4 empty empty))
(cons 5 r)
(lambda (x) x))) '(6 7 8 9))
(loop (node 3
(node 1
(node 0 empty empty)
(node 2 empty empty))
(node 4 empty empty))
(cons 5 '(6 7 8 9))
(lambda (x) x))
(loop (node 4 empty empty)
'(5 6 7 8 9)
(lambda (r)
(loop (node 1
(node 0 empty empty)
(node 2 empty empty))
(cons 3 r)
(lambda (x) x))))
(loop empty
'(5 6 7 8 9)
(lambda (r)
(loop empty
(cons 4 r)
(lambda (r)
(loop (node 1
(node 0 empty empty)
(node 2 empty empty))
(cons 3 r)
(lambda (x) x))))))
((lambda (r)
(loop empty
(cons 4 r)
(lambda (r)
(loop (node 1
(node 0 empty empty)
(node 2 empty empty))
(cons 3 r)
(lambda (x) x))))) '(5 6 7 8 9))
(loop empty
(cons 4 '(5 6 7 8 9))
(lambda (r)
(loop (node 1
(node 0 empty empty)
(node 2 empty empty))
(cons 3 r)
(lambda (x) x))))
((lambda (r)
(loop (node 1
(node 0 empty empty)
(node 2 empty empty))
(cons 3 r)
(lambda (x) x))) '(4 5 6 7 8 9))
(loop (node 1
(node 0 empty empty)
(node 2 empty empty))
(cons 3 '(4 5 6 7 8 9))
(lambda (x) x))
(loop (node 2 empty empty)
'(3 4 5 6 7 8 9)
(lambda (r)
(loop (node 0 empty empty)
(cons 1 r)
(lambda (x) x))))
(loop empty
'(3 4 5 6 7 8 9)
(lambda (r)
(loop empty
(cons 2 r)
(lambda (r)
(loop (node 0 empty empty)
(cons 1 r)
(lambda (x) x))))))
((lambda (r)
(loop empty
(cons 2 r)
(lambda (r)
(loop (node 0 empty empty)
(cons 1 r)
(lambda (x) x))))) '(3 4 5 6 7 8 9))
(loop empty
(cons 2 '(3 4 5 6 7 8 9))
(lambda (r)
(loop (node 0 empty empty)
(cons 1 r)
(lambda (x) x))))
((lambda (r)
(loop (node 0 empty empty)
(cons 1 r)
(lambda (x) x))) '(2 3 4 5 6 7 8 9))
(loop (node 0 empty empty)
(cons 1 '(2 3 4 5 6 7 8 9))
(lambda (x) x))
(loop empty
'(1 2 3 4 5 6 7 8 9)
(lambda (r)
(loop empty
(cons 0 r)
(lambda (x) x))))
((lambda (r)
(loop empty
(cons 0 r)
(lambda (x) x))) '(1 2 3 4 5 6 7 8 9))
(loop empty
(cons 0 '(1 2 3 4 5 6 7 8 9))
(lambda (x) x))
((lambda (x) x) '(0 1 2 3 4 5 6 7 8 9))
'(0 1 2 3 4 5 6 7 8 9)
Upvotes: 4
Reputation: 46455
What do you mean by the function itself being tail-recursive?
Yes, tail recursion is being applied to those calls. It is not to the nested calls. This avoids creating many stack frames. But as you walk right, you will still get a deep stack.
So the function is benefitting from the optimization. But only on half of your recursive calls. What do you want to call that?
Upvotes: 0
Related Questions
- What is tail recursion?
- Why does this code behave like tail recursion
- How exactly is the print statement working in these two methods?
- Splitting a BinTree with tail recursion in Haskell
- FInding minimum of a binary search tree in Racket
- How can i maintain state between recursion calls
- How to achieve tail recursion on a tree-shaped data structure
- Output Post-Order Binary Search Tree from Given Pre-Order input without constructing tree or using recursions
- implementing bst in racket
- Why my merge sort implementation in Scheme is so slow?