Prolog भाज्य प्रत्यावर्तन

Question

मैं मुसीबत निम्नलिखित भाज्य कार्यक्रम

fact1(0,Result) :- 
    Result is 1. 
fact1(N,Result) :- 
    N > 0, 
    N1 is N-1, 
    fact1(N1,Result1), 
    Result is Result1*N. 

जब fact1 दूसरा fact1 भीतर नेस्ट कहा जाता है को समझने आ रही है, इसका मतलब यह नहीं है कि अंतिम पंक्ति, Result is Result1*N., कभी नहीं कहा जाता है? या प्रोलॉग में पिछली पंक्ति रिकर्सिव कॉल से पहले निष्पादित की जाती है?

Answer 1

नहीं, रिकर्सिव कॉल पहले होता है! इसे, या फिर अंतिम खंड का अर्थ व्यर्थ है।

factorial(0) => 1 
factorial(n) => factorial(n-1) * n; 

आप देख सकते हैं, तो आप के लिए एक सही मान वापस जाने के लिए में गुणा से पहले प्रत्यावर्तन के परिणाम की गणना करने की जरूरत है: एल्गोरिथ्म के लिए टूट जाती है!

आपके प्रोलॉग कार्यान्वयन में शायद ट्रेसिंग को सक्षम करने का एक तरीका है, जो आपको पूरे एल्गोरिदम को चलाने देता है। इससे आपकी मदद हो सकती है।

Answer 2

BTW एक बार आप बुनियादी प्रत्यावर्तन समझ में आ गया है, जब भी संभव हो पूंछ प्रत्यावर्तन प्राप्त करने के लिए प्रयास करते हैं, यहाँ यह होगी:

factorial(N, R) :- factorial(N, 1, R). 
factorial(0, R, R) :- !. 
factorial(N, Acc, R) :- 
    NewN is N - 1, 
    NewAcc is Acc * N, 
    factorial(NewN, NewAcc, R). 

पूंछ प्रत्यावर्तन, प्रत्यावर्तन आप पहले उपयोग के विपरीत, दुभाषिया/संकलक फ्लश करने के लिए अनुमति देता है रिकर्सन के अगले चरण पर जाने पर संदर्भ। तो आइए मान लें कि आप factorial(1000) की गणना करते हैं, आपका संस्करण 1000 संदर्भ बनाए रखेगा जबकि मेरा केवल बनाएगा। इसका मतलब है कि आपका संस्करण अंततः वांछित परिणाम की गणना नहीं करेगा बल्कि Out of call stack memory त्रुटि पर क्रैश होगा।

आप विकिपीडिया पर इसके बारे में read more कर सकते हैं।

Answer 3

यह ऐसा करने का एक नहीं बल्कि सरल तरीका यह है:

fac(0,1). 
fac(N,F):- 
    N>0,N1 is N-1,fac(N1,F1),F is N*F1. 

Answer 4

सामान्य शब्दों में, @m09's answer मूल रूप से पूंछ-प्रत्यावर्तन के महत्व के बारे में सही है।

बड़े N के लिए, उत्पाद की गणना अलग-अलग जीतती है! "बाइनरी पेड़" सोचें, न कि "रैखिक सूची" ...

चलिए दोनों तरीकों का प्रयास करें और रनटाइम की तुलना करें। सबसे पहले, @ m09 के factorial/2:

 
?- time((numlist(1,100000,Xs),reduce(\X^Y^XY^(XY is X*Y),Xs,_),false)). 
% 1,300,042 inferences, 0.264 CPU in 0.264 seconds (100% CPU, 4922402 Lips) 
false. 

अंतिम, चलो निर्दिष्ट कर सकते हैं और समर्पित उपयोग सहायक विधेय x_y_product/3:

 
?- time((factorial(100000,_),false)). 
% 200,004 inferences, 1.606 CPU in 1.606 seconds (100% CPU, 124513 Lips) 
false. 

इसके बाद, हम यह पेड़ शैली — meta-predicatereduce/3 एक साथ उपयोग lambda expressions के साथ क्या

x_y_product(X, Y, XY) :- XY is X*Y. 

क्या हासिल करना है? चलो स्टॉपवॉच से पूछें!

 
?- time((numlist(1,100000,Xs),reduce(x_y_product,Xs,_),false)). 
% 500,050 inferences, 0.094 CPU in 0.094 seconds (100% CPU, 5325635 Lips) 
false. 

Answer 5

मैं की तरह कुछ करना होगा:

fact(0, 1). 
fact(N, Result):- 
    Next is N - 1, 
    fact(Next, Recursion), 
    Result is N * Recursion. 

और एक पूंछ संस्करण की तरह होगा:

गैर पूंछ पुनरावर्ती:

tail_fact(0, 1, 0).   /* when trying to calc factorial of zero */ 
tail_fact(0, Acc, Res):- /* Base case of recursion, when reaches zero return Acc */ 
    Res is Acc. 
tail_fact(N, Acc, Res):- /* calculated value so far always goes to Acc */ 
    NewAcc is N * Acc, 
    NewN is N - 1, 
    tail_fact(NewN, NewAcc, Res). 

तो आपको कॉल करने के लिए विधि: तथ्य (3, परिणाम)।

पूंछ रिकर्सिव विधि: tail_fact (3, 1, परिणाम)।

यह मदद कर सकता है;)

Answer 6

गैर-टेलर प्रत्यावर्तन:

fact(0,1):-!. 
    fact(X,Y):- Z=X-1, 
     fact(Z,NZ),Y=NZ*X. 

टेलर प्रत्यावर्तन:

fact(X,F):- X>=0,fact_aux(X,F,1). 
fact_aux(0,F,F):-!. 
    fact_aux(X,F,Acc):- 
     NAcc=Acc*X, NX=X-1, 
    fact_aux(NX,F,NAcc). 

Answer 7

factorial(1, 1). 
factorial(N, Result) :- M is N - 1, 
factorial(M, NextResult), Result is NextResult * N. 

Answer 8

बेस मामले घोषित किया जाता है। ऐसी स्थितियां जो एन सकारात्मक होनी चाहिए और पिछले अवधि के साथ गुणा होनी चाहिए।

factorial(0, 1). 
factorial(N, F) :- 
     N > 0, 
     Prev is N -1, 
     factorial(Prev, R), 
     F is R * N. 

चलाने के लिए:

भाज्य (-1, एक्स)।