Проще говоря, рекурсия означает разбиение сложной задачи на более простые части, чтобы получить базовый вариант, который затем возвращает значения до тех пор, пока не будет получен окончательный результат.
Давайте разберемся с этим на примере
В этом коде мы находим степени любого натурального числа.
Решение открытого класса {
public static int power(int x, int n) {
if(n==0){
return 1;
}
int shortAns=power(x ,n-1)*x;
вернуть короткий ответ;
}
}
В приведенном выше коде мы сначала сосредоточимся на поиске простой проблемы, т.е. короткий ответ
Основная идея заключается в том, что если мы хотим решить x^n, мы должны получить результат подзадачи x^n-1. Предположим, мы знаем результат x^n-1
Тогда x^n=x*(x^n-1)
Мы просто вызываем функцию для вычисления результата подзадачи, как мы это делали в приведенном выше коде, power(x,n-1)*x
Если мы запустим это, то он будет продолжать делить задачу на более простые навсегда, т.е. бесконечный цикл
Чтобы предотвратить это, нам нужно иметь базовый случай, из которого он достигнет простейшей проблемы и вернет некоторое значение вызывающей (рекурсивной) функции. Когда рекурсивная функция вычисляет окончательное значение, она возвращает результат.
