# How to call a recursive function without stackoverflow?

**URL:** <https://discourse.julialang.org/t/how-to-call-a-recursive-function-without-stackoverflow/95865>\
**Category:** New to Julia\
**Tags:** compilation, recursion\
**Created:** [March 10, 2023, 12:48pm UTC](https://discourse.julialang.org/t/how-to-call-a-recursive-function-without-stackoverflow/95865 "2023-03-10T12:48:00Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![AwesomeQuest](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/awesomequest/32/38910_2.png) [@AwesomeQuest](https://discourse.julialang.org/u/AwesomeQuest)\
**Post date:** [March 10, 2023, 12:48pm UTC](https://discourse.julialang.org/t/how-to-call-a-recursive-function-without-stackoverflow/95865/1 "2023-03-10T12:48:00Z")

</div>

When calling

```julia
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?

---

<div class="post-metadata">

**Author:** ![ffevotte](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ffevotte/32/6587_2.png) [@ffevotte](https://discourse.julialang.org/u/ffevotte)\
**Post date:** [March 10, 2023, 1:00pm UTC](https://discourse.julialang.org/t/how-to-call-a-recursive-function-without-stackoverflow/95865/2 "2023-03-10T13:00:14Z")

</div>

> [@AwesomeQuest](#):
>
> 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](https://en.wikipedia.org/wiki/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
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

```

---

<div class="post-metadata">

**Author:** ![ndinsmore](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ndinsmore/32/7433_2.png) [@ndinsmore](https://discourse.julialang.org/u/ndinsmore)\
**Post date:** [March 10, 2023, 1:02pm UTC](https://discourse.julialang.org/t/how-to-call-a-recursive-function-without-stackoverflow/95865/3 "2023-03-10T13:02:01Z")

</div>

This should do it

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

```

---

<div class="post-metadata">

**Author:** ![Dan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dan/32/42581_2.png) [@Dan](https://discourse.julialang.org/u/Dan)\
**Post date:** [March 10, 2023, 1:35pm UTC](https://discourse.julialang.org/t/how-to-call-a-recursive-function-without-stackoverflow/95865/4 "2023-03-10T13:35:17Z")

</div>

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

```julia
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
julia> @btime foldl(((x,y))->y,Itr.take(iterated(x->√(6+x),1.0),104475))
  698.127 μs (0 allocations: 0 bytes)
3.0

```

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [March 10, 2023, 1:43pm UTC](https://discourse.julialang.org/t/how-to-call-a-recursive-function-without-stackoverflow/95865/5 "2023-03-10T13:43:28Z")

</div>

> [@ffevotte](#):
>
> `res = 1`

Note that you probably want `res = 1.0` for [type stability](https://docs.julialang.org/en/v1/manual/performance-tips/#Avoid-changing-the-type-of-a-variable).

---

<div class="post-metadata">

**Author:** ![AwesomeQuest](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/awesomequest/32/38910_2.png) [@AwesomeQuest](https://discourse.julialang.org/u/AwesomeQuest)\
**Post date:** [March 10, 2023, 2:16pm UTC](https://discourse.julialang.org/t/how-to-call-a-recursive-function-without-stackoverflow/95865/6 "2023-03-10T14:16:04Z")

</div>

Can you explain how this works?

---

<div class="post-metadata">

**Author:** ![Dan](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dan/32/42581_2.png) [@Dan](https://discourse.julialang.org/u/Dan)\
**Post date:** [March 10, 2023, 2:29pm UTC](https://discourse.julialang.org/t/how-to-call-a-recursive-function-without-stackoverflow/95865/7 "2023-03-10T14:29:14Z")

</div>

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
julia> itrlast(itr) = foldl((_,y)->y,itr)

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

```

---

<div class="post-metadata">

**Author:** ![rocco\_sprmnt21](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rocco_sprmnt21/32/20127_2.png) [@rocco\_sprmnt21](https://discourse.julialang.org/u/rocco_sprmnt21)\
**Post date:** [March 10, 2023, 6:32pm UTC](https://discourse.julialang.org/t/how-to-call-a-recursive-function-without-stackoverflow/95865/8 "2023-03-10T18:32:42Z")

</div>

```julia
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

```

---

<div class="post-metadata">

**Author:** ![uniment](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/uniment/32/24532_2.png) [@uniment](https://discourse.julialang.org/u/uniment)\
**Post date:** [March 11, 2023, 2:59am UTC](https://discourse.julialang.org/t/how-to-call-a-recursive-function-without-stackoverflow/95865/9 "2023-03-11T02:59:38Z")

</div>

> [@ffevotte](#):
>
> Julia does not perform automatic [Tail Call](https://en.wikipedia.org/wiki/Tail_call) Optimization.

Why not?

---

<div class="post-metadata">

**Author:** ![jar1](https://avatars.discourse-cdn.com/v4/letter/j/c0e974/32.png) [@jar1](https://discourse.julialang.org/u/jar1)\
**Post date:** [March 11, 2023, 3:06am UTC](https://discourse.julialang.org/t/how-to-call-a-recursive-function-without-stackoverflow/95865/10 "2023-03-11T03:06:31Z")

</div>

If anything it’ll be `@tailcall`:

> <https://github.com/JuliaLang/julia/issues/4964#issuecomment-961932928>
>
> It's interesting that this is valid syntax in Julia and Lua:
> 
> \`\`\` jl
> function re…c()
> return rec()
> end
> \`\`\`
> 
> The difference is that in Lua, when you call \`rec()\` it will stare at you and engage your motherboard's built-in space heater until you ctrl-C out. In Julia:
> 
> \`\`\` jl
> julia\> rec()
> ERROR: stack overflow
> in rec at none:2 (repeats 80000 times)
> \`\`\`
> 
> So the stack 80000 things deep. That's interesting.
> 
> Why does this matter? I'm not sure. But some people care a lot:
> 
> http://www.lua.org/pil/6.3.html

---

<div class="post-metadata">

**Author:** ![ffevotte](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/ffevotte/32/6587_2.png) [@ffevotte](https://discourse.julialang.org/u/ffevotte)\
**Post date:** [March 11, 2023, 5:11pm UTC](https://discourse.julialang.org/t/how-to-call-a-recursive-function-without-stackoverflow/95865/11 "2023-03-11T17:11:41Z")

</div>

> [@uniment](#):
>
> Why not?

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

> [@Does Julia have tail call optimization?](https://discourse.julialang.org/t/does-julia-have-tail-call-optimization/64101):
>
> does Julia have tail call optimization ? or does a recursive function always overflow regardless of if you are careful to construct it in that fashion ?

  

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

> [@Tail-call optimization and function-barrier -based accumulation in loops](https://discourse.julialang.org/t/tail-call-optimization-and-function-barrier-based-accumulation-in-loops/25831/1):
>
> Tail-call optimization/elimination was brought up in several threads like [this one in discourse](https://discourse.julialang.org/t/recursive-call-vs-while-loop/7723) and [this one in GitHub](https://github.com/JuliaLang/julia/issues/4964). The main interest seems to be purely based on the nice-to-have performance benefit and the core devs seem to be open to the change while assigning very low priority because writing for/while-loop is more idiomatic in Julia. But I think there is another point of view related to function-barrier -based accumulation which makes me wonder if the tail-call optimization actually mak…