## ++Тема 7++<br>Функции и рекурсия
(c) Яценко Р.Н., 2019-2020
---
## 1. Принципы структурного программирования
----
### Структурный принцип
- Важным принципом современного программирования является структурный принцип
- В структурированной программе отдельные ее части, предназначенные для решения каких-то частных небольших задач, организованы в подпрограммы
----
### Преимущества
1. Один и тот же фрагмент можно использовать многократно как в одной, так и в разных программах, не набирая его текст заново
2. Программы лучше писать небольшими частями. Такие программы легче читать, тестировать и отлаживать. У них, как правило, более четкая логическая структура
----
### Подпрограмма
Подпрограмма
: это повторяющаяся группа операторов, оформленная в виде самостоятельной части программы
- Она записывается однократно, а в соответствующих местах программы обеспечивается лишь обращение к ней по имени
- В Python подпрограммы реализуются с помощью функций
---
## 2. Объявление функций
----
### Пример 1. Факториал числа (for)
В математике факториал числа n определяется как
$$n! = 1 \cdot 2 \cdot ... \cdot n$$
Например, $5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120$
```python=
# вычислим 3!
res = 1
for i in range(1, 4):
res *= i
print(res)
# вычислим 5!
res = 1
for i in range(1, 6):
res *= i
print(res)
```
```
6
120
```
----
### Синтаксис объявления функций
```python
def имя_функции(параметры):
# тело_функции
return результат
```
- `имя_функции` -- это содержательный идентификатор
- `параметры` -- это список специальных переменных, которые используются для передачи данных в функцию
- `тело_функции` -- набор команд, которые должны быть выполнены
- `return результат` -- завершает работу функции и возвращает указанное значение
----
### Пример 2. Факториал числа (def)
```python=
def factorial(n):
res = 1
for i in range(1, n + 1):
res *= i
return res
print(factorial(3))
print(factorial(5))
```
----
### Пример 2. Выполнение
<iframe frameborder="0" src="http://pythontutor.com/iframe-embed.html#code=def%20factorial%28n%29%3A%0A%20%20%20%20res%20%3D%201%0A%20%20%20%20for%20i%20in%20range%281,%20n%20%2B%201%29%3A%0A%20%20%20%20%20%20%20%20res%20*%3D%20i%0A%20%20%20%20return%20res%0A%0Aprint%28factorial%283%29%29%0Aprint%28factorial%285%29%29&codeDivHeight=400&codeDivWidth=350&cumulative=false&curInstr=0&heapPrimitives=nevernest&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false" style="width: 100%; height: 50vh; transform: scale(1.1);"> </iframe>
----
### Пример 3. Максимум из двух чисел
```python=
def max(a, b):
if a > b:
return a
else:
return b
print(max(3, 5))
print(max(6, 3))
```
```
5
6
```
----
### Пример 4. Максимум из трех чисел
```python=
def max(a, b):
if a > b:
return a
else:
return b
def max3(a, b, c):
return max(max(a, b), c)
print(max3(3, 5, 4))
```
```
5
```
----
### Пример 5. Параметры
```python=
def display(message):
print(message)
def give_me_five():
five = 5
return five
def ask_yes_no(question):
# Задает вопрос с ответом 'y' или 'n'
response = None
while response not in ("y", "n"):
response = input(question).lower()
return response
```
----
```python=15
# основная часть
display("Вам сообщение.")
number = give_me_five()
print("Вот что возвратила функция give_me_five():", number)
answer = ask_yes_no("Пожалуйста, введите 'y' или 'n': ")
print("Спасибо, что ввели:", answer)
```
----
### Пример 5. Выполнение
<iframe frameborder="0" src="http://pythontutor.com/iframe-embed.html#code=def%20display%28message%29%3A%0A%20%20%20%20print%28message%29%0A%0Adef%20give_me_five%28%29%3A%0A%20%20%20%20five%20%3D%205%0A%20%20%20%20return%20five%0A%0Adef%20ask_yes_no%28question%29%3A%0A%20%20%20%20%23%20%D0%97%D0%B0%D0%B4%D0%B0%D0%B5%D1%82%20%D0%B2%D0%BE%D0%BF%D1%80%D0%BE%D1%81%20%D1%81%20%D0%BE%D1%82%D0%B2%D0%B5%D1%82%D0%BE%D0%BC%20'y'%20%D0%B8%D0%BB%D0%B8%20'n'%0A%20%20%20%20response%20%3D%20None%0A%20%20%20%20while%20response%20not%20in%20%28%22y%22,%20%22n%22%29%3A%0A%20%20%20%20%20%20%20%20response%20%3D%20input%28question%29.lower%28%29%0A%20%20%20%20return%20response%0A%0A%23%20%D0%BE%D1%81%D0%BD%D0%BE%D0%B2%D0%BD%D0%B0%D1%8F%20%D1%87%D0%B0%D1%81%D1%82%D1%8C%0Adisplay%28%22%D0%92%D0%B0%D0%BC%20%D1%81%D0%BE%D0%BE%D0%B1%D1%89%D0%B5%D0%BD%D0%B8%D0%B5.%22%29%0Anumber%20%3D%20give_me_five%28%29%0Aprint%28%22%D0%92%D0%BE%D1%82%20%D1%87%D1%82%D0%BE%20%D0%B2%D0%BE%D0%B7%D0%B2%D1%80%D0%B0%D1%82%D0%B8%D0%BB%D0%B0%20%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F%20give_me_five%28%29%3A%22,%20number%29%0Aanswer%20%3D%20ask_yes_no%28%22%D0%9F%D0%BE%D0%B6%D0%B0%D0%BB%D1%83%D0%B9%D1%81%D1%82%D0%B0,%20%D0%B2%D0%B2%D0%B5%D0%B4%D0%B8%D1%82%D0%B5%20'y'%20%D0%B8%D0%BB%D0%B8%20'n'%3A%20%22%29%0Aprint%28%22%D0%A1%D0%BF%D0%B0%D1%81%D0%B8%D0%B1%D0%BE,%20%D1%87%D1%82%D0%BE%20%D0%B2%D0%B2%D0%B5%D0%BB%D0%B8%3A%22,%20answer%29&codeDivHeight=400&codeDivWidth=350&cumulative=false&curInstr=0&heapPrimitives=nevernest&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false" style="width: 100%; height: 50vh; transform: scale(1.1);"> </iframe>
----
### Произвольное количество аргументов
- В Python у функций бывают параметры, которым уже присвоено значение по-умолчанию
- В таком случае, при вызове можно не передавать соответствующие этим параметрам аргументы
- Хотя можно и передать. Тогда значение по умолчанию заменится на переданное
----
### Пример 6. Параметры по умолчанию
```python=
def cylinder(h, r = 1):
side = 2 * 3.14 * r * h
circle = 3.14 * r**2
full = side + 2 * circle
return full
figure1 = cylinder(4, 3)
figure2 = cylinder(5)
print(figure1)
print(figure2)
```
```
131.88
37.68
```
---
## 3. Локальные и глобальные переменные
----
### Область действия переменной
Область действия переменной
: это часть программы, где она может быть использована. В программе все переменные делятся на *глобальные* и *локальные*
----
### Глобальные переменные
Глобальные переменные
: это те переменные, которые объявлены в основной части программы, ими можно пользоваться в основной программе или любой функции
```python=
def f():
print(a)
a = 1
f()
```
```
1
```
----
### Локальные переменные
Локальные переменные
: это переменные, объявленные внутри функций, и могут быть использованы только внутри данной функции
```python=
def f():
a = 1
f()
print(a)
```
```
NameError: name 'a' is not defined
```
----
### Пример 7
```python=
def f():
a = 1
print(a)
a = 0
f()
print(a)
```
```
1
0
```
Если внутри функции модифицируется значение глобальной переменной, то переменная с таким именем становится локальной переменной, и ее модификация не приведет к изменению глобальной переменной
----
### Пример 7. Выполнение
<iframe frameborder="0" src="http://pythontutor.com/iframe-embed.html#code=def%20f%28%29%3A%0A%20%20%20%20a%20%3D%201%0A%20%20%20%20print%28a%29%0A%0Aa%20%3D%200%0Af%28%29%0Aprint%28a%29&codeDivHeight=400&codeDivWidth=350&cumulative=false&curInstr=0&heapPrimitives=nevernest&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false" style="width: 100%; height: 50vh; transform: scale(1.1);"> </iframe>
----
### Правило использования глобальных переменных
- Если ваша функция должна поменять какую-то переменную, пусть лучше она вернёт это значением, и вы сами при вызове функции явно присвоите в переменную это значение
- В этом случае функции получаются независимыми от кода, и их можно легко копировать из одной программы в другую
---
## 4. Рекурсия
----
### Определение рекурсии
Рекурсия
: Вызов функцией самой себя называется рекурсией, а сама функция называется *рекурсивной*
```python=
def short_story():
print("У попа была собака, он ее любил.")
print("Она съела кусок мяса, он ее убил,")
print("В землю закопал и надпись написал:")
short_story()
```
----
### Пример 8. Факториал числа (рекурсия)
Известно, что 0!=1, 1!=1.
А как вычислить величину n! для большого n?
$$n! = n \cdot (n-1)! = n \cdot (n-1) \cdot (n-2)! = ...$$
----
В конце концов, мы дойдем до величины 0!, которая равна 1
```python=
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
print(factorial(5))
```
----
### Пример 8. Выполнение
<iframe frameborder="0" src="http://pythontutor.com/iframe-embed.html#code=def%20factorial%28n%29%3A%0A%20%20%20%20if%20n%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20return%201%0A%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20return%20n%20*%20factorial%28n%20-%201%29%0A%0Aprint%28factorial%285%29%29&codeDivHeight=400&codeDivWidth=350&cumulative=false&curInstr=0&heapPrimitives=nevernest&origin=opt-frontend.js&py=3&rawInputLstJSON=%5B%5D&textReferences=false" style="width: 100%; height: 50vh; transform: scale(1.1);"> </iframe>
----
### Бесконечная рекурсия
1. Неправильное оформление выхода из рекурсии. Например, если мы в программе вычисления факториала забудем поставить проверку `if n == 0`, то `factorial(0)` вызовет `factorial(-1)`, тот вызовет `factorial(-2)` и т.д.
2. Рекурсивный вызов с неправильными параметрами. Например, если функция `factorial(n)` будет вызывать `factorial(n)`, то также получится бесконечная цепочка
---
## Спасибо за внимание!
(c) Яценко Р.Н., 2019-2020
{"metaMigratedAt":"2023-06-15T15:13:02.176Z","metaMigratedFrom":"YAML","title":"Тема 7. Функции и рекурсия","breaks":false,"slideOptions":"{\"allottedMinutes\":80,\"slideNumber\":\"c\",\"theme\":\"beige\",\"transition\":\"slide\",\"spotlight\":{\"enabled\":true}}","contributors":"[{\"id\":\"93a8c43f-1b5b-4461-9101-89b183ccbc1c\",\"add\":9992,\"del\":411}]"}