Mutual recursion: Difference between revisions
Content added Content deleted
(Made code Forth200x compliant) |
(→{{header|REXX}}: added version 2, changed the format of the output. -- ~~~~) |
||
| Line 1,435: | Line 1,435: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
===version 1=== |
|||
<lang rexx>/*REXX program |
<lang rexx>/*REXX program shows mutual recursion (via Hofstadter Male & Female seq)*/ |
||
arg limit .; if limit='' then limit=40 |
|||
arg lim .; if lim='' then lim=40; pad=left('',20) |
|||
do j=0 to limit |
|||
say 'F('right(j,2)")="right(F(j),9) ' M('right(j,2)")="right(M(j),9) |
|||
do j=0 to lim; jj=Jw(j); ff=F(j); mm=M(j) |
|||
say pad 'F('jj") =" Jw(ff) pad 'M('jj") =" Jw(mm) /*display nicely.*/ |
|||
end |
end |
||
exit |
exit |
||
/*─────────────────────────────────────F |
/*─────────────────────────────────────F, M, Jw subroutines────────────*/ |
||
F: procedure; parse 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; parse 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*/</lang> |
|||
'''output'' (using the default of 40): |
'''output''' (using the default of 40): |
||
<pre style="height:30ex;overflow:scroll"> |
<pre style="height:30ex;overflow:scroll"> |
||
F( 0)= |
F( 0) = 1 M( 0) = 0 |
||
F( 1)= |
F( 1) = 1 M( 1) = 0 |
||
F( 2)= |
F( 2) = 2 M( 2) = 1 |
||
F( 3)= |
F( 3) = 2 M( 3) = 2 |
||
F( 4)= |
F( 4) = 3 M( 4) = 2 |
||
F( 5)= |
F( 5) = 3 M( 5) = 3 |
||
F( 6)= |
F( 6) = 4 M( 6) = 4 |
||
F( 7)= |
F( 7) = 5 M( 7) = 4 |
||
F( 8)= |
F( 8) = 5 M( 8) = 5 |
||
F( 9)= |
F( 9) = 6 M( 9) = 6 |
||
F(10)= |
F(10) = 6 M(10) = 6 |
||
F(11)= |
F(11) = 7 M(11) = 7 |
||
F(12)= |
F(12) = 8 M(12) = 7 |
||
F(13)= |
F(13) = 8 M(13) = 8 |
||
F(14)= |
F(14) = 9 M(14) = 9 |
||
F(15)= |
F(15) = 9 M(15) = 9 |
||
F(16)= |
F(16) = 10 M(16) = 10 |
||
F(17)= |
F(17) = 11 M(17) = 11 |
||
F(18)= |
F(18) = 11 M(18) = 11 |
||
F(19)= |
F(19) = 12 M(19) = 12 |
||
F(20)= |
F(20) = 13 M(20) = 12 |
||
F(21)= |
F(21) = 13 M(21) = 13 |
||
F(22)= |
F(22) = 14 M(22) = 14 |
||
F(23)= |
F(23) = 14 M(23) = 14 |
||
F(24)= |
F(24) = 15 M(24) = 15 |
||
F(25)= |
F(25) = 16 M(25) = 16 |
||
F(26)= |
F(26) = 16 M(26) = 16 |
||
F(27)= |
F(27) = 17 M(27) = 17 |
||
F(28)= |
F(28) = 17 M(28) = 17 |
||
F(29)= |
F(29) = 18 M(29) = 18 |
||
F(30)= |
F(30) = 19 M(30) = 19 |
||
F(31)= |
F(31) = 19 M(31) = 19 |
||
F(32)= |
F(32) = 20 M(32) = 20 |
||
F(33)= |
F(33) = 21 M(33) = 20 |
||
F(34)= |
F(34) = 21 M(34) = 21 |
||
F(35)= |
F(35) = 22 M(35) = 22 |
||
F(36)= |
F(36) = 22 M(36) = 22 |
||
F(37)= |
F(37) = 23 M(37) = 23 |
||
F(38)= |
F(38) = 24 M(38) = 24 |
||
F(39)= |
F(39) = 24 M(39) = 24 |
||
F(40)= |
F(40) = 25 M(40) = 25 |
||
</pre> |
|||
===version 2=== |
|||
This version of the REXX program uses memoization as well as a horizontal output format. |
|||
<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)*/ |
|||
arg lim .;if lim='' then lim=99; hm.=; hm.0=0; hf.=; hf.0=1; Js=; Fs=; Ms= |
|||
do j=0 to lim; ff=F(j); mm=M(j) |
|||
Js=Js jW(j); Fs=Fs jw(ff); Ms=Ms jW(mm) |
|||
end |
|||
say 'Js='strip(Js) |
|||
say 'Fs='strip(Fs) |
|||
say 'Ms='strip(Ms) |
|||
exit |
|||
/*─────────────────────────────────────F, M, Jw subroutines────────────*/ |
|||
F: procedure expose hm. hf.;parse arg n;if hf.n=='' then hf.n=n-M(F(n-1)) |
|||
return hf.n /*Hofstadter seq uses memoization*/ |
|||
M: procedure expose hm. hf.;parse arg n;if hm.n=='' then hm.n=n-F(M(n-1)) |
|||
return hm.n /*Hofstadter seq uses memoization*/ |
|||
Jw: return right(arg(1),length(lim)) /*right justifies # for nice look*/</lang> |
|||
'''output''' (using the default of 99): |
|||
<pre style="height:15ex;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 |
|||
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 |
|||
Ms=0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12 12 13 14 14 15 16 16 17 17 18 19 19 20 20 21 22 22 23 24 24 25 25 26 27 27 28 29 29 30 30 31 32 32 33 33 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 54 55 56 56 57 58 58 59 59 60 61 61 |
|||
</pre> |
</pre> |
||