Mutual recursion: Difference between revisions

Content added Content deleted

Inline

@@ Line 2,992: / Line 2,992: @@
 =={{header|Picat}}==
-Here are two approaches:
+Here are two approaches, both using tabling. For small values (say N < 50) tabling is not really needed.
+===Tabled functions===
-* a (tabled) function based: f/1 and f/2
+<lang Picat>table
-* a (tabled) predicate based: male/2 and female/2 {{trans|Prolog}}
+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.</lang>
+===Tabled predicates===
-For small values (say N < 50) tabling is not really needed.
+{{trans|Prolog}}
+<lang Picat>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>
+===Test===
 <lang Picat>go =>
   N = 30,
@@ Line 3,018: / Line 3,042: @@
   println([M : I in 0..N, male(I,M)]),
   println([F : I in 0..N, female(I,F)]),
-  nl.
+  nl.</lang>
-% 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
@@ Line 3,058: / Line 3,053: @@
 [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>
+===Larger values===
-For larger values, tabling is essential and then one can discern that the predicate based approach is a little faster.
+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:
-Here are the times for testing N=1 000 000:
 * func: 1.829s
 * pred: 1.407s
 =={{header|PicoLisp}}==