Что такое рекурсия?
Рекурсия в информатике — это функция, которая вызывает себя до тех пор, пока не будет выполнено базовое условие.
Что такое базовое условие в рекурсии?
В рекурсивной программе предоставляется решение базового случая, а решение большей проблемы выражается в терминах меньших проблем.
Стек вызовов
Рекурсивные функции используют то, что называется «стеком вызовов». Когда программа вызывает функцию, эта функция помещается на вершину стека вызовов. Это похоже на стопку книг. Вы добавляете вещи по одной. Затем, когда вы готовы что-то снять, вы всегда снимаете верхний предмет.
например, возьмем эту программу:
#include ‹stdio.h›
поплавок _pow_recursion (поплавок x, поплавок y)
{
if (y == 0)
возврат (1);
if (y < 0)
return (_pow_recursion(x, y + 1) / x);
return (_pow_recursion(x, y — 1) * x);
}
интервал основной (пустой)
{
плавающий результат;
результат = _pow_recursion (2, 2);
printf(“%.2f\n”, результат);
возврат (0);
}
Обратите внимание, что базовое условие здесь if (y == 0), если это условие выполнено, цикл остановится. Правильное определение базового условия необходимо, чтобы избежать бесконечного цикла вызовов функций. Подробно изучив цикл, можно увидеть, что при вызове этой функции с кодом:
return (_pow_recursion (x, y — 1) * x);
Происходит что-то похожее на разворот, то есть увеличивая или уменьшая «y» на 1, чтобы добраться до 0, в итоге будут производиться итерации, которые позволят в какой-то момент приблизиться к выполнению базового условия (y == 0) .
Наконец, когда условие выполнено, программа начинает возвращать значение, и для базового случая возвращаемое значение будет 1. С этим возвращаемым значением оно добавляется к предыдущему возврату, который разделит его на x и завершите его, вернувшись к функции, пока не вернетесь к своему первому экземпляру, в котором функция была вызвана в первый раз. Графическим описанием предыдущего процесса является этот рисунок:
Спасибо за прочтение этого поста, надеюсь, он будет полезен для понимания темы.
