# How to call a recursive function without stackoverflow?

When calling

``````julia> f(x) = x>1 ? √(6+f(x-1)) : 1
f (generic function with 1 method)

julia> f(104475)
3.0

julia> f(104476)
ERROR: StackOverflowError:
Stacktrace:
 <
@ .\REPL:1 [inlined]
 >
@ .\operators.jl:382 [inlined]
 f(x::Int64) (repeats 79984 times)
@ Main .\REPL:1
``````

You get a stack overflow.
Is it possible to implicitly compile the function so that it isn’t recursive? So that it doesn’t cause a stack overflow?

AFAIK, no: even if the recursive call was in tail position (which is not the case here), Julia does not perform automatic Tail Call Optimization.

However, it’s rather straightforward (at least in this case, but also in many others) to convert the recursion into a loop. In your example, this would yield:

``````julia> function f(x)
res = 1
for i in 2:x
res = sqrt(6+res)
end
res
end
f (generic function with 1 method)

julia> f(104475)
3.0

julia> f(104476)
3.0
``````
1 Like

This should do it

``````function f(x)
r = 1
for n=2:s
r =  √(6+r)
end
return r
end
``````
1 Like

With IterTools package, there is a solution which feels a little more like recursion:

``````using IterTools
import Base.Iterators as Itr

foldl(((x,y))->y,Itr.take(iterated(x->√(6+x), 1.0),104475))
``````

It doesn’t allocate needlessly:

``````julia> @btime foldl(((x,y))->y,Itr.take(iterated(x->√(6+x),1.0),104475))
698.127 μs (0 allocations: 0 bytes)
3.0
``````
1 Like

Note that you probably want `res = 1.0` for type stability.

1 Like

Can you explain how this works?

The heavy lifting is done by `IterTools.iterated(f,x)` which repeatedly applies `f` on each iteration i.e. returns `x, f(x), f(f(x))`… This is wrapped by `take` from `Base.Iterators` which limits the items taken from an iterator. So starting with the innermost recursive call (in original recursive implementation), the value of `x` is `1.0` and then `f` is applied until the last time when the iterator value is similar to the recursive call output.

Finally, taking the last value of the iterator is not as simple as `last(itr)` alas, so `foldl` is used to discard all but last element.

Maybe this is clearer:

``````julia> itrlast(itr) = foldl((_,y)->y,itr)

julia> itrlast(Itr.take(iterated(x->√(6+x),1.0),104475))
3.0
``````
``````julia> using IterTools

julia> using BenchmarkTools

julia> @btime nth(iterated(x->√(6+x),1.0),104475)
505.500 μs (0 allocations: 0 bytes)
3.0

julia> @btime nth(iterated(x->√(6+x),1.0),30)
66.053 ns (0 allocations: 0 bytes)
3.0
``````
1 Like

Why not?

If anything it’ll be `@tailcall`:

1 Like

There have been numerous discussions on this topic in the past. See for example this one and the references therein:

The following thread is also very interesting IMO, in that it discusses the topic from a different point-of-view:

1 Like