# How do I solve a problem where sometimes recursion is untenably vast and sometimes it is not?

I am writing a programming language of my own. (I've done two Turing complete ones in the past, but this time I'm trying to actually be useful.)

Now, one thing that should be especially easy with this is interactive fiction.

"Three criminals approach you and accuse you of being a detective (which of course you are).  What do you do?"

Choice A (pull your weapon)
Choice B (accuse someone else)
Chioce C (flee)


Right now, I'm just executing choices that the player makes. However, I was thinking of translating my script to Java so you can play this on a website. My approach was going to be recursion.. just execute A, execute all the choices after that until you run out of choices and go to B. Essentially generate a tree. For this kind of a problem, this looks like it would work great. You are just transcribing the problem into

However, this exposes the language to certain ways of solving problems that might lead to more recursion than could have been computed since the start of the known universe. Easily. For example, chess.

I have a subroutine askMultiple(...) that would offer the player a series of choices. This is where the recursion would take place; every time a choice leads to more choices, just go down the tree.

Now, this would be an unwieldy way to ask for choices on a chess board (its a long list of moves.) But it would be quite logically possible, and maybe less unwieldy than you might think since the language supports custom output modules.

Now if I use the same approach to this problem I would on the detective game, my program would puke. There are 10^120 chess games. Countless lifetimes would be long over by the time your incomprehensibly vast javascript page was done.

It's easy to handle infinite numbers of input in a finite space (what is your name?). For example

Hi, detective Ashley,
Hi, detective Morris...


but I know that this approach might generate problems.

How can I avoid this?

• "I was thinking of translating my script to Java so you can play this on a website." - do you mean JavaScript? This is a different language from Java. But more fundamentally: why would you ever need to recurse more than one level down the tree at a time? "What are all possible future board states that could arise in Chess" is something like $10^{120}$, but "What choices can I make for the next move from this current board state" is more like 35 on average. Then you wait for the player to make a choice, and only then do you search the ~35 choices resulting from that one. What am I missing? Jun 5, 2021 at 15:25

Why do you need recursion for a dialog tree?

In the dialog system of my current project, each dialog tree is an array of nodes. I then have an integer which represents the index of the currently active dialog node.

When the player picks a choice, I just do currentNodeId = nodes[currentNodeId].choices[pickedChoiceIndex].nextId and that's it. No recursion whatsoever.

Need to remember a choice later? That's what variables are for. Nodes can change the value of variables. Those variables can later be used to hide or show conditional choices or create invisible branches between two or more nodes. That gives me a Turing-complete system without requiring any stack-based recursion whatsoever. Oh, and I also have a syntax which allows to embed conditional text within text nodes which is {character.loyalty>=50|shown|hidden} depending on the value of a variable. A useful shortcut for small details which don't warrant a whole branch.

If I wanted to implement a turn-based game like Chess to be played through this system, then I would also use variables for that. I would not create a separate node for each possible state of the game board. I would encode the state of the game using variables and then present that state and the choices the player has by using those variables. Although I would likely hard-code the actual mechanics of that game (it would be theoretically possible due to the Turing-completeness of this system, but I am not a masochist).

The only situation where I have recursion is when I am working with sub-trees (dialog nodes which are implemented as complete separate dialog trees - usually used to make them reusable or to break up very large trees into multiple ones for easier editing). But I see no reason why I would ever go deeper than a hand full of levels of recursion with this.

• Well, one of the possible output cases if actually, say, a PDF or postscript file with your game. Not only can you play your game, but you could outright publish it in static format just by coding it once, and simply changing the "output module." In order to generate this static output, the application must have some way of differentiating recursion trees which are navigable and those that are not. I was going to just have two ways of getting input that the human would choose, one would support recursion (finite choices) and one would be geared at arbitrary input. Jun 6, 2021 at 7:07
• @user1833028 "In order to generate this static output, the application must have some way of differentiating recursion trees which are navigable and those that are not" - It seems to me like in order to do that reliable in a turing-complete system, you would need to solve the halting problem. Jun 6, 2021 at 12:17