एक ट्रैम्पोलिन स्टैक-आधारित रिकर्सन को बराबर लूप में बदलने के लिए एक पैटर्न है। चूंकि लूप स्टैक फ्रेम नहीं जोड़ते हैं, इसलिए इसे स्टैकलेस रिकर्सन के रूप में माना जा सकता है।
यहाँ एक चित्र मैंने पाया उपयोगी है:
से bartdesmet.net
आप एक प्रक्रिया है कि एक प्रारंभिक मूल्य लेता है के रूप में एक ट्रैम्पोलिन के बारे में सोच सकते हैं; उस मूल्य पर पुनरावृत्ति; और फिर अंतिम मूल्य के साथ बाहर निकलता है।
इस ढेर आधारित प्रत्यावर्तन पर विचार करें:
public static int factorial(final int n) {
if (n <= 1) {
return 1;
}
return n * factorial(n - 1);
}
हर पुनरावर्ती कॉल इस बनाता है, एक नया फ्रेम धकेल दिया जाता है। ऐसा इसलिए है क्योंकि पूर्व फ्रेम नए फ्रेम के परिणाम के बिना मूल्यांकन नहीं कर सकता है। यह एक समस्या बन जाएगी जब ढेर बहुत गहरा हो जाता है और हम स्मृति से बाहर हो जाते हैं।
public static int factorial2(int n) {
int i = 1;
while (n > 1) {
i = i * n;
n--;
}
return i;
}
यहाँ क्या हो रहा है:
सौभाग्य से, हम एक पाश के रूप में इस समारोह को व्यक्त कर सकते हैं? हमने रिकर्सिव कदम उठाया है और इसे लूप के अंदर पुनरावृत्ति बना दिया है। हम लूप करते हैं जब तक कि हम सभी रिकर्सिव चरणों को पूरा नहीं कर लेते हैं, परिणाम को संग्रहित करते हैं या एक चर में प्रत्येक पुनरावृत्ति को संग्रहित करते हैं।
यह अधिक कुशल है क्योंकि कम फ्रेम बनाए जाएंगे। प्रत्येक रिकर्सिव कॉल (n फ़्रेम) के लिए फ्रेम संग्रहीत करने के बजाय, हम वर्तमान मान और शेष पुनरावृत्तियों की संख्या (2 मान) को संग्रहीत करते हैं।
इस पैटर्न का सामान्यीकरण एक ट्रैम्पोलिन है।
public class Trampoline<T>
{
public T getValue() {
throw new RuntimeException("Not implemented");
}
public Optional<Trampoline<T>> nextTrampoline() {
return Optional.empty();
}
public final T compute() {
Trampoline<T> trampoline = this;
while (trampoline.nextTrampoline().isPresent()) {
trampoline = trampoline.nextTrampoline().get();
}
return trampoline.getValue();
}
}
Trampoline दो सदस्यों की आवश्यकता है:
- मौजूदा चरण का मूल्य;
- अगले समारोह गणना करने के लिए, या कुछ भी नहीं है अगर हम अंतिम चरण
किसी भी गणना इस तरह से वर्णित किया जा सकता है कि कर सकते हैं "trampolined" हो पहुँच गए हैं।
यह फैक्टोरियल के लिए कैसा दिखता है?
public final class Factorial
{
public static Trampoline<Integer> createTrampoline(final int n, final int sum)
{
if (n == 1) {
return new Trampoline<Integer>() {
public Integer getValue() { return sum; }
};
}
return new Trampoline<Integer>() {
public Optional<Trampoline<Integer>> nextTrampoline() {
return Optional.of(createTrampoline(n - 1, sum * n));
}
};
}
}
और कॉल करने के लिए:
Factorial.createTrampoline(4, 1).compute()
नोट्स
- Boxing इस जावा में अक्षम कर देगा।
- यह कोड SO पर लिखा गया था; यह परीक्षण नहीं किया गया है या यहां तक कि
आगे पढ़ने संकलित
[यह सवाल] (http://stackoverflow.com/questions/159590/way-to-go-from-recursion-to-iteration) एक सहायक के रूप में शुरू हो सकता है [इस जवाब हो सकता है, ] (http://programmers.stackexchange.com/a/194708) प्रोग्रामर पर, जो ट्रैम्पोलिन पर छूते हैं –
ट्रैम्पोलिन कार्यान्वयन के बारे में इस धागे पर एक नज़र डालें: [http://stackoverflow.com/questions/189725/what -इस-ए-ट्रैम्पोलिन-फ़ंक्शन] (http://stackoverflow.com/questions/189725/what-is-a-trampoline- कार्यक्षमता) –