cancel
Showing results for 
Search instead for 
Did you mean: 
cancel
Showing results for 
Search instead for 
Did you mean: 

Community Tip - Did you know you can set a signature that will be added to all your posts? Set it here! X

Feature Request: Mutual Recursion

StuartBruff
23-Emerald III

Feature Request: Mutual Recursion

Several classes of problem (eg, context-free grammar interpreters) are easily thought about and implemented by mutually recursive function calls,

For example, one of the Rosetta Code programming challenges is to implement the Hofstadter Female and Male Sequences (http://rosettacode.org/wiki/Mutual_recursion#PureBasic).  As far as I'm aware, this isn't possible in Mathcad, but appears to be in a whole host of other languages including Matlab and Mathematica (two of Mathcad's major competitors).   As the ultimate humilation, I wrote my first program in LibreOffice Basic to show that even a word processor can do mutual recursion whereas a mathematical application can't.  Indeed, it seems as if even a pocket calculator can do it (see Ti-89 entry in the Rosetta listing).

Stuart

Rosetta Code Hofstadter Female and Male Sequence Challenge


Two functions are said to be mutually recursive if the first calls the second, and in turn the second calls the first.


Write two mutually recursive functions that compute members of the Hofstadter Female and Male sequences defined as:


F(0) = 1 ; M(0)=0

F(n) = n - M(F(n-1)), n > 0

M(n) = n - F(M(n-1)), n > 0

 

n    = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

F(n) = 1 1 2 2 3 3 4 5 5 6  6  7  8  8  9  9 10 11 11 12 13

M(n) = 0 0 1 2 2 3 4 4 5 6  6  7  7  8  9  9 10 11 11 12 12


LibreOffice Basic Function Definitions:

Function F(n as long) as long

    If n = 0 Then

        F =  1

    ElseIf n > 0 Then

        F = n - M(F(n - 1))

    EndIf

End Function

Function M(n)

    If n = 0 Then

        M = 0

    ElseIf n > 0 Then

        M = n - F(M(n - 1))

    EndIf

End Function

ACCEPTED SOLUTION

Accepted Solutions
RichardJ
19-Tanzanite
(To:StuartBruff)

If there's a way of "tricking" Mathcad into being able to do this, I can't figure it out. It just fundamentally breaks Mathcad's top left to bottom right paradigm.

As for the "feature request" aspect of your post, I think the best we can hope for is that 20 years from now we can complain that is still hasn't been implemented. Like MDAs, etc etc etc.

View solution in original post

12 REPLIES 12
RichardJ
19-Tanzanite
(To:StuartBruff)

If there's a way of "tricking" Mathcad into being able to do this, I can't figure it out. It just fundamentally breaks Mathcad's top left to bottom right paradigm.

As for the "feature request" aspect of your post, I think the best we can hope for is that 20 years from now we can complain that is still hasn't been implemented. Like MDAs, etc etc etc.

StuartBruff
23-Emerald III
(To:RichardJ)

Richard Jackson wrote:

If there's a way of "tricking" Mathcad into being able to do this, I can't figure it out. It just fundamentally breaks Mathcad's top left to bottom right paradigm.

I was hoping that there'd be some way of playing around with the symbolic processor, but I haven't found a way either.    I've tried code fragments and even defining F via a global definition and M as normal definition.  Helpfully, the latter raised an error that said "recursive definition"; that's just plain cruel and I think I ought to be instructing my lawyers.  If you can't do, sue!

I did think about mutual recursion breaking the normal evaluation, but we already have a mechanism that subverts it  - the above-mentioned global definition, so that might be one means by which Mathcad could 'legally' implement double mutual recursion.  Another way might be to introduce a keyword (eg, "forward" a la Pascal) that would flag up mutual recursion during the first pass.  Following the principle of maximum laziness, however, I'd rather see a mechanism that doesn't require additional thought upon my part.  I'll have to have a think about how it might break normal order otherwise and to what degree that would be a problem, or a benefit.

It would be nice to find a means by which we could legimately have closures, deferred evaluation and memoization (rather than the special case closure mechanism I found for creating functions with (vector) memory and that is almost certainly a bug an unintended feature).

As for the "feature request" aspect of your post, I think the best we can hope for is that 20 years from now we can complain that is still hasn't been implemented. Like MDAs, etc etc etc.

I guess I'm going to have to mark your answer correct ...  not sure whether that requires a emoticon, just out of plain snarkiness, or a because you're right.

Stuart

StuartBruff
23-Emerald III
(To:StuartBruff)

StuartBruff wrote:

Richard Jackson wrote:

If there's a way of "tricking" Mathcad into being able to do this, I can't figure it out. It just fundamentally breaks Mathcad's top left to bottom right paradigm.

I'll have to have a think ...

I shall have to give up this thinking lark.  No sooner had I put the keyboard down on you, than I wondered if I'd missed a trick in my previous attempt to use local definitions.  If one is willing to live with the burden of defining one function twice (ie, locally and at worksheet level), then it might be possible to trick Mathcad into allowing mutual recursion.

Stuart

StuartBruff
23-Emerald III
(To:StuartBruff)

StuartBruff wrote:

If one is willing to live with the burden of defining one function twice (ie, locally and at worksheet level), then it might be possible to trick Mathcad into allowing mutual recursion.

This approach in no way abrogates the feature request, as it is clearly a workaround.

Stuart

Werner_E
25-Diamond I
(To:StuartBruff)

Just dropped by after a long time and to be honest it was more by accident than on purpose as I very much dislike the new cumbersome forum design and the way everything gets worse when PTC put their hand on it.

Nevertheless the subject intrigued me and encouraged me to work on a solution. So here is what I came up with. It does not require to define a function twice and may be easily extended to more than two functions. At least if all of them have the same number of arguments (otherwise we would have to resort to providing the arguments via a vector).

Nevertheless its still just an awkward workaround for something we should be able to do in a much more natural way.

Regards

Werner

P.S.: The last function defined locally (here F(n)) could use all the locally defined previous functions so we could simply write "n-M(F(n-1)) if n>0" in the otherwise section of F(n). Similarly M(n) may of course call itself:

StuartBruff
23-Emerald III
(To:Werner_E)

Werner Exinger wrote:

Just dropped by after a long time and to be honest it was more by accident than on purpose as I very much dislike the new cumbersome forum design and the way everything gets worse when PTC put their hand on it.

Nevertheless the subject intrigued me and encouraged me to work on a solution. So here is what I came up with. It does not require to define a function twice and may be easily extended to more than two functions. At least if all of them have the same number of arguments (otherwise we would have to resort to providing the arguments via a vector).

Nevertheless its still just an awkward workaround for something we should be able to do in a much more natural way.

Regards

Werner

P.S.: The last function defined locally (here F(n)) could use all the locally defined previous functions so we could simply write "n-M(F(n-1)) if n>0" in the otherwise section of F(n). Similarly M(n) may of course call itself:

Nice to see you around again, Werner.  Please have more accidents! 😉

A neat solution.  I'd just been playing around with different forms of substitution but I don't think I'd have improved on your method in the slightest.  As you say, it extends to the multiple mutual recursion case quite readily.  I used Stoll's Parent-Child extension to the Female-Male sequence.  One other aspect of your solution is that, because it is effectively a single function with different cases, there is no need to define the local functions at all; the function programs can be used directly in the if-otherwise statements (although I think it improves readability to use local functions).  I've made an attempt to simplify the expressions by defining auxiliary functions a,b,c that are simply curried versions of abc (the Parent-Child equivalent of the Female-Male FM).  This, to my eyes at least, makes it look more natural.

Stuart

StuartBruff
23-Emerald III
(To:StuartBruff)

And checked with the original FM problem ...

Werner_E
25-Diamond I
(To:StuartBruff)

I've made an attempt to simplify the expressions by defining auxiliary functions a,b,c that are simply curried versions of abc (the Parent-Child equivalent of the Female-Male FM).  This, to my eyes at least, makes it look more natural.

I tend to agree - nice touch.

I haven't used Prime for quite some time and not that I would care, but as far as I remember, a definition like c<--abc("c") will not work in Prime.

WE

StuartBruff
23-Emerald III
(To:Werner_E)

Werner Exinger wrote:

I've made an attempt to simplify the expressions by defining auxiliary functions a,b,c that are simply curried versions of abc (the Parent-Child equivalent of the Female-Male FM).  This, to my eyes at least, makes it look more natural.

I tend to agree - nice touch.

I haven't used Prime for quite some time and not that I would care, but as far as I remember, a definition like c<--abc("c") will not work in Prime.

WE

Why is it that everytime I think "Ooh! That's interesting.  I'm sure I can do something with that ....", PTC (or Mathsoft as was) take it away?   I remember during the development of M12 that they actually got recursion right (or better anyway) and then changed it because of complaints that it would break a couple of functions.   Which is ironic, because the static type checking broke more things and necessitated far more work than fixing the recursion problem would have done.

Anyway, it shouldn't be a problem because  c(n)<-abc("c",n) should still work.

Stuart

StuartBruff
23-Emerald III
(To:Werner_E)

Werner Exinger wrote:

I haven't used Prime for quite some time and not that I would care, but as far as I remember, a definition like c<--abc("c") will not work in Prime.

You're right; partial function application no longer works. 😞

However, my workaround for it does (as one would expect).

The If-Elseif-Else structure is very good at taking up vertical space on the worksheet.  I find it harder to make sense of such extended programs, so I used if functions instead of if statements.

There's another form that's amenable to your method, and that is to use a generic function.

Stuart

tietjee
15-Moonstone
(To:StuartBruff)

Nice little challenge.  F(0) through F(n-1) have to know to calculate F(n), same with M(n).  M(n) can be calculated before F(n), provided F(0) through F(n-1) are known.  See attached code and check my logic.

HofstadterChallenge.jpg

Cheers

StuartBruff
23-Emerald III
(To:tietjee)

David Tietje wrote:

Nice little challenge.  F(0) through F(n-1) have to know to calculate F(n), same with M(n).  M(n) can be calculated before F(n), provided F(0) through F(n-1) are known. 

HofstadterChallenge.jpg

Cheers

It seems to work ... see attached worksheet.

See attached code and check my logic.

I tried to but now

Stuart

Announcements

Top Tags