ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
Long factorial(int n){ if (n <= 1) return 1; // выход из рекурсии – терминальная ветвь else return n * factorial(n-1); } При n = 5 эта функция будет работать следующим образом: factorial:= 5 * factorial(4) Factorial(3) Factorial(2) Factorial(1) 5 * 4 * 3 * 2 * 1 = 120 В данном случае реализована так называемая нисходящая рекурсия: вызов factorial(5) означает, что функция factorial вызывает себя раз за разом: factorial(4), factorial(3), … – до тех пор, пока не будет достигнута терминальная ситуация – ситуация окончания рекурсии. При каждом вызове текущие вычисления откладываются, локальные переменные и адрес возврата остаются в стеке. Терминальная ситуация factorial = 1 достигается при n = 1. При этом рекурсивный спуск заканчивается, начинается рекурсивный возврат изо всех вызванных в данный момент копий функции: начинает строиться ответ n*factorial(n-1). Сохраненные локальные параметры выбираются из стека в обратной последовательности, а получаемые промежуточные результаты: 1*1, 2*1, 3*2*1, 4*3*2*1, 5*4*3*2*1 – передаются вызывающим функциям. Рекурсивная функция, вычисляющая n- й член ряда Фибоначчи, может иметь вид: Int fibo(int n) { if ((n == 1) || (n == 2)) return 1; // выход из рекурсии else return fibo(n-2) + fibo(n-1); } Примеры 1. Составить функцию, рекурсивно определяющую значение биномиального коэффициента при 0<m<n по формулам: = = 1, = + Не нашли, что искали? Воспользуйтесь поиском:
|