Recursion (Рекурсия)

ProgramBox

Recursion (Рекурсия)

Post author:admin
Запись опубликована:13 декабря, 2021
Post category:C# язык программирования / JavaScript язык программирования / PHP язык программирования / Python язык программирования

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

Процесс, в котором функция прямо или косвенно вызывает саму себя, называется рекурсией, а соответствующая функция называется рекурсивной функцией. Используя рекурсивный алгоритм, некоторые проблемы могут быть решены довольно легко.

Математическая интерпретация

Давайте рассмотрим проблему, с которой программист должен определить сумму первых n натуральных чисел, есть несколько способов сделать это, но самый простой подход-просто добавить числа, начинающиеся от 1 до n. Таким образом, функция просто выглядит так:

approach(1) – Simply adding one by one

f(n) = 1 + 2 + 3 +……..+ n

но есть и другой математический подход к представлению этого:

approach(2) – Recursive adding

f(n) = 1 n=1

f(n) = n + f(n-1) n>1

Существует простое различие между подходом (1) и подходом(2), и оно заключается в подход(2) функция “ f( ) ” сама по себе вызывается внутри функции, поэтому это явление называется рекурсией, а функция, содержащая рекурсию, называется рекурсивной функцией, в конце концов, это отличный инструмент в руках программистов для кодирования некоторых проблем намного проще и эффективнее.

Что такое базовое условие в рекурсии?

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

int fact(int n)
{
 if (n < = 1) // base case
 return 1;
 else 
 return n*fact(n-1); 
}

Если fact(10) будет вызван, он вызовет fact(9), fact(8), fact(7) и так далее, но число никогда не достигнет 100. Таким образом, базовый случай не достигнут. Если память в стеке будет исчерпана этими функциями, это приведет к ошибке переполнения стека.

В чем разница между прямой и косвенной рекурсией?

Функция fun называется прямой рекурсивной, если она вызывает ту же функцию fun. Функция fun называется косвенной рекурсивной, если она вызывает другую функцию, например fun_new, и fun_new прямо или косвенно вызывает fun. Различие между прямой и косвенной рекурсией показано в таблице 1.

// An example of direct recursion
void directRecFun()
{
 // Some code....

 directRecFun();

 // Some code...
}

// An example of indirect recursion
void indirectRecFun1()
{
 // Some code...

 indirectRecFun2();

 // Some code...
}
void indirectRecFun2()
{
 // Some code...

 indirectRecFun1();

 // Some code...
}

В чем разница между хвостатой и нехвостой рекурсией?

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

Как выделяется память для различных вызовов функций в рекурсии?

Когда какая-либо функция вызывается из main(), ей выделяется память в стеке. Рекурсивная функция вызывает саму себя, память для вызываемой функции выделяется поверх памяти, выделенной вызывающей функции, и для каждого вызова функции создается другая копия локальных переменных. Когда достигается базовый случай, функция возвращает свое значение функции, которой она вызывается, память освобождается, и процесс продолжается.
Давайте рассмотрим пример того, как работает рекурсия, взяв простую функцию.

// A C++ program to demonstrate working of
// recursion
#include <bits/stdc++.h>
using namespace std;

void printFun(int test)
{
	if (test < 1)
		return;
	else {
		cout << test << " ";
		printFun(test - 1); // statement 2
		cout << test << " ";
		return;
	}
}

// Driver Code
int main()
{
	int test = 3;
	printFun(test);
}

// A Java program to demonstrate working of
// recursion
class GFG {
	static void printFun(int test)
	{
		if (test < 1)
			return;
		else {
			System.out.printf("%d ", test);
			printFun(test - 1); // statement 2
			System.out.printf("%d ", test);
			return;
		}
	}

	// Driver Code
	public static void main(String[] args)
	{
		int test = 3;
		printFun(test);
	}
}

// This code is contributed by
// Smitha Dinesh Semwal

