Repeat expression [n] times? A Recursive Experiment

As @TW_Tones pointed out, there are plenty of ways to do loops. But you can also use recursion to solve such problems. Recursion is generally easy to use in TW. Your problem is too general, but I will demonstrate how to solve another one, which should give you some ideas.

Here we look at a mathematical recursion, calculating the Collatz sequence from a starting number.1 The Collatz Conjecture says that a sequence of integers, where the next one is found by following the following rule, always eventually reaches 1:

9b2a03faf9d31a8de0abb3c4a3d318490105da12

For instance, if we start with 3, it’s odd, so we multiply by three and add one, giving 10. This is even, so we divide by two, giving 5. This is odd, and 3 * 5 + 1 gives 16, then we keep dividing by two, giving 8, then 4, then 2, then 1.

3 → 10 → 5 → 16 → 8 → 4 → 2 → 1

As obscure as this problem sounds, it’s quite famous. Finding the sequence for a starting number is a good example of a recursive problem.

We can convert the math pretty easily to wikitext, especially with the introduction of the Conditional Shortcut Syntax. Here’s my version:

\procedure collatz(n) 
<% if [<n>match[1]] %>
  1
<% elseif [<n>remainder[2]match[1]] %>
  <<n>> → <$transclude $variable="collatz" n = {{{ [<n>multiply[3]add[1]] }}}/>
<% else %>
  <<n>> → <$transclude $variable="collatz" n = {{{ [<n>divide[2]] }}}/>
<% endif %>
\end

With this, <<collatz 3>> yields 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1, <collatz 1>> yields 1, and <<collatz 27>> yields a string of 111 integers, going as high as 9232 before eventually reaching 1.

We have a base case, when n is 1, and when it’s not, we recur on 3n + 1 if n is odd, and on n / 2 if n is even, recursively calling our collatz procedure on the resulting value.

collatz.json (524 Bytes)


1 So, I’m a math geek, so what?

2 Likes

@jeremyruston
hmmm, For stuff like this we should allow to widen the limit of the “recursion protection” in the core – somehow.

I think for most realistic cases of recursion in TW, that’s not likely necessary. I don’t know the limit here. I don’t know if we’d want a special case for things like this. My guess is that if you’re going to do significant calculations in your wiki, you’d probably descend to JS for them.

1 Like

Perhaps an approach I have suggested earlier. A widget to wrap a section on which you can set a timeout.

That could be very useful for effects that occur in some recursive manner, even simple animations.

It wouldn’t be very fun to use for calculations like the above, though.

Brilliant! I love stuff like this that deals with the pragmatics of TW coding whilst having a great purpose.

I am not a maths geek. But I am aware of the Collatz Conjecture. It is fascinating to see a TW approach to it!

What starting number (i.e. with v. high resulting numbers and steps) might test a TW to see if it could survive?

That seems interesting to investigate on recursion in general in TW?

Best wishes
TT

837799 gave me a recursive transclusion error:

(I haven’t yet tested to see whether it works better if I clear the browser’s memory-decks first.)

1 Like

It would definitely be the number of steps that matter. We’ll run out of recursion space long before hitting limits on the JS number type.

Yeah, it happens earlier too. I’m assuming you got this choice from the information about longest stopping times, which Wikipedia reports as

The starting value having the largest total stopping time while being

less than 10 is 9, which has 19 steps,
less than 100 is 97, which has 118 steps,
less than 1000 is 871, which has 178 steps,
less than 104 is 6171, which has 261 steps,
less than 105 is 77031, which has 350 steps,
less than 106 is 837799, which has 524 steps,
less than 107 is 8400511, which has 685 steps,
…

But it also fails for 77031 and 6171. It works for 871. I ran a loop and the first failure is at 6171, where a recursion depth of 220 seems to be the hard limit.

It shouldn’t matter. These are not taking large amounts of memory; instead they’re running into recursion depth limits imposed by TW. I don’t know if 220 is the hard-coded limit, or it it’s more like 250, but some of that is taken by other overhead of displaying this tiddler. The built-in JS limits are substantially higher. The JS Engine on my work Chrome box easily handles collatz(989345275647), which has 1349 steps. Modern engines will have depth of at least 10,000.

1 Like

Right.

/* Maximum permitted depth of the widget tree for recursion detection */
var MAX_WIDGET_TREE_DEPTH = 1000;

