Anonymous user
Mutual recursion: Difference between revisions
m
{{out}}
m (Added Sidef language) |
m ({{out}}) |
||
Line 1:
{{task|recursion}}
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 [[wp:Hofstadter sequence#Hofstadter Female and Male sequences|Hofstadter Female and Male sequences]] defined as:
Line 11 ⟶ 12:
</math>
<br>(If a language does not allow for a solution using mutually recursive functions
then state this rather than give a solution by other means).
=={{header|ACL2}}==
Line 152 ⟶ 154:
new line(stand out)
)</lang>
{{out}}
<pre>
1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12
Line 271 ⟶ 273:
DEF FNm(n%) IF n% = 0 THEN = 0 ELSE = n% - FNf(FNm(n% - 1))</lang>
{{out}}
<pre>
F sequence:
Line 479 ⟶ 481:
</lang>
{{out}}
<lang>
> coffee mutual_recurse.coffee
Line 819 ⟶ 820:
println 'm(0..20): ' + (0..20).collect { m(it) }</lang>
{{out}}
<pre>f(0..20): [1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 13]
m(0..20): [0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12]</pre>
Line 900 ⟶ 901:
}
print(out.F + "\n" + out.M);</lang>
{{out}}
<pre>1,1,2,2,3,3,4,5,5,6,6,7,8,8,9,9,10,11,11,12
0,0,1,2,2,3,4,4,5,6,6,7,7,8,9,9,10,11,11,12</pre>
Line 922 ⟶ 923:
<lang julia>F(n) = n < 1 ? one(n) : n - M(F(n - 1))
M(n) = n < 1 ? zero(n) : n - F(M(n - 1))</lang>
{{out}}
<pre>
julia> [F(i) for i = 0:19], [M(i) for i = 0:19]
Line 1,013 ⟶ 1,014:
}
}</lang>
{{out}}
<pre>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
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>
Line 1,078 ⟶ 1,079:
end</lang>
{{out}}
<lang MATLAB>>> n = (0:10);
>> arrayfun(@female,n)
Line 1,222 ⟶ 1,223:
TRAP 0,Halt,0</lang>
{{out}}
~/MIX/MMIX/Rosetta> mmix mutualrecurs1
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
Line 1,679 ⟶ 1,680:
CloseConsole()
EndIf</lang>
{{out}}
<pre>1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12
0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12</pre>
Line 1,691 ⟶ 1,692:
print ([ M(n) for n in range(20) ])</lang>
{{out}}
<pre>[1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12]
[0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12]</pre>
Line 1,726 ⟶ 1,727:
print ["F:" mold fs crlf "M:" mold ms]</lang>
{{out}}
<pre>F: [1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12]
Line 1,755 ⟶ 1,756:
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>
<pre style="height:30ex">
F( 0) = 1 M( 0) = 0
Line 1,818 ⟶ 1,819:
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)) /*right justifies # for nice look*/</lang>
<pre>
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
Line 1,846 ⟶ 1,847:
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)) /*right justifies # for nice look*/</lang>
<pre>
J(70000)= 70000
Line 1,852 ⟶ 1,853:
M(70000)= 43262
</pre>
<pre>
J(250000)= 250000
Line 1,870 ⟶ 1,871:
p (Array.new(20) {|n| M(n) })</lang>
{{out}}
<pre>[1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12]
[0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12]</pre>
Line 1,896 ⟶ 1,897:
if n <> 0 then m = n - f(m(n - 1))
end function</lang>
{{out}}
<pre>F sequence:1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 13
M sequence:0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12 12</pre>
Line 1,926 ⟶ 1,927:
println!("")
}</lang>
{{out}}
<pre>1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12
0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12</pre>
Line 1,969 ⟶ 1,970:
println((0 until 20).map(M).mkString(", "))</lang>
{{out}}
<pre>1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12
0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12</pre>
Line 2,101 ⟶ 2,102:
end</lang>
{{out}}
<pre>M: 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
F: 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</pre>
Line 2,287 ⟶ 2,288:
test = ^(F*,M*) iota 20</lang>
{{out}}
<pre>
(
Line 2,401 ⟶ 2,402:
]</lang>
{{out}}
<pre>
1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12
|