# A Python 3 program to
# demonstrate working of
# recursion


def printFun(test):

	if (test < 1):
		return
	else:

		print(test, end=" ")
		printFun(test-1) # statement 2
		print(test, end=" ")
		return

# Driver Code
test = 3
printFun(test)

# This code is contributed by
# Smitha Dinesh Semwal

// A C# program to demonstrate
// working of recursion
using System;

class GFG {

	// function to demonstrate
	// working of recursion
	static void printFun(int test)
	{
		if (test < 1)
			return;
		else {
			Console.Write(test + " ");

			// statement 2
			printFun(test - 1);

			Console.Write(test + " ");
			return;
		}
	}

	// Driver Code
	public static void Main(String[] args)
	{
		int test = 3;
		printFun(test);
	}
}

// This code is contributed by Anshul Aggarwal.

<?php
// PHP program to demonstrate
// working of recursion

// function to demonstrate
// working of recursion
function printFun($test)
{
	if ($test < 1)
		return;
	else
	{
		echo("$test ");
		
		// statement 2
		printFun($test-1);
		
		echo("$test ");
		return;
	}
}

// Driver Code
$test = 3;
printFun($test);

// This code is contributed by
// Smitha Dinesh Semwal.
?>

<script>

// JavaScript program to demonstrate working of
// recursion

function printFun(test)
	{
		if (test < 1)
			return;
		else {
			document.write(test + " ");
			printFun(test - 1); // statement 2
			document.write(test + " ");
			return;
		}
	}

// Driver code
	let test = 3;
	printFun(test);

</script>

Выход :

3 2 1 1 2 3

Когда printFun(3) вызывается из main(), память выделяется для printFun(3) и локальная переменная test инициализируется до 3, а операторы 1-4 помещаются в стек, как показано на диаграмме ниже. Сначала он печатает «3». В заявлении 2, printFun(2) вызывается и память выделяется для printFun(2) и локальная переменная test инициализируется значением 2, а операторы 1-4 помещаются в стек. Аналогично, printFun(2) звонки printFun(1) и printFun(1) звонки printFun(0). printFun(0) переходит к оператору if и возвращается в printFun(1). Остальные заявления о printFun(1) выполняются, и он возвращается в printFun(2) и так далее. На выходных данных выводятся значения от 3 до 1, а затем от 1 до 3. Стек памяти показан на приведенной ниже диаграмме.

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

Задача 1:

Напишите программу и рекуррентное соотношение, чтобы найти ряд Фибоначчи n, где n>2 . >
Математическое уравнение:

n if n == 0, n == 1; 
fib(n) = fib(n-1) + fib(n-2) otherwise;

Рекуррентное Отношение:

T(n) = T(n-1) + T(n-2) + O(1)

Рекурсивная программа:

Input: n = 5  Output:
Fibonacci series of 5 numbers is : 0 1 1 2 3

Реализация:

// C++ code to implement Fibonacci series
#include <bits/stdc++.h>
using namespace std;

// Function for fibonacci

int fib(int n)
{
	// Stop condition
	if (n == 0)
		return 0;

	// Stop condition
	if (n == 1 || n == 2)
		return 1;

	// Recursion function
	else
		return (fib(n - 1) + fib(n - 2));
}

// Driver Code
int main()
{
	// Initialize variable n.
	int n = 5;
	cout<<"Fibonacci series of 5 numbers is: ";

	// for loop to print the fibonacci series.
	for (int i = 0; i < n; i++)
	{
		cout<<fib(i)<<" ";
	}
	return 0;
}

// C code to implement Fibonacci series
#include <stdio.h>

// Function for fibonacci
int fib(int n)
{
	// Stop condition
	if (n == 0)
		return 0;

	// Stop condition
	if (n == 1 || n == 2)
		return 1;

	// Recursion function
	else
		return (fib(n - 1) + fib(n - 2));
}