/*

(in $:/core/modules/widgets/widget.js )

2 Likes

Then I assume that each level of this collatz call uses multiple widgets. Perhaps its the <% if %> and friends.

1 Like

The MAX_WIDGET_TREE_DEPTH is set to 1000, where the TW UI for some elements may use up to 150 or so. If users mess up templates the limit 1000 seems to be too high. It can “brick” the UI for quite some time. So we did discuss to lower the limit.

@jeremyruston

For recursions that are well defined, like the example here, the limit seems to be to low. It may be possible to define a tv-max-widget-tree-depth variable that can overwrite the hardcoded limit.

just some thoughts.

Right!

That was my thought when looking at @Scott_Sauyet’s interesting example.
Is there a way to let such cases run more freely?

This is fascinating. I have no objection to such a change, but it’s so far afield from why I brought this up. I simply wanted to point out that we could use recursion as well as iteration within TW. I didn’t want to continue the overuse of factorial or fibonacci for recursion discussions, and this was the first reasonably simple one I came up with.

For the record, I have no interest at all in using TW to do even slightly complicated mathematical calculations. I have much better tools for that. But Collatz was an easy-to-grasp function useful for demonstrating recursion.

I think that if this is worth doing, then the rationale should not be something like Collatz.

2 Likes

Interesting discussion. I am moving home today so unlikely to get into the details. However from my perspective I would hope for more transparency and where posible control to set or override global and or local limits perhaps via tv-variables.

TiddlywIki is a great platform for innovation and you dont know where innovation will take you. The idea of hard and inflexible limits are as unhelpful, as no limits on the firsts place.

I see also value in interesting mathematical sequences to use on exploring or generating data.

None of this is rocket science and is I belive solvable although only a few in our community may have the skills to execute this.

1 Like

Wow, really wow :sweat_smile:
I’m not a math geek and I never heard of the Collatz Conjecture, neither.

But it shows me very well how recursion can be used in TiddlyWiki.
Thank you for your very interesting reply!

Animations? Sounds interesting to me.
But I’m afraid that such widgets (with timeouts) could burden the browser too much?
Especially if more of them are being used.

Well good, for that was the only reason for the comment. The subsequent discussion was interesting, but somewhat beside the point.

Tiddlywiki includes some short-running animations, and they seem smooth in modern browsers. The only reason for discussing them here is that its one of the few useful reasons I’ve ever seen for setTimeout based recursions, and those were superseded years ago by better animation techniques. (I’m exaggerating a bit; there are other uses, as for an endless cycle that still allows for other parts of the code to interrupt; but they’re rare.)

The lowercase Operator has a last modified time nearly five years old, so I don’t think this is a new style.

1 Like

It was a spin-off, but nevertheless very interesting - even for a non-math geek like me. Sometimes I wish that I was more interested in mathematics, but I never found a good reason for that. It seems to be like based on some traumatic experience, dating back to my school days :grimacing:. But that’s another story.

Where did I stop? Ah yes, thank you for giving me a pretty good example for recursion.

I’ve heard of throttle.refresh before, but I’m not aware of other possibilities using Timeouts in TW as a user? Timeouts are used by the core, mostly preventing TW to become unusable due to some misconfiguration/code on the user’s behalf. Or at least it is what I’m thinking about how it should be.

Oh my, you are right. I overlooked this, thank you for pointing this out.
Must be a reason because the documentation is written by more persons, not a single one, depending of the personal style of the writer.
I like the crossreferences which helped me a lot back in the days learning other programming languages by studying the keywords in the manual - a good example is Turbo Pascal, which had an excellent online help. There were cross references, I believe, too.
Sorry if I should remember wrong, which could be the case because I didn’t use Turbo Pascal over decades.

I would really appreciate seeing a similar style in TiddlyWiki documentation.
Or am I the only one with such preferences?

Returning to this with a fresh perspective, I realised the way we use filters we tend to be guaranteed, that a recursive or iterative process will end, because a filter tends to generate a finite number of results (even if very large). Whilst this is an advantage in many cases, it is not always an advantage, as discussed in this thread.

In various procedural languages you need to use a while/when/repeat until etc… for this and you have to code the condition needed to exit a loop. This is where people can go wrong, by failing to create the appropriate exit condition. This is not a common problem in TiddlyWiki because of the above.

  • However, This has the advantage, that you can often set more than one exit condition, including one when a simple counter exceeds a preset number. In a recursive process you can even store a count of recursion depth, and exist after an arbitrary number.
  • This is not a timeout, but an alternate exit condition.
  • It will break out of the “loop”, stop processing the “titles” and end as if there was not more titles.

Perhaps if we could improve something as important as the $list widget, or provide a similar widget, to permit such a conditional forced exit of a list, give an “alternate” exit condition filter, it would be possible for designers to put it into lists that may run off too long?

As we already have the counter variable, consider if we could set in the list widget parameters an exit condition filter, such as if we use the attribute value pair “counter=item”;

  • exit-condition="[<item>compare:number:gt[100000]]"
    • Then if the number of items generated by the filter were really large ie > 100,000. Then the remainder of items will be ignored, and the list[ing] will stop.
  • We can also allow the user to also provide an optional exit-message, to indicate when the exist condition was true, perhaps even allow a trigger?
    • This is similar to the emptyMessage condition but when a second filter is true, rather than no entries.
  • For a recursive process, where one macro (containing a list) calls itself, we could count a depth variable and use that in the exist condition
    • Eg; exit-condition="[<depth>compare:number:gt[100]]
    • But can we find a way to exit all levels? I expect you can in JavaScript.

What do you think @pmario @jeremyruston etc… ?

I am no coder. No expert on loops.

BUT, in TW, it does seem that even “IN the loop” you can set whatever conditions you want. For instance the Collatz (above) could be run a long time with pauses? Also the “recommencement number” could be established after, say, 100 loops—so that, in TW, it freshly restarts the loop at that number (retaining the loop-count)? So that potential infinity is postponed?

That is a bit different from needing an external “supervisor” to ensure you don’t explode?

Just a (slightly esoteric) comment.
TT