프롤로그의 재귀

Question

프롤로그에서 재귀를 이해하기 란 정말 어렵지만 다른 언어의 방법과는 분명 다릅니다 (PHP, Java 및 C로 작업하고 있습니다).

그래, 나는 그것에 관한 모든 튜토리얼을 읽었지 만 여전히 구체적인, 다소 복잡한 경우는 얻지 못한다. 예를 들어

, 목록에서 요소의 발생 횟수를 얻기 위해 우리는이 :

사용 호출 할 수 있습니다

occurrence([], _, 0). 
occurrence([H | T], H, N) :- !, occurrence(T, H, N1), N is N1 + 1. 
occurrence([_ | T], H, N) :- occurrence(T, H, N). 

가 :

occurrence([1,4,9,1,2],1,R). 

하고 결과를해야합니다

?- R=2 

이제 3 행이 왜 발생합니까? 뭐하는거야? 나는 답을 보지 않고이 프로그램을 썼고 두 번째 줄 이후에 끝났다. Ofcourse 그것 doesn''t는 일하고있다.

반면에 "절단"이 왜 발생합니까? 모든 호출 후에 결과를 출력하려고 노력해 왔으며 점점 더 혼란스러워졌습니다.

Answer 1

3 호는 목록의 머리말이 찾고있는 항목과 일치하지 않는 경우를 처리합니다. 경기를 지배

occurrence([4,9,1,2], 1, 1). 

: 당신이 첫 번째 요소를 통과 한 가정 해, 당신과 같은 occurrence/3에 재귀 호출에 바람? 규칙 1은 비어있는 목록이 없기 때문에 일치하지 않습니다. 규칙 2는 4 \ = 1이기 때문에 일치하지 않습니다. 세 번째 규칙은이 경우를위한 것이며 여기에 1을 찾지 못했기 때문에 목록의 꼬리를 계속 살펴 봅니다 ([9,1,2 ]).

세 번째 규칙은 모든 목록과 일치하므로 잘라내 기가 있습니다. 커팅을 선택하면 커밋됩니다. 무슨 선택이야? 목록의 머리 부분과 찾고자하는 요소와 동일한 값을가집니다.이 규칙의 본문을 입력하기 위해 일치해야하는 패턴이기 때문입니다. 당신은 당신이 R = 2 통일화 둘 이상의 솔루션을 얻을 것이다 의미 추구되는 요소 목록의 머리를 통일 후 선택 포인트 을 허용하고, 상처를 생략하면, R = 1, R = 0입니다. 이것은 각각의 1이 세 번째 규칙 에서처럼 무시 될 수 있기 때문입니다.

조건부 세 번째 규칙함으로써 절단 제거 할 수

:

occurrence([H|T], S, N) :- 
    (H = S 
    -> occurrence(T, S, N1), N is N1 + 1 
     ; occurrence(T, S, N) 
). 

이를 :

occurrence([H1|T], H2, N) :- H1 \= H2, occurrence(T, H2, N). 

당신은 또한 하나의 규칙은 규칙 2와 3을 결합 조건식을 사용하고있을 수를 다소 효율적 일 것 같다. 조건식은 추가 규칙 본문이하는 방식으로 선택 점을 만들지 않습니다. Prolog는 초능력이 아니므로 규칙이 상호 배타적이라는 것을 감지 할 수 없습니다. 나는 가독성을 위해 여러 규칙을 가진 논리적 공식을 선호 할 것이다.

희망이 도움이됩니다.