// Driver Code
int main()
{
	// Initialize variable n.
	int n = 5;
	printf("Fibonacci series "
		"of %d numbers is: ",
		n);

	// for loop to print the fibonacci series.
	for (int i = 0; i < n; i++) {
		printf("%d ", fib(i));
	}
	return 0;
}

// Java code to implement Fibonacci series
import java.util.*;

class GFG
{

// Function for fibonacci
static int fib(int n)
{
	// Stop condition
	if (n == 0)
		return 0;

	// Stop condition
	if (n == 1 || n == 2)
		return 1;

	// Recursion function
	else
		return (fib(n - 1) + fib(n - 2));
}

// Driver Code
public static void main(String []args)
{

	// Initialize variable n.
	int n = 5;
	System.out.print("Fibonacci series of 5 numbers is: ");

	// for loop to print the fibonacci series.
	for (int i = 0; i < n; i++)
	{
		System.out.print(fib(i)+" ");
	}
}
}

// This code is contributed by rutvik_56.

# Python code to implement Fibonacci series

# Function for fibonacci
def fib(n):

	# Stop condition
	if (n == 0):
		return 0

	# Stop condition
	if (n == 1 or n == 2):
		return 1

	# Recursion function
	else:
		return (fib(n - 1) + fib(n - 2))


# Driver Code

# Initialize variable n.
n = 5;
print("Fibonacci series of 5 numbers is :",end=" ")

# for loop to print the fibonacci series.
for i in range(0,n):
	print(fib(i),end=" ")

using System;

public class GFG
{

// Function for fibonacci
static int fib(int n)
{

	// Stop condition
	if (n == 0)
	return 0;

	// Stop condition
	if (n == 1 || n == 2)
	return 1;

	// Recursion function
	else
	return (fib(n - 1) + fib(n - 2));
}

// Driver Code
static public void Main ()
{

	// Initialize variable n.
	int n = 5;
	Console.Write("Fibonacci series of 5 numbers is: ");

	// for loop to print the fibonacci series.
	for (int i = 0; i < n; i++)
	{
	Console.Write(fib(i) + " ");
	}
}
}

// This code is contributed by avanitrachhadiya2155

<script>
// JavaScript code to implement Fibonacci series

// Function for fibonacci
function fib(n)
{
// Stop condition
if(n == 0)
	return 0;
	
// Stop condition
if(n == 1 || n == 2)
	return 1;
// Recursion function
else
	return fib(n-1) + fib(n-2);
}

// Initialize variable n.
let n = 5;

document.write("Fibonacci series of 5 numbers is: ");

// for loop to print the fibonacci series.
for(let i = 0; i < n; i++)
{
	document.write(fib(i) + " ");
}

</script>

Выход

Fibonacci series of 5 numbers is: 0 1 1 2 3

Вот рекурсивное дерево для ввода 5, которое показывает четкую картину того, как большую проблему можно разделить на меньшие.
fib(n) является функцией Фибоначчи. Временная сложность данной программы может зависеть от вызова функции.

fib(n) -> level CBT (UB) -> 2^n-1 nodes -> 2^n function call -> 2^n*O(1) -> T(n) = O(2^n)

В лучшем случае.

T(n) = θ(2^n\2)

Работающий:

Проблема 2:

Напишите программу и рекуррентное соотношение, чтобы найти факториал n, где n>2 .

Математическое уравнение:

1 if n == 0 or n == 1;  f(n) = n*f(n-1) if n> 1;

Рекуррентное отношение:

T(n) = 1 for n = 0 T(n) = 1 + T(n-1) for n > 0

Рекурсивная программа:

Input: n = 5

Выход:

factorial of 5 is: 120

Реализация:

// C++ code to implement factorial
#include <bits/stdc++.h>
using namespace std;

// Factorial function
int f(int n)
{
	// Stop condition
	if (n == 0 || n == 1)
		return 1;

	// Recursive condition
	else
		return n * f(n - 1);
}

