Что такое рекурсия хвоста?

Хвостовая рекурсия - это тип вызова метода программирования, при котором метод вызывает сам себя, а затем немедленно возвращает значение этого второго вызова. Другими словами, хвостовая рекурсия происходит, когда заключительный оператор внутри метода - это еще один вызов этого же метода. Параметры во втором вызове метода обычно отличаются от параметров первого, но это не обязательно. Чтобы эта рекурсия работала, метод, который вызывается внутри самого себя, должен возвращать конкретное значение, такое как число, строка или какой-либо другой объект. Пустые методы, которые не возвращают значение, плохо работают для рекурсии.

Требование, чтобы рекурсивный вызов был последним оператором в вызывающем методе, не обязательно означает, что рекурсивный вызов является последней строкой в ​​методе. Правильный вызов хвостовой рекурсии также может быть найден внутри структуры управления, что означает, что в исходном коде структура управления может завершать метод, а не вызов. Важным отличием в этом случае является то, что структура управления является не оператором программирования, а встроенной частью компьютерного языка.

Хвостовая рекурсия существует во многих компьютерных языках, включая Java и C ++. Часто эти рекурсивные вызовы могут быть переписаны с использованием других средств, таких как циклы for, while и операторы goto. Утилита рекурсии обнаруживается при создании множества последовательных вызовов одного и того же метода. Рекурсия часто является самым чистым и простым способом выполнения повторяющихся задач.

Типичным примером хвостовой рекурсии является метод, который вычисляет факториал числа. Этот процесс идеален, потому что, начиная с любого числа, каждый номер, прежде чем он умножается вместе. Таким образом, чтобы найти факториал 5, правильный процесс для этого должен был бы умножить 5 * 4 * 3 * 2 * 1. Рекурсия возникает из-за структуры факториального метода: если факториал равен 1, вернуть 1, в противном случае вернуть факториал числа, данного методу, минус один. Этот метод также полезен, потому что он может быть эквивалентно написан с использованием любого типа хвостовой рекурсии, с оператором управления или без него вокруг последнего вызова метода.

Хвостовая рекурсия - это лишь один из примеров нескольких типов рекурсии. Понятие во всех типах рекурсии по сути одно и то же, что в некотором роде метод вызывает сам себя. Из этих типов различие хвостовой рекурсии состоит в том, что значение рекурсивного вызова немедленно возвращается, и больше ничего не происходит в вызывающем методе после этого вызова.