Программирование на языке Python

Описание презентации по отдельным слайдам:

• 

  1 слайд

  Программирование на языке Python
  1
  

• 

  2 слайд

  Программа, вывод и комментарии
  2
  # Это пустая программа
  Что делает эта программа?
  ?
  комментарии после #
  не обрабатываются
  # -*- coding: utf-8 -*-
  # Это пустая программа
  кодировка utf-8 по умолчанию)
  Windows: cp1251
  """
  Это тоже комментарий
  """
  

• 

  3 слайд

  Вывод на экран
  3
  print ( "2+2=?" )
  print ( "Ответ: 4" )
  Протокол:
  2+2=?
  Ответ: 4
  автоматический переход на новую строку
  print ( '2+2=?' )
  print ( 'Ответ: 4' )
  

• 

  4 слайд

  Задания
  4
  «B»: Вывести на экран текст «лесенкой»
  Вася
  пошел
  гулять
  «C»: Вывести на экран рисунок из букв
  Ж
  ЖЖЖ
  ЖЖЖЖЖ
  ЖЖЖЖЖЖЖ
  HH HH
  ZZZZZ
  

• 

  5 слайд

  Ввод двух значений в одной строке
  5
  a, b = map ( int, input().split() )
  input()
  ввести строку с клавиатуры
  21 33
  input().split()
  21
  33
  разделить строку на части по пробелам
  map ( int, input().split() )
  21
  33
  целые
  применить
  эту операцию
  к каждой части
  a, b = map ( int, input().split() )
  

• 

  6 слайд

  Изменение значений переменной
  6
  a = 5
  b = a + 2
  a = (a + 2)*(b – 3)
  b = b + 1
  a
  5
  b
  =5+2
  7
  28
  =(5+2)*(7-3)
  =7+1
  8
  

• 

  7 слайд

  Вывод данных
  7
  print ( a )
  значение переменной
  print ( "Ответ: ", a )
  значение и текст
  перечисление через запятую
  print ( "Ответ: ", a+b )
  вычисление выражения
  print ( a, "+", b, "=", c )
  2 + 3 = 5
  через пробелы
  print ( a, "+", b, "=", c, sep = "" )
  2+3=5
  sep = ""
  убрать разделители
  

• 

  8 слайд

  Форматный вывод
  8
  a = 123
  print ( "{:5d}".format(a) )
  5 знаков
  123
  5
  a = 123
  print ( "{:5d}{:5d}{:5d}".format
  (a, a*a, a*a*a) )
  целое
  5 знаков
  5
  5 знаков
  25
  5 знаков
  125
  

• 

  9 слайд

  Случайные числа
  9
  Случайно…
  встретить друга на улице
  разбить тарелку
  найти 10 рублей
  выиграть в лотерею
  Случайный выбор:
  жеребьевка на
  соревнованиях
  выигравшие номера
  в лотерее
  Как получить случайность?
  

• 

  10 слайд

  Случайные числа на компьютере
  10
  Электронный генератор
  нужно специальное устройство
  нельзя воспроизвести результаты
  318458191041
  564321
  209938992481
  458191
  938992
  малый период
  (последовательность повторяется через 106 чисел)
  Метод середины квадрата (Дж. фон Нейман)
  в квадрате
  Псевдослучайные числа – обладают свойствами случайных чисел, но каждое следующее число вычисляется по заданной формуле.
  зерно
  

• 

  11 слайд

  Генератор случайных чисел
  11
  Генератор на [0,1):
  X = random(); # псевдослучайное число
  Y = random() # это уже другое число!
  англ. random – случайный
  Целые числа на отрезке [a,b]:
  X = randint(a, b) # псевдослучайное число
  Y = randint(a, b) # это уже другое число!
  import random
  

• 

  12 слайд

  Задачи
  12
  «A»: Ввести с клавиатуры три целых числа, найти их сумму, произведение и среднее арифметическое.
  Пример:
  Введите три целых числа:
  5 7 8
  5+7+8=20
  5*7*8=280
  (5+7+8)/3=6.667
  «B»: Ввести с клавиатуры координаты двух точек (A и B) на плоскости (вещественные числа). Вычислить длину отрезка AB.
  Пример:
  Введите координаты точки A:
  5.5 3.5
  Введите координаты точки B:
  1.5 2
  Длина отрезка AB = 4.272
  

