Revision as of 18:27, 7 May 2022 (view source) Hakank (talk \| contribs) (→‎{{header\|Picat}}) ← Older edit		Revision as of 06:11, 13 May 2022 (view source) Hakank (talk \| contribs) (→‎{{header\|Picat}}: Split into subsections) Newer edit →
Line 2,992: =={{header\|Picat}}== 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 ⟶ 3,042: println([M : I in 0..N, male(I,M)]), println([F : I in 0..N, female(I,F)]), 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 ⟶ 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. 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}}==

Mutual recursion: Difference between revisions

Mutual recursion (view source)

Revision as of 06:11, 13 May 2022