Mutual recursion: Difference between revisions
Content added Content deleted
m (Added Sidef language) |
m ({{out}}) |
||
Line 1: | Line 1: | ||
{{task|recursion}} |
{{task|recursion}} |
||
Two functions are said to be mutually recursive if the first calls the second, |
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: |
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: | Line 12: | ||
</math> |
</math> |
||
<br>(If a language does not allow for a solution using mutually recursive functions |
<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}}== |
=={{header|ACL2}}== |
||
Line 152: | Line 154: | ||
new line(stand out) |
new line(stand out) |
||
)</lang> |
)</lang> |
||
{{out}} |
|||
Output: |
|||
<pre> |
<pre> |
||
1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 |
1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 |
||
Line 271: | Line 273: | ||
DEF FNm(n%) IF n% = 0 THEN = 0 ELSE = n% - FNf(FNm(n% - 1))</lang> |
DEF FNm(n%) IF n% = 0 THEN = 0 ELSE = n% - FNf(FNm(n% - 1))</lang> |
||
{{out}} |
|||
'''Output:''' |
|||
<pre> |
<pre> |
||
F sequence: |
F sequence: |
||
Line 479: | Line 481: | ||
</lang> |
</lang> |
||
{{out}} |
|||
output |
|||
<lang> |
<lang> |
||
> coffee mutual_recurse.coffee |
> coffee mutual_recurse.coffee |
||
Line 819: | Line 820: | ||
println 'm(0..20): ' + (0..20).collect { m(it) }</lang> |
println 'm(0..20): ' + (0..20).collect { m(it) }</lang> |
||
{{out}} |
|||
Output: |
|||
<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] |
<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> |
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: | Line 901: | ||
} |
} |
||
print(out.F + "\n" + out.M);</lang> |
print(out.F + "\n" + out.M);</lang> |
||
{{out}} |
|||
outputs: |
|||
<pre>1,1,2,2,3,3,4,5,5,6,6,7,8,8,9,9,10,11,11,12 |
<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> |
0,0,1,2,2,3,4,4,5,6,6,7,7,8,9,9,10,11,11,12</pre> |
||
Line 922: | Line 923: | ||
<lang julia>F(n) = n < 1 ? one(n) : n - M(F(n - 1)) |
<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> |
M(n) = n < 1 ? zero(n) : n - F(M(n - 1))</lang> |
||
{{out}} |
|||
Output: |
|||
<pre> |
<pre> |
||
julia> [F(i) for i = 0:19], [M(i) for i = 0:19] |
julia> [F(i) for i = 0:19], [M(i) for i = 0:19] |
||
Line 1,013: | Line 1,014: | ||
} |
} |
||
}</lang> |
}</lang> |
||
{{out}} |
|||
Output: |
|||
<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 |
<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> |
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: | Line 1,079: | ||
end</lang> |
end</lang> |
||
{{out}} |
|||
Sample Output: |
|||
<lang MATLAB>>> n = (0:10); |
<lang MATLAB>>> n = (0:10); |
||
>> arrayfun(@female,n) |
>> arrayfun(@female,n) |
||
Line 1,222: | Line 1,223: | ||
TRAP 0,Halt,0</lang> |
TRAP 0,Halt,0</lang> |
||
{{out}} |
|||
Output: |
|||
~/MIX/MMIX/Rosetta> mmix mutualrecurs1 |
~/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 |
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: | Line 1,680: | ||
CloseConsole() |
CloseConsole() |
||
EndIf</lang> |
EndIf</lang> |
||
{{out}} |
|||
Sample output: |
|||
<pre>1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12 |
<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> |
0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12</pre> |
||
Line 1,691: | Line 1,692: | ||
print ([ M(n) for n in range(20) ])</lang> |
print ([ M(n) for n in range(20) ])</lang> |
||
{{out}} |
|||
Output: |
|||
<pre>[1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12] |
<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> |
[0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12]</pre> |
||
Line 1,726: | Line 1,727: | ||
print ["F:" mold fs crlf "M:" mold ms]</lang> |
print ["F:" mold fs crlf "M:" mold ms]</lang> |
||
{{out}} |
|||
Output: |
|||
<pre>F: [1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12] |
<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: | Line 1,756: | ||
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> |
Jw: return right(arg(1),length(lim)) /*right justifies # for nice look*/</lang> |
||
{{out}} using the default input of: <tt> 40 </tt> |
|||
<pre style="height:30ex"> |
<pre style="height:30ex"> |
||
F( 0) = 1 M( 0) = 0 |
F( 0) = 1 M( 0) = 0 |
||
Line 1,818: | Line 1,819: | ||
M: procedure expose hm. hf.; parse 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)) /*right justifies # for nice look*/</lang> |
Jw: return right(arg(1),length(lim)) /*right justifies # for nice look*/</lang> |
||
{{out}} using the default input of: <tt> 99 </tt> |
|||
<pre> |
<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 |
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: | Line 1,847: | ||
M: procedure expose hm. hf.; parse 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)) /*right justifies # for nice look*/</lang> |
Jw: return right(arg(1),length(lim)) /*right justifies # for nice look*/</lang> |
||
{{out}} using the input of: <tt> -70000 </tt> |
|||
<pre> |
<pre> |
||
J(70000)= 70000 |
J(70000)= 70000 |
||
Line 1,852: | Line 1,853: | ||
M(70000)= 43262 |
M(70000)= 43262 |
||
</pre> |
</pre> |
||
{{out}} using the input of a ¼ million: <tt> -250000 </tt> |
|||
<pre> |
<pre> |
||
J(250000)= 250000 |
J(250000)= 250000 |
||
Line 1,870: | Line 1,871: | ||
p (Array.new(20) {|n| M(n) })</lang> |
p (Array.new(20) {|n| M(n) })</lang> |
||
{{out}} |
|||
Output: |
|||
<pre>[1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12] |
<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> |
[0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12]</pre> |
||
Line 1,896: | Line 1,897: | ||
if n <> 0 then m = n - f(m(n - 1)) |
if n <> 0 then m = n - f(m(n - 1)) |
||
end function</lang> |
end function</lang> |
||
{{out}} |
|||
Output: |
|||
<pre>F sequence:1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 13 |
<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> |
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: | Line 1,927: | ||
println!("") |
println!("") |
||
}</lang> |
}</lang> |
||
{{out}} |
|||
Output: |
|||
<pre>1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 |
<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> |
0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12</pre> |
||
Line 1,969: | Line 1,970: | ||
println((0 until 20).map(M).mkString(", "))</lang> |
println((0 until 20).map(M).mkString(", "))</lang> |
||
{{out}} |
|||
Output: |
|||
<pre>1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12 |
<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> |
0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12</pre> |
||
Line 2,101: | Line 2,102: | ||
end</lang> |
end</lang> |
||
{{out}} |
|||
Output: |
|||
<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 |
<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> |
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: | Line 2,288: | ||
test = ^(F*,M*) iota 20</lang> |
test = ^(F*,M*) iota 20</lang> |
||
{{out}} |
|||
output: |
|||
<pre> |
<pre> |
||
( |
( |
||
Line 2,401: | Line 2,402: | ||
]</lang> |
]</lang> |
||
{{out}} |
|||
Output: |
|||
<pre> |
<pre> |
||
1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 |
1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 |