• 

  13 слайд

  Задачи
  13
  «C»: Получить случайное трехзначное число и вывести через запятую его отдельные цифры.
  Пример:
  Получено число 123.
  Его цифры 1, 2, 3.
  

• 

  14 слайд

  Программирование на языке Python
  Ветвления
  14
  

• 

  15 слайд

  Условный оператор
  15
  Задача: изменить порядок действий в зависимости от выполнения некоторого условия.
  M = a
  a > b?
  M = b
  да
  нет
  вывод M
  полная форма ветвления
  Если a = b?
  ?
  if a > b:
  M = a
  else:
  M = b
  отступы
  

• 

  16 слайд

  Условный оператор: неполная форма
  16
  M = b
  b > a?
  да
  нет
  вывод M
  M = a
  неполная форма ветвления
  M = a
  if b > a:
  M = b
  M = max(a, b)
  Решение в стиле Python:
  M = a if a > b else b
  

• 

  17 слайд

  Условный оператор
  17
  if a > b:
  с = a
  a = b
  b = c
  Что делает?
  ?
  4
  6
  ?
  4
  6
  4
  a
  b
  3
  2
  1
  Можно ли обойтись
  без переменной c?
  ?
  c
  a, b = b, a
  Решение в стиле Python:
  

• 

  18 слайд

  Знаки отношений
  18
  >
  <
  >=
  <=
  ==
  !=
  больше, меньше
  больше или равно
  меньше или равно
  равно
  не равно
  

• 

  19 слайд

  Вложенные условные операторы
  19
  if a > b:
  print("Андрей старше")
  else:
  
  
  
  
  if a == b:
  print("Одного возраста")
  else:
  print("Борис старше")
  вложенный условный оператор
  Зачем нужен?
  ?
  Задача: в переменных a и b записаны возрасты Андрея и Бориса. Кто из них старше?
  Сколько вариантов?
  ?
  

• 

  20 слайд

  Каскадное ветвление
  20
  if a > b:
  print("Андрей старше")
  elif a == b:
  print("Одного возраста")
  else:
  print("Борис старше")
  elif = else if
  !
  

• 

  21 слайд

  Каскадное ветвление
  21
  cost = 1500
  if cost < 1000:
  print ( "Скидок нет." )
  elif cost < 2000:
  print ( "Скидка 2%." )
  elif cost < 5000:
  print ( "Скидка 5%." )
  else:
  print ( "Скидка 10%." )
  Что выведет?
  ?
  первое сработавшее условие
  Скидка 2%.
  

• 

  22 слайд

  Задачи
  22
  

• 

  23 слайд

  Программирование на языке Python
  Циклические алгоритмы
  23
  

• 

  24 слайд

  Что такое цикл?
  24
  Цикл – это многократное выполнение одинаковых действий.
  Два вида циклов:
  цикл с известным числом шагов (сделать 10 раз)
  цикл с неизвестным числом шагов (делать, пока не надоест)
  Задача. Вывести на экран 10 раз слово «Привет».
  Можно ли решить известными методами?
  ?
  

