Устранение хвостового крика
We have discussed (in tail recursion) that a recursive function is tail recursive if the recursive call is the last thing executed by the function.
C++
// An example of tail recursive functionvoid print(int n){ if (n < 0) return; cout << " " << n; // The last executed statement is recursive call print(n-1);} |
Java
// An example of tail recursive functionstatic void print(int n){ if (n < 0) return; System.out.print(" " + n); // The last executed statement // is recursive call print(n - 1);}// This code is contributed by rutvik_56 |
Python3
# An example of tail recursive functiondef print(n): if (n < 0): return print(" ", n) # The last executed statement is recursive call print(n - 1)# This code is contributed by sanjoy_62 |
C#
// An example of tail recursive functionstatic void print(int n){ if (n < 0) return; Console.Write(" " + n); // The last executed statement // is recursive call print(n - 1);}// This code is contributed by pratham76 |
Javascript
<script>// An example of tail recursive functionfunction print(n){ if (n < 0) return; document.write( " " + n); // The last executed statement is recursive call print(n-1);}</script> |
Мы также обсудили, что хвостовая рекурсия лучше, чем не хвостовая рекурсия, поскольку хвостовая рекурсия может быть оптимизирована современными компиляторами. Современный компилятор в основном делает устранение хвостового вызова для оптимизации кода с хвостовой рекурсией.
If we take a closer look at the above function, we can remove the last call with goto. Below are examples of tail call elimination.
C++
// Above code after tail call eliminationvoid print(int n){start: if (n < 0) return; cout << " " << n; // Update parameters of recursive call // and replace recursive call with goto n = n-1 goto start;} |
QuickSort : One more example
QuickSort is also tail recursive (Note that MergeSort is not tail recursive, this is also one of the reasons why QuickSort performs better)
C++
/* Tail recursive function for QuickSort arr[] --> Array to be sorted, low --> Starting index, high --> Ending index */void quickSort(int arr[], int low, int high){ if (low < high) { /* pi is partitioning index, arr[p] is now at right place */ int pi = partition(arr, low, high); // Separately sort elements before // partition and after partition quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); }}// See below link for complete running code |
Вышеупомянутую функцию можно заменить следующей после устранения хвостового вызова.
Поэтому задача компиляторов - определить хвостовую рекурсию, добавить метку в начале и обновить параметр (ы) в конце, а затем добавить последний оператор goto.
Управление кадрами стека функций в устранении хвостового вызова:
Рекурсия использует стек для отслеживания вызовов функций. При каждом вызове функции в стек помещается новый фрейм, содержащий локальные переменные и данные этого вызова. Скажем, для одного кадра стека требуется O (1), т. Е. Постоянное пространство памяти, тогда для N рекурсивных вызовов требуется память O (N).
Устранение хвостового вызова снижает пространственную сложность рекурсии с O (N) до O (1). Поскольку вызов функции исключен, новые кадры стека не создаются, и функция выполняется в постоянном пространстве памяти.
Функция может выполняться в постоянном пространстве памяти, потому что в хвостовой рекурсивной функции нет операторов после оператора вызова, поэтому сохранение состояния и кадра родительской функции не требуется. Дочерняя функция вызывается и немедленно завершается, ей не нужно возвращать управление родительской функции.
Поскольку для возвращаемого значения не выполняются вычисления и не остается никаких операторов для выполнения, текущий кадр может быть изменен в соответствии с требованиями текущего вызова функции. Таким образом, нет необходимости сохранять кадры стека предыдущих вызовов функций, и функция выполняется в постоянном пространстве памяти. Это делает хвостовую рекурсию более быстрой и удобной для памяти.
Следующая статья:
Оптимизация вызовов QuickSort Tail (сокращение места для журнала в худшем случае)
Эта статья предоставлена Дираджем Джайном . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше
Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .
Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.