Литература: Осн. [7,8]
Контрольные вопросы:
Как вызвать функий?
Что такое оператор def?
Что такое функции?
Python. Лекция 14.
Тема: Рекурсия и двумерные массивы
Цель: Изучить рекурсию и двумерный массив и их применение
План:
Рекурсия
Массивы
Как создаются матрицы в Python?
Базовые операции в NumPy Форма матрицы в Python Операции со срезами matrix в Python
Рекурсия в программировании — это возможность дать определение функции, используя в процессе саму определяемую функцию. В математике многие функции определены именно таким образом, поэтому и большинство языков программирования берёт на вооружение этот подход. Python здесь не является исключением: обычно в определении функции вы можете использовать только определения, данные ранее, но есть одно исключение — функция в своём теле может вызывать себя. Выглядит это так:
def factorial(n):
if n <= 0:
return 1
return n * factorial(n - 1)
Эта функция, вычисляет факториал числа n через умножение числа на факториал числа n - 1.
def short_story():
print("У попа была собака, он ее любил.")
print("Она съела кусок мяса, он ее убил,")
print("В землю закопал и надпись написал:")
short_story()
Как мы видели выше, функция может вызывать другую функцию. Но функция также может вызывать и саму себя! Рассмотрим это на примере функции вычисления факториала. Хорошо известно, что 0!=1, 1!=1. А как вычислить величину n! для большого n? Если бы мы могли вычислить величину (n-1)!, то тогда мы легко вычислим n!, поскольку n!=n⋅(n-1)!. Но как вычислить (n-1)!? Если бы мы вычислили (n-2)!, то мы сможем вычисли и (n-1)!=(n-1)⋅(n-2)!. А как вычислить (n-2)!? Если бы... В конце концов, мы дойдем до величины 0!, которая равна 1. Таким образом, для вычисления факториала мы можем использовать значение факториала для меньшего числа. Это можно сделать и в программе на Питоне:
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
print(factorial(5))
Подобный прием (вызов функцией самой себя) называется рекурсией, а сама функция называется рекурсивной.
Рекурсивные функции являются мощным механизмом в программировании. К сожалению, они не всегда эффективны. Также часто использование рекурсии приводит к ошибкам. Наиболее распространенная из таких ошибок – бесконечная рекурсия, когда цепочка вызовов функций никогда не завершается и продолжается, пока не кончится свободная память в компьютере. Пример бесконечной рекурсии приведен в эпиграфе к этому разделу. Две наиболее распространенные причины для бесконечной рекурсии:
Неправильное оформление выхода из рекурсии. Например, если мы в программе вычисления факториала забудем поставить проверку if n == 0, то factorial(0) вызовет factorial(-1), тот вызовет factorial(-2) и т. д.
Рекурсивный вызов с неправильными параметрами. Например, если функция factorial(n) будет вызывать factorial(n), то также получится бесконечная цепочка.
Поэтому при разработке рекурсивной функции необходимо прежде всего оформлять условия завершения рекурсии и думать, почему рекурсия когда-либо завершит работу.
Достарыңызбен бөлісу: |