Mutual recursion: Difference between revisions
Content added Content deleted
(added Elixir) |
m (→{{header|REXX}}: used clear version of parse (for arg), broke some long line up, added whitespace.) |
||
Line 1,730: | Line 1,730: | ||
This version uses vertical formatting. |
This version uses vertical formatting. |
||
<lang rexx>/*REXX program shows mutual recursion (via Hofstadter Male & Female seq)*/ |
<lang rexx>/*REXX program shows mutual recursion (via Hofstadter Male & Female seq)*/ |
||
arg lim .; if lim |
parse arg lim .; if lim='' then lim=40; pad=left('',20) |
||
do j=0 to lim; |
do j=0 to lim; jj=Jw(j); ff=F(j); mm=M(j) |
||
say pad |
say pad 'F('jj") =" Jw(ff) pad 'M('jj") =" Jw(mm) |
||
end /*j*/ |
end /*j*/ |
||
exit /*stick a fork in it, we're done.*/ |
exit /*stick a fork in it, we're done.*/ |
||
/*─────────────────────────────────────F, M, Jw subroutines────────────*/ |
/*─────────────────────────────────────F, M, Jw subroutines────────────*/ |
||
F: procedure; arg n; if n==0 then return 1; return n-M(F(n-1)) |
F: procedure; parse arg n; if n==0 then return 1; return n-M(F(n-1)) |
||
M: procedure; arg n; if n==0 then return 0; return n-F(M(n-1)) |
M: procedure; parse arg n; if n==0 then return 0; return n-F(M(n-1)) |
||
Jw: return right(arg(1),length(lim)) /*right justifies # for nice look*/ |
Jw: return right(arg(1),length(lim)) /*right justifies # for nice look*/ |
||
</lang> |
|||
'''output''' (using the default of 40): |
'''output''' (using the default of 40): |
||
<pre style="height:30ex |
<pre style="height:30ex"> |
||
F( 0) = 1 M( 0) = 0 |
F( 0) = 1 M( 0) = 0 |
||
F( 1) = 1 M( 1) = 0 |
F( 1) = 1 M( 1) = 0 |
||
Line 1,788: | Line 1,789: | ||
<br><br>The optimization due to memoization is faster by many orders of magnitude. |
<br><br>The optimization due to memoization is faster by many orders of magnitude. |
||
<lang rexx>/*REXX program shows mutual recursion (via Hofstadter Male & Female seq)*/ |
<lang rexx>/*REXX program shows mutual recursion (via Hofstadter Male & Female seq)*/ |
||
arg lim .;if lim=='' then lim=99 |
parse arg lim .; if lim=='' then lim=99 /*get or assume LIM.*/ |
||
hm.=; hm.0=0; hf.=; hf.0=1; Js=; Fs=; Ms= |
|||
do j=0 to lim; |
do j=0 to lim; ff=F(j); mm=M(j) |
||
Js=Js jW(j); Fs=Fs jw(ff); Ms=Ms jW(mm) |
|||
end /*j*/ |
end /*j*/ |
||
say 'Js=' Js |
say 'Js=' Js |
||
say 'Fs=' Fs |
say 'Fs=' Fs |
||
say 'Ms=' Ms |
say 'Ms=' Ms |
||
exit /*stick a fork in it, we're done.*/ |
exit /*stick a fork in it, we're done.*/ |
||
/*──────────────────────────────────one─liner subroutines──────────────────────────────*/ |
|||
/*─────────────────────────────────────F, M, Jw subroutines────────────*/ |
|||
F: procedure expose hm. hf.; arg n; if hf.n=='' then hf.n=n-M(F(n-1)); return hf.n |
F: procedure expose hm. hf.; parse arg n; if hf.n=='' then hf.n=n-M(F(n-1)); return hf.n |
||
M: procedure expose hm. hf.; arg n; if hm.n=='' then hm.n=n-F(M(n-1)); return hm.n |
M: procedure expose hm. hf.; parse arg n; if hm.n=='' then hm.n=n-F(M(n-1)); return hm.n |
||
Jw: return right(arg(1),length(lim)) |
Jw: return right(arg(1),length(lim)) /*right justifies # for nice look*/</lang> |
||
'''output''' (using the default of 99): |
'''output''' (using the default of 99): |
||
<pre> |
|||
<pre style="overflow:scroll"> |
|||
Js= 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
Js= 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
||
Fs= 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 13 13 14 14 15 16 16 17 17 18 19 19 20 21 21 22 22 23 24 24 25 25 26 27 27 28 29 29 30 30 31 32 32 33 34 34 35 35 36 37 37 38 38 39 40 40 41 42 42 43 43 44 45 45 46 46 47 48 48 49 50 50 51 51 52 53 53 54 55 55 56 56 57 58 58 59 59 60 61 61 |
Fs= 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 13 13 14 14 15 16 16 17 17 18 19 19 20 21 21 22 22 23 24 24 25 25 26 27 27 28 29 29 30 30 31 32 32 33 34 34 35 35 36 37 37 38 38 39 40 40 41 42 42 43 43 44 45 45 46 46 47 48 48 49 50 50 51 51 52 53 53 54 55 55 56 56 57 58 58 59 59 60 61 61 |
||
Line 1,814: | Line 1,816: | ||
/*If LIM is negative, only show a single result for the abs(lim) entry.*/ |
/*If LIM is negative, only show a single result for the abs(lim) entry.*/ |
||
parse arg lim .; |
parse arg lim .; if lim=='' then lim=99; aLim=abs(lim) |
||
parse var lim . hm. hf. Js Fs Ms; hm.0=0; hf.0=1 |
parse var lim . hm. hf. Js Fs Ms; hm.0=0; hf.0=1 |
||
do j=0 to Alim; |
do j=0 to Alim; ff=F(j); mm=M(j) |
||
Js=Js jW(j); Fs=Fs jw(ff); Ms=Ms jW(mm) |
|||
end |
end |
||
if lim>0 then say 'Js=' Js; else say 'J('aLim")=" word(Js,aLim+1) |
if lim>0 then say 'Js=' Js; else say 'J('aLim")=" word(Js,aLim+1) |
||
Line 1,825: | Line 1,827: | ||
if lim>0 then say 'Ms=' Ms; else say 'M('aLim")=" word(Ms,aLim+1) |
if lim>0 then say 'Ms=' Ms; else say 'M('aLim")=" word(Ms,aLim+1) |
||
exit /*stick a fork in it, we're done.*/ |
exit /*stick a fork in it, we're done.*/ |
||
/*──────────────────────────────────one─liner subroutines──────────────────────────────*/ |
|||
/*─────────────────────────────────────F, M, Jw subroutines────────────*/ |
|||
F: procedure expose hm. hf.; arg n; if hf.n=='' then hf.n=n-M(F(n-1)); return hf.n |
F: procedure expose hm. hf.; parse arg n; if hf.n=='' then hf.n=n-M(F(n-1)); return hf.n |
||
M: procedure expose hm. hf.; arg n; if hm.n=='' then hm.n=n-F(M(n-1)); return hm.n |
M: procedure expose hm. hf.; parse arg n; if hm.n=='' then hm.n=n-F(M(n-1)); return hm.n |
||
Jw: return right(arg(1),length(lim)) |
Jw: return right(arg(1),length(lim)) /*right justifies # for nice look*/</lang> |
||
'''output''' using the input of: <tt> -70000 </tt> |
'''output''' using the input of: <tt> -70000 </tt> |
||
<pre> |
|||
<pre style="overflow:scroll"> |
|||
J(70000)= 70000 |
J(70000)= 70000 |
||
F(70000)= 43262 |
F(70000)= 43262 |
||
Line 1,836: | Line 1,838: | ||
</pre> |
</pre> |
||
'''output''' using the input of a ¼ million: <tt> -250000 </tt> |
'''output''' using the input of a ¼ million: <tt> -250000 </tt> |
||
<pre> |
|||
<pre style="overflow:scroll"> |
|||
J(250000)= 250000 |
J(250000)= 250000 |
||
F(250000)= 154509 |
F(250000)= 154509 |