Общее по Computer Science и Web Development

Что такое хвостовая рекурсия?
Это особый вид рекурсии, когда функция заканчивается вызовом самой себя без дополнительных операторов. Когда это условие выполняется, компилятор разворачивает рекурсию в цикл с одним стек-фреймом, просто меняя локальные переменные от итерации к итерации.
Так, классическое определение рекурсивного факториала return N * fact(N - 1) не поддерживает хвостовую рекурсию, потому что для каждого стек-фрейма придется хранить текущее значение N.
Чтобы сделать рекурсии хвостовой, добавляют параметры-аккумуляторы. Благодаря им функция знает о своем текущем состоянии. Пусть параметр acc по умолчанию равен 1. Тогда запись с хвостовой рекурсией будет выглядеть так:
def fact(N, acc=1):
if N == 1:
return acc
else:
return fact(N - 1, acc * N)

Опишите быструю сортировку. Какова ее сложность?
На первом этапе выбирают опорный элемент. Чаще всего его берут из середины массива. Затем последовательно сравнивают первый элемент массива с последним, второй с предпоследним и т.д. Если элемент слева от опорного элемента больше правого, они меняются местами. Когда доходят до опорного элемента, итерация считается законченной.
Далее описанный выше алгоритм применяют для двух подмассивов. Первый – от первого элемента до опорного элемента (не включительно), второй – от опорного до последнего.
Рекурсивный спуск продолжается, пока длины подмассивов не станут равны единице.
Сложность быстрой сортировки в среднем случае равна N * log(N).
Что такое О-нотация?
todo

Задачи на алгоритмы

• 
  Как извлечь элементы массива в случайном порядке без повторений?
  

Практика

• 
  Написать декоратор, который выводит на экран время работы произвольной функции.
  
• 
  Написать декоратор, который возвращает либо результат, либо экземпляр исключения.
  
• 
  Написать генератор Фибоначчи от a и b.
  
• 
  Получить из файла текст в юникоде.
  
• 
  Написать генератор чисел Фибоначчи вида def fib(a=1, b=2):