Рекурсию не очень просто понять при первом знакомстве, но без ее понимания в разработке будет тяжело. В этом материале рассмотрим:
- Рекурсивную функцию поиска факториала.
- Как рекурсивные функции работают в коде.
- Действительно ли рекурсивные функции выполняют свои задачи лучше итеративных?
Рекурсивные функции
Рекурсивная функция — это та, которая вызывает сама себя.
В качестве простейшего примера рассмотрите следующий код:
def factorial_recursive(n):
if n == 1:
return n
else:
return n*factorial_recursive(n-1)
Вызывая рекурсивную функцию здесь и передавая ей целое число, вы получаете факториал этого числа (n!).
Вкратце о факториалах
Факториал числа — это число, умноженное на каждое предыдущее число вплоть до 1.
Например, факториал числа 7:
7! = 7*6*5*4*3*2*1 = 5040
Вывести факториал числа можно с помощью функции:
num = 3
print(f»Факториал это «)
#41. Рекурсивные функции | Python для начинающих
Эта функция выведет: «Факториал 3 это 6». Еще раз рассмотрим эту рекурсивную функцию:
def factorial_recursive(n): .
По аналогии с обычной функцией имя рекурсивной указывается после def , а в скобках обозначается параметр n :
def factorial_recursive(n): if n == 1: return n else: return n*factorial_recursive(n-1)
Благодаря условной конструкции переменная n вернется только в том случае, если ее значение будет равно 1. Это еще называют условием завершения. Рекурсия останавливается в момент удовлетворения условиям.
def factorial_recursive(n): if n == 1: return n else: return n*factorial_recursive(n-1)
В коде выше выделен фрагмент самой рекурсии. В блоке else условной конструкции возвращается произведение n и значения этой же функции с параметром n-1 .
Это и есть рекурсия. В нашем примере это так сработало:
3 * (3-1) * ((3-1)-1) # так как 3-1-1 равно 1, рекурсия остановилась
Детали работы рекурсивной функции
Чтобы еще лучше понять, как это работает, разобьем на этапы процесс выполнения функции с параметром 3.
Для этого ниже представим каждый экземпляр с реальными числами. Это поможет «отследить», что происходит при вызове одной функции со значением 3 в качестве аргумента:
# Первый вызов
factorial_recursive(3):
if 3 == 1:
return 3
else:
return 3*factorial_recursive(3-1)
# Второй вызов
factorial_recursive(2):
if 2 == 1:
return 2
else:
return 2*factorial_recursive(2-1)
# Третий вызов
factorial_recursive(1):
if 1 == 1:
return 1
else:
return 1*factorial_recursive(1-1)
Рекурсивная функция не знает ответа для выражения 3*factorial_recursive(3–1) , поэтому она добавляет в стек еще один вызов.
Как работает рекурсия
/ factorial_recursive(1) — последний вызов || factorial_recursive(2) — второй вызов || factorial_recursive(3) — первый вызов
Выше показывается, как генерируется стек. Это происходит благодаря процессу LIFO (last in, first out, «последним пришел — первым ушел»). Как вы помните, первые вызовы функции не знают ответа, поэтому они добавляются в стек.
41 Рекурсия в Python. Рекурсивная функция Часть 1
Но как только в стек добавляется вызов factorial_recursive(1) , для которого ответ имеется, стек начинает «разворачиваться» в обратном порядке, выполняя все вычисления с реальными значениями. В процессе каждый из слоев выпадает в процессе.
- factorial_recursive(1) завершается, отправляет 1 в
- factorial_recursive(2) и выпадает из стека.
- factorial_recursive(2) завершается, отправляет 2*1 в
- factorial_recursive(3) и выпадает из стека. Наконец, инструкция else здесь завершается, возвращается 3 * 2 = 6, и из стека выпадает последний слой.
Рекурсия в Python имеет ограничение в 3000 слоев.
>>> import sys
>>> sys.getrecursionlimit()
3000
Рекурсивно или итеративно?
Каковы же преимущества рекурсивных функций? Можно ли с помощью итеративных получить тот же результат? Когда лучше использовать одни, а когда — другие?
Важно учитывать временную и пространственную сложности. Рекурсивные функции занимают больше места в памяти по сравнению с итеративными из-за постоянного добавления новых слоев в стек в памяти. Однако их производительность куда выше.
Рекурсия может быть медленной, если реализована неправильно
Тем не менее рекурсия может быть медленной, если ее неправильно реализовать. Из-за этого вычисления будут происходить чаще, чем требуется.
Написание итеративных функций зачастую требуется большего количества кода. Например, дальше пример функции для вычисления факториала, но с итеративным подходом. Выглядит не так изящно, не правда ли?
def factorial_iterative(num):
factorial = 1
if num < 0:
print(«Факториал не вычисляется для отрицательных чисел»)
else:
for i in range (1, num + 1):
factorial = factorial*i
print(f»Факториал это «)
Источник: pythonru.com
Рекурсия в Java
Чтобы понять, что такое рекурсия, нужно понять, что такое рекурсия. На самом деле, в понимании таких функций нет ничего сложного, нужно только один раз хорошо в этом разобраться. И попрактиковаться, если речь идёт о программировании. Рекурсия встречается не только в программировании, но и в реальной жизни. Возьми в руки зеркало и встань напротив другого зеркала.
Отражение отражения отразится в отражении и так далее. Ты увидишь бесконечное количество отражений, уходящих в бесконечность. Больше о “реальной” рекурсии ты можешь найти в статье “Дню Сурка посвящается…” Возвратимся из реального мира к будням программиста. Простое определение: рекурсивные функции в java – это функции, которые вызывают сами себя. Приведу очень простой и очень вредный пример:
public void recursionFucn()
- Базис рекурсии – условие выхода из блока рекурсивных вызовов – базисное решение задачи, при условиях, когда нет необходимости вызывать рекурсию.
- Шаг рекурсии – вызов функцией самой себя при изменении параметров.
private int fact(int n) < int result = 1; for (int i = 1; i return result; >
Добавим проверку того, что число положительное и целое, и отдельно проверку для нуля.
private int fact(int n) < if (n < 0) < System.out.println(«Зачем тебе факториал из отрицательного числа?»); return null; >int result = 1; if (n == 0) < return result; >for (int i = 1; i return result; >
Теперь приведу код метода для рекурсивного решения этой задачи:
private int factorial(int n) < int result = 1; if (n == 1 || n == 0) < return result; >result = n * factorial(n-1); return result; >
Посмотрим результаты вывода для вызовов:
System.out.println(factorial(0)); System.out.println(factorial(1)); System.out.println(factorial(2)); System.out.println(factorial(3)); System.out.println(factorial(4)); System.out.println(factorial(5)); System.out.println(factorial(6));
Получим ожидаемые значения:
1 1 2 6 24 120 720
Добавим красивый вывод и вычислим фаториал для числа побольше:
private int factorial(int n) < int result = 1; if (n == 0) < System.out.print(» = «); return result; >if (n == 1) < System.out.print(» * 1 = «); return result; >System.out.print(n); if (n != 2) < System.out.print(» * «); >result = n * factorial(n-1); return result; > System.out.println(factorial(15) + «!»);
Получим: 15 * 14 * 13 * 12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 = 1 307 674 368 000! В данном случае применение рекурсивной функции оправдано и безопасно. Мы четко обозначили условие выхода из рекурсивного блока, и мы уверены в том, что он достижим: мы вводим целое неотрицательное число, в случае, если число равно нулю или единице — возвращаем результат, если же число больше — умножаем результат на функцию от числа n-1 . На примере факториала от трех:
factorial(3) внутри себя выполнит следующее: result = 3 * factorial(2); (рекурсивный вызов) factorial(2) внутри себя выполнит следующее: result = 2 * factorial(1); (рекурсивный вызов) factorial(1) вернет 1 (базис рекурсии) factorial(2) вернет 2 * 1 factorial(3) вернет 3 * 2 * 1
По поводу осторожности применения: в чем уязвимость этой функции? Если дать методу в качестве параметра отрицательное число, то проверка
if (n == 1 || n == 0)
не имеет смысла и мы уйдем в бесконечный цикл вызовов методом самого себя. Стоит добавить проверку на неотрицательность:
if (n
И все будет хорошо.
В чем преимущество одного метода перед другим?
Кажется, что большой разницы нет, но на самом деле множество рекурсивных вызовов негативно скажется на производительности и потребляемой памяти: стек вызовов – практически неконтролируемый ресурс и при разных условиях вызова одной и той же рекурсивной функции, мы можем получить или не получить проблемы, связанные с этим ресурсом. Практически все задачи, решаемые с помощью итераций (циклов типа for-each ), можно решить и рекурсивно.
Преимущество рекурсии в читаемости и простоте написания, о недостатках мы говорили выше: возможность «выстрелить себе в ногу» неиллюзорна. Еще более осторожным надо быть при использовании так называемой «сложной рекурсии»: Функция A() вызовет функцию B() , вызывающую функцию A() .Для решения таких задач необходимо полное понимание того, как работает рекурсия. Пример такой задачи: вычисление значения x^n/(n!) . Факториал, как мы обсуждали выше, определен на множестве неотрицательных целых чисел. Напоследок приведу код решения. Сложная рекурсия будет состоять из двух методов:
private double calculate(int x, int n) < return power(x, n) / n; >private double power(int x, int n)
Для входа в рекурсию используется метод calculate , вызывающий метод power , в свою очередь вызывающий метод calculate . Базис рекурсии мы обозначили в методе power:
if (n == 1) return x;
Там же определен и шаг рекурсии:
return x * calculate(x, n — 1);
- Любое число, кроме нуля, в нулевой степени равно 1 . Если n = 0 , то n! = 1 . Нужно вернуть 1 .
- Нуль в любой степени равен нулю.
- Неопределенность типа 0^0 рассматривать не будем и примем такие входные данные за невалидные.
private double calculate(int x, int n) throws ArithmeticException < if (x == 0 n == 0) < throw new ArithmeticException(«Невалидные входные данные: Неопределенность типа 0^0»); >if (n < 0) < throw new ArithmeticException(«Невалидные входные данные: Факториал из отрицательного числа!»); >if (n == 0) < return 1; >if (x == 0) < return 0; >if (x == 0) < return 0; >return power(x, n) / n; > private double power(int x, int n)
Ну, и при вызове функции нужно не забыть поймать ошибку:
try < System.out.println(calculate(x, n)); >catch (ArithmeticException e)
Источник: javarush.com
Рекурсия
Рекурсия — состоит в определении, описании, изображении какого-либо объекта или процесса внутри самого этого объекта или процесса. Это ситуация, когда объект является частью самого себя.
Процедура или функция может содержать вызов других процедур или функций. В том числе процедура может вызвать саму себя. Компьютер лишь последовательно выполняет команды и, если встречается вызов процедуры, просто начинает выполнять эту процедуру. Без разницы, какая процедура дала команду это делать.
1
2
3
4
5
6
7
8
9
10
11
12
#include
using namespace std;
void func( int num)
if (num > 0) func(num — 1);
cout >
int main()
func(3);
cin.get(); return 0;
>
Процедура func() вызывается с параметром 3. В ней содержится вызов процедуры func() с параметром 2. Предыдущий вызов еще не завершился, поэтому создается еще одна процедура и до окончания ее работы func(3) свою работу приостанавливает. Процесс вызова заканчивается, когда параметр равен 0. В этот момент одновременно выполняются 4 экземпляра процедуры.
Количество одновременно выполняемых процедур называют глубиной рекурсии .
Последняя вызванная процедура func(0) выведет число 0 и закончит свою работу. После этого управление возвращается к процедуре, которая ее вызвала: func(1) и выводится число 1. И так далее пока не завершатся все процедуры.
Важным и обязательным моментом в формировании рекурсивной процедуры является базис рекурсии. Базис рекурсии определяет условие выхода из рекурсии. Как правило, в качестве базиса записывается некий простейший случай, при котором ответ получается сразу, без использования рекурсии.
Существует такое понятие как шаг рекурсии или рекурсивный вызов . В случае, когда рекурсивная функция вызывается для решения сложной задачи (не базового случая) выполняется некоторое количество рекурсивных вызовов или шагов, с целью сведения задачи к более простой. И так до тех пор пока не получим базовое решение.
Сложная рекурсия
Возможна чуть более сложная схема: функция A вызывает функцию B, а та в свою очередь вызывает A. Это называется сложной рекурсией . При этом оказывается, что описываемая первой процедура должна вызывать еще не описанную. Чтобы это было возможно, требуется использовать описание функции B до ее использования.
Пример : вычислить значение выражения
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include
using namespace std;
int pow( int , int ); // описание сигнатуры
double calc( int x, int n)
return ( double )pow(x, n) / n; // вызов функции pow
>
int pow( int x, int n)
if (n == 1) return x;
return x*calc(x, n — 1); // вызов функции calc
>
int main()
int n, x;
cout > n;
cout > x;
double a = calc(x, n); // вызов рекурсивной функции
cout cin.get(); cin.get();
return 0;
>
Результат выполнения
Префиксная и постфиксная форма записи
Если процедура вызывает сама себя, то, по сути, это приводит к повторному выполнению содержащихся в ней инструкций, что аналогично работе цикла. При этом различают префиксную и постфиксную формы записи.
Источник: prog-cpp.ru