# Tail recursion but stack runs out

**URL:** <https://swi-prolog.discourse.group/t/tail-recursion-but-stack-runs-out/6361>\
**Category:** General\
**Created:** [March 11, 2023, 9:32pm UTC](https://swi-prolog.discourse.group/t/tail-recursion-but-stack-runs-out/6361 "2023-03-11T21:32:28Z")\
**Posts on this page:** 1\
**Showing post:** 5

<div class="post-metadata">

**Author:** ![Boris](https://yyz2.discourse-cdn.com/free1/user_avatar/swi-prolog.discourse.group/boris/32/7486_2.png) [@Boris](https://swi-prolog.discourse.group/u/Boris)\
**Post date:** [March 12, 2023, 1:16pm UTC](https://swi-prolog.discourse.group/t/tail-recursion-but-stack-runs-out/6361/5 "2023-03-12T13:16:32Z")

</div>

Yes, it is the choice point that prevents tail call optimization and this fills up the stack. I made a test:

```prolog
state(S0) :-
    transition(S0, S1),
    ( S1 rem 1_000_000 =:= 0
    -> prolog_current_frame(Frame),
        format(user_error, "step ~d frame ~d~n", [S1, Frame])
    ; true
    ),
    state(S1).

transition(S0, S1) :-
    ( S1 is S0 + 1
    ; fail
    ).

```

I used here the same instrumentation as described in [this thread](https://swi-prolog.discourse.group/t/is-this-doing-tco-and-if-so-how/2396) to see if tail recursion optimization is actually happening: if the recursive calls are in the same “frame”, then the optimization was in fact done.

Sorry about using printing instead of the debugger… just easier to share the result:

```prolog
?- state(1).
step 1000000 frame 31000112
step 2000000 frame 62000112
step 3000000 frame 93000112
ERROR: Stack limit (1.0Gb) exceeded
ERROR: Stack sizes: local: 0.8Gb, global: 0.1Gb, trail: 27.9Mb
ERROR: Stack depth: 3,659,450, last-call: 0%, Choice points: 3,659,442
ERROR: Possible non-terminating recursion:
ERROR: [3,659,448] user:state(3659439)
ERROR: [3,659,447] user:state(3659438)

```

If you now remove the `; fail` from there, it will go on forever:

```prolog
state(S0) :-
    transition(S0, S1),
    ( S1 rem 1_000_000 =:= 0
    -> prolog_current_frame(Frame),
        format(user_error, "step ~d frame ~d~n", [S1, Frame])
    ; true
    ),
    state(S1).

transition(S0, S1) :-
    ( S1 is S0 + 1
    %; fail
    ).

```

You should run it, it goes much faster, too:

```prolog
?- state(1).
step 1000000 frame 174
step 2000000 frame 174
step 3000000 frame 174
step 4000000 frame 174
step 5000000 frame 174
step 6000000 frame 174
step 7000000 frame 174
step 8000000 frame 174
step 9000000 frame 174
step 10000000 frame 174
step 11000000 frame 174
step 12000000 frame 174
^CAction (h for help) ? abort
% Execution Aborted

```

---

_[View the full topic](https://swi-prolog.discourse.group/t/tail-recursion-but-stack-runs-out/6361)._