Тема 7. Функции и рекурсия

--- title: Тема 7. Функции и рекурсия tags: Python Step slideOptions: allottedMinutes: 80 slideNumber: c theme: beige transition: slide spotlight: enabled: true --- ## ++Тема 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)`, то также получится бесконечная цепочка --- ## Спасибо за внимание! ![](https://i.imgur.com/gKDsna4.png) (c) Яценко Р.Н., 2019-2020

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.