Parameterised Transclusion: Recursive Functions

, ,
1

TW 5.3.0 introduced functions and they can be used in a recursive manner. I tried to implement the Fibonacci sequence (already impletemted in TW by @Mark_S. See TW-Scripts) using functions as below

\function .step(n) [<n>subtract[1]]:map[.f<currentTiddler>][<n>subtract[2]]:map[.f<currentTiddler>]:and[sum[]]
\function .f(n) [<n>match[0]then[0]] [<n>match[1]then[1]] :else[.step<n>]

<<.f 6>>

But I failed, using large number like 10 makes Tiddlywiki unresponsive!

EDITED

  • The problem solved. See below solution. The issue was with :map. It processes all comming input from previous filter runs. I had to use :map in .step only one time.

  • You can try the above code in TiddlyWiki Pre-release — 5.3.0-prerelease

2

I believe you forgot to paste the code.

3

Thank you Saq! I revised the OP.

4

Any other recursive function example is welcome!

5

I think your code is wrong. The numbers below 1000 are: 0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987

Your <<.f 6>> and <<.f 7>> both show 3 for me. …

Also see my post about recursive macros at: Frustrations of Wikitext from a Software Dev - #15 by pmario

6

The code is correct (I assume :wink: ) It uses below formula

F(0) = 0
F(1) = 1

For n> 1

I think the way recursive function works is the problem or my understanding of recursive function is not correct! ( I assume the latter)
F(n) = F(n-1) + F(n-2)

7

To me recursion is when something calls itself. When it does so with a filter it will call itself N times according to that filter, then each time it is called it will again call itself N times if there are items to be recursed.

  • The TOC is the default examples, recursion typically runs out a full tree.
  • Recursions can become eternal loops if there is an internal self reference, or a logical error that stops each level of the recursion stopping.

I could only get 3 in your example, and some odd behaviour. If it iterates until it finds the fibonaci number it is kind of recursive, but to me its more of an iteration.

8

Right! I said in the OP, I failed to get it work.

9

Here’s a fixed version of the factorial function:

\function .step(n) [<n>subtract[1]] :map[.f<currentTiddler>multiply<n>]
\function .f(n) [<n>match[0]then[0]] [<n>match[1]then[1]] :else[.step<n>]

<<.f 8>>
10

Hi @jeremyruston
Thank you!

factorial(n) = factorial(n-1) * n

Lovely, it is simple and efficient!

11

This is the working version. I modified the original post. The math behind this solution is fibo(n) = fibo(n-1) + fibo(n-2). You can make your function global (put in a tiddler tagged with $:/tags/Macro) to get access to them in any tiddler you like.

\function .step(n) [<n>subtract[1]] [<n>subtract[2]]  :map[.fibo<currentTiddler>]  :and[sum[]]
\function .fibo(n:0) [<n>match[0]then[0]] [<n>match[1]then[1]] :else[.step<n>]

Example i

<<.fibo 10>>

produces: 55

Example ii

<$text text={{{ [range[0,20]] :map[.fibo<currentTiddler>] :and[join[, ]] }}} />

produces

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765

Thank you @jeremyruston. TW 5.3.0 is just amazing :wink:

NOTE: The above solution runs the function for every number is given like <<.fibo n>>. A better solution is to keep intermediate numbers and generate the sequence from f(0) to f(n)

12

Thank you @pmario. I replied here: Frustrations of Wikitext from a Software Dev - #40 by Mohammad. It seems recursive function can reproduce your macro solution.

Note
Another solution to Fibonacci sequence based on @pmario code is given in the above link.

13

Thanks @Mohammad and @jeremyruston with these helpful examples with the new functions. I have added to my library.

  • I am still learning

Of course as we and the community start to get familiar, I try to predict how best to code, to increase readability and understanding. In this case I would think for occasional use it may be better not to use abbreviations like fibo but use the full Fibonacci but then also realised we can also define a macro;

\function .step(n) [<n>subtract[1]] [<n>subtract[2]]  :map[.fibonacci<currentTiddler>]  :and[sum[]]
\function .fibonacci(n:0) [<n>match[0]then[0]] [<n>match[1]then[1]] :else[.step<n>]
\define fibonacci(n:0) <<.fibo $n$>>

<<fibonacci 10>>
  • Thus we make available the forms <<fibonacci N>>, [function[.fibonacci],[n]....] and [.fibonacci[n]]
  • By using this form we need not use the leading “.” however we can;

Directly invoke functions whose names start with a period as custom filter operators with the syntax [.fibonacci[n]]

Other

  • Or perhaps we use a procedure?
  • Maybe we generalise the step function .step(n ".functionname")

What are your thoughts?