// Driver code
int main()
{
	int n = 5;
	cout<<"factorial of "<<n<<" is: "<<f(n);
	return 0;
}

// C code to implement factorial
#include <stdio.h>

// Factorial function
int f(int n)
{
	// Stop condition
	if (n == 0 || n == 1)
		return 1;

	// Recursive condition
	else
		return n * f(n - 1);
}

// Driver code
int main()
{
	int n = 5;
	printf("factorial of %d is: %d", n, f(n));
	return 0;
}

// Java code to implement factorial
public class GFG
{

// Factorial function
static int f(int n)
{

	// Stop condition
	if (n == 0 || n == 1)
	return 1;

	// Recursive condition
	else
	return n * f(n - 1);
}

// Driver code
public static void main(String[] args)
{
	int n = 5;
	System.out.println("factorial of " + n + " is: " + f(n));
}
}

// This code is contributed by divyesh072019.

# Python3 code to implement factorial

# Factorial function
def f(n):

	# Stop condition
	if (n == 0 or n == 1):
		return 1;

	# Recursive condition
	else:
		return n * f(n - 1);


# Driver code
if __name__=='__main__':

	n = 5;
	print("factorial of",n,"is:",f(n))
	
	# This code is contributed by pratham76.

// C# code to implement factorial
using System;
class GFG {

// Factorial function
static int f(int n)
{
	// Stop condition
	if (n == 0 || n == 1)
	return 1;

	// Recursive condition
	else
	return n * f(n - 1);
}

// Driver code
static void Main()
{
	int n = 5;
	Console.WriteLine("factorial of " + n + " is: " + f(n));
}
}

// This code is contributed by divyeshrabadiya07.

<script>
// JavaScript code to implement factorial

// Factorial function
function f(n)
{
// Stop condition
if(n == 0 || n == 1)
	return 1;
	
// Recursive condition
else
	return n*f(n-1);
}

// Initialize variable n.
let n = 5;
document.write("factorial of "+ n +" is: " + f(n));

// This code is contributed by probinsah.
</script>

Выход:

factorial of 5 is: 120

Работающий:

Каковы недостатки рекурсивного программирования по сравнению с итеративным?

Обратите внимание, что как рекурсивные, так и итеративные программы обладают одинаковыми способностями к решению проблем, т. е. Каждая рекурсивная программа может быть написана итеративно, и наоборот также верно. Рекурсивная программа требует большего пространства, чем итеративная программа, поскольку все функции будут оставаться в стеке до тех пор, пока не будет достигнут базовый вариант. Он также требует большего времени из-за вызовов функций и накладных расходов на возврат.

В чем преимущества рекурсивного программирования перед итеративным программированием?

Рекурсия обеспечивает чистый и простой способ написания кода. Некоторые проблемы по своей сути рекурсивны, как обход деревьев, и так далее. Для решения таких задач предпочтительно писать рекурсивный код. Мы также можем писать такие коды итеративно с помощью структуры данных стека.

Метки: Recursion (Рекурсия)

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

Математическая интерпретация

Что такое базовое условие в рекурсии?

В чем разница между прямой и косвенной рекурсией?

В чем разница между хвостатой и нехвостой рекурсией?

Как выделяется память для различных вызовов функций в рекурсии?

Выход :

Задача 1:

Реализация:

Выход

Работающий:

Проблема 2:

Математическое уравнение:

Рекуррентное отношение:

Рекурсивная программа:

Выход:

Реализация:

Выход:

Работающий:

Каковы недостатки рекурсивного программирования по сравнению с итеративным?

В чем преимущества рекурсивного программирования перед итеративным программированием?

Вам также может понравиться

Python – Извлекает значения i-го столбца из значений j-го столбца

Циклы и управляющие операторы (continue, break и pass) в Python

Параметр Python | sep в print()