Рекурсия. Что такое рекурсия
 Скачать 0.59 Mb.
|
|
Рекурсия Что такое рекурсия?Натуральные числа: 1 – натуральное число если – натуральное число, то – натуральное число индуктивное определение Рекурсия — это способ определения множества объектов через само это множество на основе заданных простых базовых случаев. Числа Фибоначчи: при 1, 1, 2, 3, 5, 8, 13, 21, 34, … ФракталыФракталы – геометрические фигуры, обладающие самоподобием. Треугольник Серпинского: Ханойские башни1 2 3 за один раз переносится один диск класть только меньший диск на больший третий стержень вспомогательный перенести (n-1, 1, 2) 1 -> 3 перенести (n-1, 2, 3) перенести (n, 1, 3) def Hanoi ( n, k, m ): p = 6 - k - m Hanoi ( n-1, k, p ) print ( k, "->", m ) Hanoi ( n-1, p, m ) номер вспомогательного стержня (1+2+3=6!) сколько откуда куда Что плохо? ? Рекурсия никогда не остановится! ! рекурсия рекурсия Рекурсивная процедура (функция) — это процедура (функция), которая вызывает сама себя напрямую или через другие процедуры и функции. def Hanoi ( n, k, m ): p = 6 - k - m Hanoi ( n-1, k, p ) print ( k, "->", m ) Hanoi ( n-1, p, m ) if n == 0: return условие выхода из рекурсии # основная программа Hanoi( 4, 1, 3 ) Вычисление суммы цифр числаdef sumDig ( n ): sum = n % 10 if n >= 10: sum += sumDig ( n // 10 ) return sum Где условие окончания рекурсии? ? рекурсивный вызов sumDig( 1234 ) 4 + sumDig( 123 ) 4 + 3 + sumDig( 12 ) 4 + 3 + 2 + sumDig( 1 ) 4 + 3 + 2 + 1 последняя цифра Алгоритм ЕвклидаАлгоритм Евклида. Чтобы найти НОД двух натуральных чисел, нужно вычитать из большего числа меньшее до тех пор, пока меньшее не станет равно нулю. Тогда второе число и есть НОД исходных чисел. def NOD ( a, b ): if a == 0 or b == 0: if a > b: return NOD( a - b, b ) else: return NOD( a, b – a ) return a + b; рекурсивные вызовы условие окончания рекурсии Как работает рекурсия?def Fact(N): print ( "->", N ) if N <= 1: F = 1 else: F = N * Fact ( N – 1 ) print ( "<-", N ) return F -> N = 3 -> N = 2 -> N = 1 <- N = 1 <- N = 2 <- N = 3 Как сохранить состояние функции перед рекурсивным вызовом? ? Факториал: СтекСтек – область памяти, в которой хранятся локальные переменные и адреса возврата. SP SP
SP
SP Fact(3) Fact(2) Fact(1) значение параметра адрес возврата локальная переменная Рекурсия – «за» и «против»с каждым новым вызовом расходуется память в стеке (возможно переполнение стека) затраты на выполнение служебных операций при рекурсивном вызове программа становится более короткой и понятной возможно переполнение стека замедление работы Любой рекурсивный алгоритм можно заменить нерекурсивным! ! def Fact ( n ): f = 1 for i in range(2,n+1): f *= i return f итерационный алгоритм |