Nim is not a functional language. You should avoid unbounded recursion, even if
it's tail recursion; it's not idiomatic and you are at the mercy of your C
compiler to optimize it out. So in this case you should prefer the iterative
version.
That said, if you really want to tail recurse, here's some mistakes you can
correct to get it optimized out (at least on my computer...):
* [idx..^1] does not do what you think it does. It's essentially equivalent
to substr, and allocates a new string. What you really want is an
openArray[char], and the toOpenArray function, which is a non-copying slice.
Rule of thumb: don't use [m..n] slices unless you want to copy.
* Making the accumulator a var is a good idea, but why not just use a string?
With a string accumulator, you are just appending stuff with the occasional
realloc. With a seq accumulator, you have to allocate a gazillion strings and
then a final one, which is slow.
* Put string allocations inside a separate block in the function. This way,
they go out of scope before the tail call and Nim can deallocate them
(therefore allowing the C compiler to turn the call into a loop.)
Putting it all together:
import std/[strformat, strutils]
# changed input to openArray[char]
proc findDiffCharIdx(input: openArray[char]): int =
let first = input[0]
for i, c in input:
if c != first:
return i
# all the same, diff is len
return input.len
# gets optimized properly
proc lookAndSay(input: openArray[char], acc: var string) =
if input.len < 1:
return
let idx = findDiffCharIdx(input)
block: # $idx allocates! so get it to deallocate before the tail call.
acc &= $idx
acc &= input[0] # this uses nimAddCharV1, so it's fine to put it outside
lookAndSay(input.toOpenArray(idx, input.high), acc)
proc main() =
var input = "3113322113"
for i in 0..<50:
var acc = ""
lookAndSay(input, acc)
input = acc
echo i , " ", input.len
echo fmt"output {input.len}"
main()
Run
BTW, all info about allocations is in the generated C code; please check it out
yourself with your variations.
`nim c -d:release --nimcache:/tmp/myprog myprog.nim` will put the C files in
`/tmp/myprog`, so that it is easy to inspect.
