I am (more than) a little confused about tail call optimisation. Does there have to be only one recursive call in the function for it to be optimised? Or can you have more than one as long as it is the last part of that function call? Sorry that is not very clear is it. This is a binary search function for a tree, (define (binary-search value tree)
(cond [(null? tree) null]
[(= value (tree-node-value tree)) tree]
[(< value (tree-node-value tree)) (binary-search value (tree-node-left tree))]
[(> value (tree-node-value tree)) (binary-search value (tree-node-right tree))]
[else (display "Bad")]))
```
Are both binary-search
calls tail calls or is this rubbish design?
I believe both are in tail position and will be optimized
it’s possible to check this taking a look at the generated bytecode
@andreiformiga Thanks, I hoped they should be but was concerned that they weren’t. Haven’t got around to doing bytecode inspection yet, just the basics.
heh, actually I think they’re tail calls in the byte code as well
you’d have to look at the generated assembly to see if they become jumps, but I’m almost certain they do
you can test this by passing a really big tree and see if the memory footprint keeps growing
@mark.warren Note: You can get DrRacket to show you, whether a call is a tail call or not: https://stackoverflow.com/a/12933639/23567
Yeah, I will do that soon in some tests. Just checking I was on the right track.
@soegaard2 Sweet, thanks.
Also check out the description on tail call in R5RS. They show exactly which call positions give you a tail call.
Thanks guys, that very useful.
You’ll run into people who are super picky about calling it “tail call optimization” vs. “tail call elimination”. In some languages, it’s an optimization the compiler might do. In Scheme and Racket, it’s guaranteed, you can depend on it (if something is truly in tail position). Which is why some people tend to get picky about saying “tail call elimination”.
Also it avoids fiery debates about whether it is spelled ‘optimisation’ vs. the obviously correct “optimization”. :grinning: