Mutual recursion: Difference between revisions

=={{header|Picat}}==

Here are two approaches:

* a (tabled) function based: f/1 and f/2

* a (tabled) predicate based: male/2 and female/2 {{trans|Prolog}}

For small values (say N < 50) tabling is not really needed.

<lang Picat>go =>

N = 30,

println(func),

test_func(N),

println(pred),

test_pred(N),

nl.

nl.

% Testing the function based approach

test_func(N) =>

println([M : I in 0..N, male(I,M)]),

println([F : I in 0..N, female(I,F)]),

nl.

% Testing the predicate approach

test_pred(N) =>

println([M : I in 0..N, male(I,M)]),

println([F : I in 0..N, female(I,F)]),

nl.

% Function based

table

f(0) = 1.

f(N) = N - m(f(N-1)), N > 0 => true.

table

m(0) = 0.

m(N) = N - f(m(N-1)), N > 0 => true.

% predicate based

% translation of the Prolog solution

table

female(0,1).

female(N,F) :-

N>0,

N1 = N-1,

female(N1,R),

male(R, R1),

F = N-R1.

table

male(0,0).

male(N,F) :-

N>0,

N1 = N-1,

male(N1,R),

female(R, R1),

F = N-R1.</lang>

{{out}}

<pre>func

[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]

[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]

pred

[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]

[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]</pre>

For larger values, tabling is essential and then one can discern that the predicate based approach is a little faster.

Here are the times for testing N=1 000 000:

* func: 1.829s

* pred: 1.407s