How to call a recursive function without stackoverflow?

New to Julia
,
1

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:
 [1] <
   @ .\REPL[76]:1 [inlined]
 [2] >
   @ .\operators.jl:382 [inlined]
 [3] f(x::Int64) (repeats 79984 times)
   @ Main .\REPL[76]: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?

2

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
3

This should do it

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

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
5

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

1 Like
6

Can you explain how this works?

7

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
8 
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
9

Why not?

10

If anything it’ll be @tailcall:

1 Like
11

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