Хвост Рекурсия

01.01.2020Анализ, Рекурсия

Что такое хвостовая рекурсия?
Рекурсивная функция является хвостовой рекурсивной, когда рекурсивный вызов — это последнее, что выполняется функцией. Например, следующая функция C ++ print () является хвостовой рекурсивной.

// Пример хвостовой рекурсивной функции

void print(int n)

{

if (n < 0) return;

cout << " " << n;

// Последний выполненный оператор - рекурсивный вызов

print(n-1);

}

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

Может ли не хвостовая рекурсивная функция быть написана как хвостовая рекурсивная для ее оптимизации?
Рассмотрим следующую функцию для вычисления факториала n. Это не хвостовая рекурсивная функция. Хотя на первый взгляд хвост выглядит рекурсивным. Если мы посмотрим поближе, то увидим, что значение, возвращаемое фактом (n-1), используется в действительности (n), поэтому обращение к факту (n-1) — не последнее, что сделано fact (n)

C ++

#include<iostream>

using namespace std;

// НЕ-хвостовая рекурсивная функция. Функция не хвост
// рекурсивно, потому что значение, возвращаемое фактом (n-1), используется в
// fact (n) и обращение к факту (n-1) - это не последнее, что сделано fact (n)

unsigned int fact(unsigned int n)

{

if (n == 0) return 1;

return n*fact(n-1);

}

// Программа драйвера для проверки вышеуказанной функции

int main()

{

cout << fact(5);

return 0;

}

Джава

class GFG {

// НЕ-хвостовая рекурсивная функция.

// Функция не хвостовая

// рекурсивный, потому что значение

// возвращено по факту (n-1) используется

// фактически (n) и призыв к факту (n-1)

// это не последнее, что сделано

// факт (n)

static int fact(int n)

{

if (n == 0) return 1;

return n*fact(n-1);

}

// Драйвер программы

public static void main(String[] args)

{

System.out.println(fact(5));

}

// Этот код предоставлен Smitha.

Python 3

# Не хвостовая рекурсивная функция.
# Функция не хвостовая
# рекурсивный, потому что значение
# возвращается по факту (n-1) используется
# на самом деле (n) и призыв к факту (n-1)
# не последнее, что сделано
# факт (n)

def fact(n):

if (n == 0):

return 1

return n * fact(n-1)

# Драйвер программы для тестирования
# выше функция

print(fact(5))

# Этот код предоставлен Смитой.

C #

using System;

class GFG {

// НЕ-хвостовая рекурсивная функция.

// Функция не хвостовая

// рекурсивный, потому что значение

// возвращено по факту (n-1) используется

// фактически (n) и призыв к факту (n-1)

// это не последнее, что сделано

// факт (n)

static int fact(int n)

{

if (n == 0)

return 1;

return n * fact(n-1);

}

// Программа драйвера для тестирования

// вышеуказанная функция

public static void Main()

{

Console.Write(fact(5));

}

// Этот код предоставлен Smitha

PHP

<?php
// НЕ-хвостовая рекурсивная функция.
// Функция не хвостовая
// рекурсивный, потому что значение
// возвращено по факту (n-1) используется в
// факт (n) и призыв к факту (n-1)
// не последнее, что сделано на самом деле (n)

function fact( $n)

{

if ($n == 0) return 1;

return $n * fact($n - 1);

}

// Код драйвера

echo fact(5);

// Этот код предоставлен Ajit
?>

Выход :

Вышеуказанная функция может быть записана как хвостовая рекурсивная функция. Идея состоит в том, чтобы использовать еще один аргумент и накапливать факториальное значение во втором аргументе. Когда n достигнет 0, верните накопленное значение.

C ++

#include<iostream>

using namespace std;

// Хвостовая рекурсивная функция для вычисления факториала

unsigned factTR(unsigned int n, unsigned int a)

{

if (n == 0) return a;

return factTR(n-1, n*a);

}

// Обертка поверх factTR

unsigned int fact(unsigned int n)

{

return factTR(n, 1);

}

// Программа драйвера для проверки вышеуказанной функции

int main()

{

cout << fact(5);

return 0;

}

Джава

// Java-код для хвостовой рекурсии

class GFG {

// Хвостовая рекурсивная функция

// рассчитать факториал

static int factTR(int n, int a)

{

if (n == 0)

return a;

return factTR(n - 1, n * a);

}

// Обертка поверх factTR

static int fact(int n)

{

return factTR(n, 1);

}

// Код драйвера

static public void main (String[] args)

{

System.out.println(fact(5));

}

// Этот код предоставлен Smitha.

Python 3

# Хвостовая рекурсивная функция
# для расчета факториала

def factTR(n, a):

if (n == 0):

return a

return factTR(n - 1, n * a)

# Обертка поверх factTR

def fact(n):

return factTR(n, 1)

# Драйвер программы для тестирования
# выше функция

print(fact(5))

# Этот код добавлен
# от Smitha

C #

// C # код для хвостовой рекурсии

using System;

class GFG {

// Хвостовая рекурсивная функция

// рассчитать факториал

static int factTR(int n, int a)

{

if (n == 0)

return a;

return factTR(n - 1, n * a);

}

// Обертка поверх factTR

static int fact(int n)

{

return factTR(n, 1);

}

// Код драйвера

static public void Main ()

{

Console.WriteLine(fact(5));

}

// Этот код предоставлен Ajit.

PHP

<?php
// Хвостовая рекурсивная функция
// рассчитать факториал

function factTR($n, $a)

{

if ($n == 0) return $a;

return factTR($n - 1, $n * $a);

}

// Обертка поверх factTR

function fact($n)

{

return factTR($n, 1);

}

// Программа драйвера для тестирования
// вышеуказанная функция

echo fact(5);

// Этот код добавлен
// Смита
?>

Выход :

Следующие статьи на эту тему:
Устранение Хвоста
QuickSort Tail Call Optimization (Сокращение места наихудшего случая для регистрации n)

Ссылки:
http://en.wikipedia.org/wiki/Tail_call
http://c2.com/cgi/wiki?TailRecursion

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Хвост Рекурсия

0.00 (0%) 0 votes