Блог

Главная - C# язык программирования - Хвостовая рекурсия
You are currently viewing Хвостовая рекурсия

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

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

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

// An example of tail recursive function
void print(int n)
{
	if (n < 0) return;
	cout << " " << n;

	// The last executed statement is recursive call
	print(n-1);
}

// An example of tail recursive function
static 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 divyeh072019

# An example of tail recursive function
def prints(n):

	if (n < 0):
		return
	print(str(n), end=' ')

	# The last executed statement is recursive call
	prints(n-1)
	
	# This code is contributed by Pratham76
	# improved by ashish2021

// An example of tail recursive function
static 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 divyeshrabadiya07

Почему нас это волнует?

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

Может ли не-хвостовая рекурсивная функция быть записана как хвостовая рекурсивная для ее оптимизации?

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

#include<iostream>
using namespace std;

// A NON-tail-recursive function. The function is not tail
// recursive because the value returned by fact(n-1) is used in
// fact(n) and call to fact(n-1) is not the last thing done by fact(n)
unsigned int fact(unsigned int n)
{
	if (n == 0) return 1;

	return n*fact(n-1);
}

// Driver program to test above function
int main()
{
	cout << fact(5);
	return 0;
}

class GFG {
	
	// A NON-tail-recursive function.
	// The function is not tail
	// recursive because the value
	// returned by fact(n-1) is used
	// in fact(n) and call to fact(n-1)
	// is not the last thing done by
	// fact(n)
	static int fact(int n)
	{
		if (n == 0) return 1;
	
		return n*fact(n-1);
	}
	
	// Driver program
	public static void main(String[] args)
	{
		System.out.println(fact(5));
	}
}

// This code is contributed by Smitha.

# A NON-tail-recursive function.
# The function is not tail
# recursive because the value
# returned by fact(n-1) is used
# in fact(n) and call to fact(n-1)
# is not the last thing done by
# fact(n)
def fact(n):

	if (n == 0):
		return 1

	return n * fact(n-1)

# Driver program to test
# above function
print(fact(5))
# This code is contributed by Smitha.

using System;

class GFG {
	
	// A NON-tail-recursive function.
	// The function is not tail
	// recursive because the value
	// returned by fact(n-1) is used
	// in fact(n) and call to fact(n-1)
	// is not the last thing done by
	// fact(n)
	static int fact(int n)
	{
		if (n == 0)
			return 1;
	
		return n * fact(n-1);
	}
	
	// Driver program to test
	// above function
	public static void Main()
	{
		Console.Write(fact(5));
	}
}

// This code is contributed by Smitha

<?php
// A NON-tail-recursive function.
// The function is not tail
// recursive because the value
// returned by fact(n-1) is used in
// fact(n) and call to fact(n-1) is
// not the last thing done by fact(n)

function fact( $n)
{
	if ($n == 0) return 1;

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

	// Driver Code
	echo fact(5);

// This code is contributed by Ajit
?>

<script>

// A NON-tail-recursive function.
// The function is not tail
// recursive because the value
// returned by fact(n-1) is used
// in fact(n) and call to fact(n-1)
// is not the last thing done by
// fact(n)
function fact(n)
{
	if (n == 0)
		return 1;

	return n * fact(n - 1);
}

// Driver code
document.write(fact(5));

// This code is contributed by divyeshrabadiya07

</script>

Выход:

120

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

#include<iostream>
using namespace std;

// A tail recursive function to calculate factorial
unsigned factTR(unsigned int n, unsigned int a)
{
	if (n == 1) return a;

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

// A wrapper over factTR
unsigned int fact(unsigned int n)
{
return factTR(n, 1);
}

// Driver program to test above function
int main()
{
	cout << fact(5);
	return 0;
}

// Java Code for Tail Recursion

class GFG {
	
	// A tail recursive function
	// to calculate factorial
	static int factTR(int n, int a)
	{
		if (n == 0)
			return a;
	
		return factTR(n - 1, n * a);
	}
	
	// A wrapper over factTR
	static int fact(int n)
	{
		return factTR(n, 1);
	}

	// Driver code
	static public void main (String[] args)
	{
		System.out.println(fact(5));
	}
}

// This code is contributed by Smitha.

# A tail recursive function
# to calculate factorial
def fact(n, a = 1):

	if (n == 1):
		return a

	return fact(n - 1, n * a)

# Driver program to test
# above function
print(fact(5))

# This code is contributed
# by Smitha
# improved by Ujwal, ashish2021

// C# Code for Tail Recursion
using System;

class GFG {
	
	// A tail recursive function
	// to calculate factorial
	static int factTR(int n, int a)
	{
		if (n == 0)
			return a;
	
		return factTR(n - 1, n * a);
	}
	
	// A wrapper over factTR
	static int fact(int n)
	{
		return factTR(n, 1);
	}

	// Driver code
	static public void Main ()
	{
		Console.WriteLine(fact(5));
	}
}

// This code is contributed by Ajit.

<?php
// A tail recursive function
// to calculate factorial
function factTR($n, $a)
{
	if ($n == 0) return $a;

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

// A wrapper over factTR
function fact($n)
{
	return factTR($n, 1);
}

// Driver program to test
// above function
echo fact(5);

// This code is contributed
// by Smitha
?>

<script>

// Javascript Code for Tail Recursion

// A tail recursive function
// to calculate factorial
function factTR(n, a)
{
	if (n == 0)
		return a;

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

// A wrapper over factTR
function fact(n)
{
	return factTR(n, 1);
}

// Driver code
document.write(fact(5));

// This code is contributed by rameshtravel07
	
</script>

Выход:

120

Метки: