§5.10. Стековые диаграммы рекурсивных вызовов
Разберемся, какой путь проделывает поток выполнения в процессе вычисления факториала. Изобразим стековую диаграмму для вызова fact (3).
11 Имейте ввиду, что функция может не справиться со слишком большими значениями (например, при п > 1000). Это связано с ограничениями, присущими вычислительной технике. Этот случай мы разберем в последующих разделах.
60
Ревизия: 170
Логические выражения, условия и рекурсия
fact(1-1)*1
eturn|1*1*2
*3
Итак, теперь все должно быть понятно. До добавления условия возврата 1 при х == О стек вызовов рос бесконечно, поэтому возникало исключение. Когда же мы добавили это условие, все встало на свои места: сначала стек рекурсивных вызовов увеличивается, пока не дойдет до граничного значения параметра, а затем начинает опустошаться - поток выполнения начинает возврат обратно в главную программу, собирая ответ по кусочкам (кстати, термин «рекурсия» происходит от позднелатинского «recursio» - «возвращение»). При этом результат каждого вызова передается в тело функции, находящейся в стеке на уровень ниже, где используется в дальнейших вычислениях. В результате этого трюка мы и получаем ответ.
Можно ли улучшить этот алгоритм? Вы, наверное, обратили внимание, что на втором шаге возврата мы умножаем 1 на 1 - бессмысленная операция. Кроме того, каждый рекурсивный вызов требует выделения некоторого количества памяти, да и сам вызов занимает какое-то время.
Вариант решения: изменить условие, при котором будет начинаться возврат на х == 1. Проверим его с помощью граничных значений: что произойдет при вызове fact (0) ? Программа зациклится. Попробуем так:
def fact(n): |
|
|
|
|
if type(n) != type(l) |
or n < |
0: |
# Проверка |
корректности п |
return None |
|
|
|
|
if n == 1 or n == 0: |
|
|
|
|
return 1 |
|
|
|
|
return fact(n-l)*n |
|
|
|
|
Такой подход позволит избежать лишний рекурсивный вызов, но увеличивается сложность проверяемого условия, что сказываете на скорости выполнения программы. Конечно, на современных компьютерах разница не заметна, но это противоречие встречается довольно часто: программистам приходится выбирать между экономией памяти и скоростью выполнения. Обычно в такой ситуации приблизительно оценивается, как часто выполняется блок кода - от этого зависит влияние его усложнения на общее время выполнения программы.
Упражнение. Как вы думаете, стоит ли в случае функции fact () производить лишнюю проверку? Объясните почему.
61
Ревизия: 170
Логические выражения, условия и рекурсия