• 

  25 слайд

  Повторения в программе
  25
  print("Привет“)
  print("Привет")
  ...
  print("Привет")
  Что плохо?
  ?
  

• 

  26 слайд

  Блок-схема цикла
  26
  начало
  конец
  да
  нет
  тело цикла
  сделали 10 раз?
  print("Привет!")
  

• 

  27 слайд

  Как организовать цикл?
  27
  счётчик = 0
  пока счётчик < 10:
  print("Привет“)
  увеличить счётчик на 1
  счётчик = 10
  пока счётчик > 0:
  print("Привет")
  уменьшить счётчик на 1
  
  результат операции автоматически сравнивается с нулём!
  

• 

  28 слайд

  Цикл с условием
  28
  count = 0;
  while :
  
  
  
  n = n // 10
  count += 1
  
  тело цикла
  начальное значение счётчика
  n > 0
  условие продолжения
  заголовок цикла
  Цикл с предусловием – проверка на входе в цикл!
  !
  

• 

  29 слайд

  Цикл с условием
  29
  k = 0
  while k < 10:
  print ( "привет" )
  k += 1
  При известном количестве шагов:
  k = 0
  while k < 10:
  print ( "привет" )
  Зацикливание:
  

• 

  30 слайд

  Цикл с постусловием
  30
  while True:
  
  
  if n > 0: break
  условие выхода
  print ( "Введите положительное число:" )
  n = int ( input() )
  тело цикла
  при входе в цикл условие не проверяется
  цикл всегда выполняется хотя бы один раз
  Задача. Обеспечить ввод положительного числа в переменную n.
  бесконечный цикл
  прервать цикл
  

• 

  31 слайд

  Цикл с переменной
  31
  Задача. Вывести 10 раз слово «Привет!».
  Аналог цикла «пока»?
  ?
   
  while :
  print("Привет!")
   
  i = 0
  i < 10
  i += 1
  for :
  print("Привет!")
  i in range(10)
  в диапазоне [0,10)
  Цикл с переменной:
  Не включая 10!
  !
  range(10)  0, 1, 2, 3, 4, 5, 6, 7, 8, 9
  

• 

  32 слайд

  Цикл с переменной
  32
  Задача. Вывести все степени двойки от 21 до 210.
  Как сделать с циклом «пока»?
  ?
   
  while :
  print ( 2**k )
   
  k = 1
  k <= 10
  k += 1
  for :
  print ( 2**k )
  k in range(1,11)
  в диапазоне [1,11)
  Цикл с переменной:
  Не включая 11!
  !
  range(1,11)  1, 2, 3, 4, 5, 6, 7, 8, 9, 10
  

• 

  33 слайд

  Цикл с переменной: другой шаг
  33
  100
  81
  64
  49
  36
  25
  16
  9
  4
  1
  Что получится?
  ?
  1
  9
  25
  49
  81
  for :
  print ( k**2 )
  k in range(1,11,2)
  for :
  print ( k**2 )
  k in range(10,0,-1)
  шаг
  10,9,8,7,6,5,4,3,2,1
  1,3,5,7,9
  

• 

  34 слайд

  Задачи
  34
  i=1
  m=32000
  while i<=10:
  a=float(input("Введите число a="))
  if a<m:
  m=a
  otv=i
  i+=1
  print("Номер минимального числа otv=",otv)
  «A»: Нахождение номера минимального значения в последовательности вводимых чисел
  i=1
  m=0
  while i<10:
  a=float(input("Введите число a="))
  if (m>a or m==0):
  m=a
  otv=i
  i+=1
  print("Номер минимального числа otv=",otv)
  

• 

  35 слайд

  Вложенные циклы
  35
  Задача. Вывести все простые числа в диапазоне
  от 2 до 1000.
  сделать для n от 2 до 1000
  если число n простое то
  вывод n
  число n простое
  нет делителей [2.. n-1]: проверка в цикле!
  Что значит «простое число»?
  ?
  for n in range(2, 10001):
  if число n простое:
  print( n )
  

• 

  36 слайд

  Вложенные циклы
  36
  for n in range(2, 10001):
  count = 0;
  
  
  
  if count == 0:
  print( n )
  for k in range(2,n):
  if n % k == 0:
  count += 1
  вложенный цикл
  

• 

  37 слайд

  Вложенные циклы
  37
  for i in range(1,45):
  for k in range(1,i+1):
  print( i, k )
  1 1
  2 1
  2 2
  3 1
  3 2
  3 3
  4 1
  4 2
  4 3
  4 4
  Переменная внутреннего
  цикла изменяется быстрее!
  !
  

• 

  38 слайд

  Поиск простых чисел – как улучшить?
  38
  count = 0
  k = 2
  while :
  if n % k == 0:
  count += 1
  k += 1
  while k <= math.sqrt(n):
  …
  while k*k <= n:
  if n % k == 0: break
  k += 1
  if k*k > n:
  print ( n )
  k*k <= n
  Как ещё улучшить?
  ?
  выйти из цикла
  если вышли по условию
  

• 

  39 слайд

  Задачи
  39
  «А»: В магазине продается мастика в ящиках по 15 кг,
  17 кг, 21 кг. Как купить ровно 185 кг мастики, не вскрывая ящики? Сколькими способами можно это сделать?
  count = 0
  for i in range(13):
  for j in range(11):
  for k in range(9):
  if 185 == i*15+j*17+k*21:
  count += 1
  print(i,j,k)
  print('Всего способов - ', count)
  

• 

  40 слайд

  Задачи
  40
  «С на дом»: Напишите программу, которая получает натуральные числа a и b(a меньше b) и выводит все простые числа в интервале от a до b
  Пример:
  Введите границы диапазона:
  10 20
  11 13 17 19
  
  
  a=int(input('Введите a='))
  b=int(input('Введите b='))
  for k in range(a,b+1):
  prime = True
  for i in range(2,k):
  if k%i==0:
  prime=False
  break
  if prime:
  print('{}-простое число'.format(k))
  

• 

  41 слайд

  Программирование на языке Python
  Процедуры
  41
  

• 

  42 слайд

  Зачем нужны процедуры?
  42
  print ( "Ошибка программы" )
  много раз!
  def Error():
  print( "Ошибка программы" )
  n = int ( input() )
  if n < 0:
  Error()
  вызов процедуры
  Процедура:
  define определить
  

• 

  43 слайд

  Что такое процедура?
  43
  Процедура – вспомогательный алгоритм, который выполняет некоторые действия.
  текст (расшифровка) процедуры записывается
  до её вызова в основной программе
  в программе может быть много процедур
  чтобы процедура заработала, нужно вызвать её по имени из основной программы или из другой процедуры
  

• 

  44 слайд

  Процедура с параметрами
  44
  Задача. Вывести на экран запись целого числа (0..255) в 8-битном двоичном коде.
  много раз!
  Алгоритм:
  178
  
  101100102
  Как вывести первую цифру?
  ?
  7 6 5 4 3 2 1 0
  1 0 1 1 0 0 1 02
  разряды
  n:=
  n // 128
  n % 128
  Как вывести вторую цифру?
  ?
  n1 // 64
  

• 

  45 слайд

  Процедура с параметрами
  45
  Задача. Вывести на экран запись целого числа (0..255) в 8-битном двоичном коде.
  Решение:
  k = 128
  while k > 0:
  print ( n // k,
  end = "" )
  n = n % k
  k = k // 2
  178
  
  10110010
  Результат зависит
  от n!
  !
  

• 

  46 слайд

  Процедура с параметрами
  46
  printBin ( 99 )
  значение параметра (аргумент)
  def printBin( n ):
  k = 128
  while k > 0:
  print ( n // k, end = "" )
  n = n % k;
  k = k // 2
  Параметры – данные, изменяющие работу процедуры.
  локальная переменная
  def printSred( a, b ):
  print ( (a + b)/2 )
  Несколько параметров:
  

• 

  47 слайд

  Локальные и глобальные переменные
  47
  a = 5
  def qq():
  a = 1
  print ( a )
  qq()
  print ( a )
  глобальная переменная
  локальная переменная
  1
  5
  a = 5
  def qq():
  print ( a )
  qq()
  5
  a = 5
  def qq():
  global a
  a = 1
  qq()
  print ( a )
  1
  global a
  работаем с
  глобальной переменной
  

• 

  48 слайд

  Задачи
  48
  «A»: Напишите процедуру, которая принимает параметр – натуральное число N – и выводит на экран линию из N символов '–'.
  Пример:
  Введите N:
  10
  ----------
  «B»: Напишите процедуру, которая выводит на экран в столбик все цифры переданного ей числа, начиная с первой.
  Пример:
  Введите натуральное число:
  1234
  1
  2
  3
  4
  def printChar(s):
  print('-'*int(s))
  
  n = input('введите число n=')
  printChar(n)
  def ShowCif(a):
  if a>0:
  ShowCif(a//10)
  print(a%10)
  
  ShowCif(1234)
  

• 

  49 слайд

  Программирование на языке Python
  § 60. Функции
  49
  

• 

  50 слайд

  Что такое функция?
  50
  Функция – это вспомогательный алгоритм, который возвращает значение-результат (число, символ или объект другого типа).
  Задача. Написать функцию, которая вычисляет сумму цифр числа.
  Алгоритм:
  сумма = 0
  пока n != 0:
  сумма += n % 10
  n = n // 10
  

• 

  51 слайд

  Сумма цифр числа
  51
  # основная программа
  print ( sumDigits(12345) )
  def sumDigits( n ):
  sum = 0
  while n!= 0:
  sum += n % 10
  n = n // 10
  return sum
  return sum
  передача результата
  

• 

  52 слайд

  Использование функций
  52
  x = 2*sumDigits(n+5)
  z = sumDigits(k) + sumDigits(m)
  if sumDigits(n) % 2 == 0:
  print ( "Сумма цифр чётная" )
  print ( "Она равна", sumDigits(n) )
  Функция, возвращающая целое число, может использоваться везде, где и целая величина!
  !
  Одна функция вызывает другую:
  def middle ( a, b, c ):
  mi = min ( a, b, c )
  ma = max ( a, b, c )
  return a + b + c - mi - ma
  вызываются min и max
  Что вычисляет?
  ?
  

• 

  53 слайд

  Задачи
  53
  «A»: Напишите функцию, которая находит наибольший общий делитель двух натуральных чисел.
  Пример:
  Введите два натуральных числа:
  7006652 112307574
  НОД(7006652,112307574) = 1234.
  
  def sumDigits(a,b):
  # Пока какое-нибудь из двух числе не будет равно 0,
  while a!=0 and b!=0:
  # сравнивать их между собой.
  # Если первое число больше второго,
  if a>b:
  # то находить остаток от деления его на второе число
  # и присваивать его первой переменной
  a=a%b
  # Иначе (когда второе число больше первого)
  else:
  # присваивать второй переменной остаток от деления
  # нацело второго числа на первое
  b=b%a
  # Одно из чисел содержит 0, а другое - НОД, но какое - неизвестно.
  # Проще их сложить, чем писать конструкцию if-else
  gcd=a+b
  return gcd
  print(sumDigits(7006652,112307574)) # ввод целых чисел
  
  

• 

  54 слайд

  Как вернуть несколько значений?
  54
  def divmod ( x, y ):
  d = x // y
  m = x % y
  return d, m
  d – частное,
  m – остаток
  a, b = divmod ( 7, 3 )
  print ( a, b )# 2 1
  q = divmod ( 7, 3 )
  print ( q )# (2, 1)
  (2, 1)
  кортеж – набор элементов
  

• 

  55 слайд

  Задачи
  55
  «B»: Напишите функцию, которая определяет сумму цифр переданного ей числа.
  Пример:
  Введите натуральное число:
  123
  Сумма цифр числа 123 равна 6.
  
  

• 

  56 слайд

  Задачи
  56
  «C»: Напишите функцию, которая сокращает дробь вида M/N.
  Пример:
  Введите числитель и знаменатель дроби:
  25 15
  После сокращения: 5/3
  
  

• 

  57 слайд

  Логические функции
  57
  Задача. Найти все простые числа в диапазоне
  от 2 до 100.
  for i in range(2,1001):
  if  i - простое  :
  print ( i )
  i - простое
  isPrime(i)
  функция, возвращающая логическое значение (True/False)
  

• 

  58 слайд

  Функция: простое число или нет?
  58
  Какой алгоритм?
  ?
  def isPrime ( n ):
  k = 2
  while k*k <= n and n % k != 0:
  k += 1
  return (k*k > n)
  return (k*k > n)
  if k*k > n:
  return True
  else:
  return False
  

• 

  59 слайд

  Логические функции: использование
  59
  n = int ( input() )
  while isPrime(n):
  print ( n, "– простое число" )
  n = int ( input() )
  Функция, возвращающая логическое значение, может использоваться везде, где и логическая величина!
  !
  

• 

  60 слайд

  Задачи
  60
  «A»: Напишите логическую функцию, которая определяет, является ли переданное ей число совершенным, то есть, равно ли оно сумме своих делителей, меньших его самого.
  Пример:
  Введите натуральное число:
  28
  Число 28 совершенное.
  Пример:
  Введите натуральное число:
  29
  Число 29 не совершенное.
  

• 

  61 слайд

  Программирование на языке Python
  § 61. Рекурсия
  61
  

• 

  62 слайд

  Что такое рекурсия?
  62
  У попа была собака, он её любил,
  Она съела кусок мяса, он её убил,
  В землю закопал,
  Надпись написал:
  У попа была собака, он её любил,
  Она съела кусок мяса, он её убил,
  В землю закопал,
  Надпись написал:
  …
  

• 

  63 слайд

  Что такое рекурсия?
  63
  Натуральные числа:
  1 – натуральное число
  если – натуральное число,
  то – натуральное число
  индуктивное определение
  Рекурсия — это способ определения множества объектов через само это множество на основе заданных простых базовых случаев.
  Числа Фибоначчи:
  
  
  при
  1, 1, 2, 3, 5, 8, 13, 21, 34, …
  

• 

  64 слайд

  Фракталы
  64
  Фракталы – геометрические фигуры, обладающие самоподобием.
  Треугольник Серпинского:
  

• 

  65 слайд

  Ханойские башни
  65
  1
  2
  3
  за один раз переносится один диск
  класть только меньший диск на больший
  третий стержень вспомогательный
  перенести (n-1, 1, 2)
  1 -> 3
  перенести (n-1, 2, 3)
  перенести (n, 1, 3)
  

• 

  66 слайд

  Ханойские башни – процедура
  66
  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!)
  сколько
  откуда
  куда
  Что плохо?
  ?
  Рекурсия никогда не остановится!
  !
  рекурсия
  рекурсия
  

• 

  67 слайд

  Ханойские башни – процедура
  67
  Рекурсивная процедура (функция) — это процедура (функция), которая вызывает сама себя напрямую или через другие процедуры и функции.
  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 )
  

• 

  68 слайд

  Вывод двоичного кода числа
  68
  def printBin ( n ):
  if n == 0: return
  printBin ( n // 2 )
  print ( n % 2, end = "" )
  условие выхода из рекурсии
  напечатать все цифры, кроме последней
  вывести последнюю цифру
  10011
  printBin( 19 )
  printBin( 9 )
  printBin( 4 )
  printBin( 2 )
  printBin( 1 )
  printBin( 0 )
  Как без рекурсии?
  ?
  

• 

  69 слайд

  Вычисление суммы цифр числа
  69
  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
  последняя цифра
  

• 

  70 слайд

  Алгоритм Евклида
  70
  Алгоритм Евклида. Чтобы найти НОД двух натуральных чисел, нужно вычитать из большего числа меньшее до тех пор, пока меньшее не станет равно нулю. Тогда второе число и есть НОД исходных чисел.
  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;
  рекурсивные вызовы
  условие окончания рекурсии
  

• 

  71 слайд

  Задачи
  71
  «A»: Напишите рекурсивную функцию, которая вычисляет НОД двух натуральных чисел, используя модифицированный алгоритм Евклида.
  Пример:
  Введите два натуральных числа:
  7006652 112307574
  НОД(7006652,112307574)=1234.
  «B»: Напишите рекурсивную функцию, которая раскладывает число на простые сомножители.
  Пример:
  Введите натуральное число:
  378
  378 = 2*3*3*3*7
  
  

• 

  72 слайд

  Задачи
  72
  «C»: Дано натуральное число N. Требуется получить и вывести на экран количество всех возможных различных способов представления этого числа в виде суммы натуральных чисел (то есть, 1 + 2 и 2 + 1 – это один и тот же способ разложения числа 3). Решите задачу с помощью рекурсивной процедуры.
  Пример:
  Введите натуральное число:
  4
  Количество разложений: 4.
  

• 

  73 слайд

  Как работает рекурсия?
  73
  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
  Как сохранить состояние функции перед рекурсивным вызовом?
  ?
  Факториал:
  

• 

  74 слайд

  Стек
  74
  Стек – область памяти, в которой хранятся локальные переменные и адреса возврата.
  SP
  SP
  SP
  SP
  Fact(3)
  Fact(2)
  Fact(1)
  значение параметра
  адрес возврата
  локальная переменная
  

• 

  75 слайд

  Рекурсия – «за» и «против»
  75
  с каждым новым вызовом расходуется память в стеке (возможно переполнение стека)
  затраты на выполнение служебных операций при рекурсивном вызове
  программа становится более короткой и понятной
  возможно переполнение стека
  замедление работы
  Любой рекурсивный алгоритм можно заменить нерекурсивным!
  !
  def Fact ( n ):
  f = 1
  for i in range(2,n+1):
  f *= i
  return f
  итерационный алгоритм