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, and in turn the second calls the first.
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 then state this rather than give a solution by other means).
<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>
'''output''' using the default input of: &nbsp; <tt> 40 </tt>
{{out}} using the default input of: &nbsp; <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>
'''output''' using the default input of: &nbsp; <tt> 99 </tt>
{{out}} using the default input of: &nbsp; <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>
'''output''' using the input of: &nbsp; <tt> -70000 </tt>
{{out}} using the input of: &nbsp; <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>
'''output''' using the input of a ¼ million: &nbsp; <tt> -250000 </tt>
{{out}} using the input of a ¼ million: &nbsp; <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
Retrieved from "https://rosettacode.org/wiki/Mutual_recursion"