# Python 2 and 3 compatibility
# pip install future
from __future__ import (absolute_import, division,
print_function, unicode_literals)
from builtins import *
Рекурсивная функция - это функция, которая в теле вызывает сама себя.
Пример. Вычисление факториала (итеративная версия)
def factorial_iter(n):
k = 1
for i in range(2, n + 1):
k *= i
return k
for i, k in enumerate(range(1, 10)):
print(i+1, factorial_iter(k))
1 1 2 2 3 6 4 24 5 120 6 720 7 5040 8 40320 9 362880
Временная сложность - линейная по n.
%timeit factorial_iter(3200)
100 loops, best of 3: 3.55 ms per loop
Пример. Вычисление факториала (рекурсивная версия)
def factorial_recur(n):
if n == 1:
return 1
else:
return n * factorial_recur(n-1)
# n! = n * (n-1)!
# 4! = 4 * 3 * 2 * 1 = 24
for i, k in enumerate(range(1, 10)):
print(i+1, factorial_recur(k))
1 1 2 2 3 6 4 24 5 120 6 720 7 5040 8 40320 9 362880
Временная сложность - линейная по n.
from sys import setrecursionlimit
setrecursionlimit(1000000)
%timeit factorial_recur(3200)
100 loops, best of 3: 4.98 ms per loop
Пример. Вычисление элементов последовательности Фибоначчи (итеративная версия)
def fib_iter(n):
a, b = 1, 1
for i in range(n):
a, b = b, a + b
return a
for i in range(11):
print(fib_iter(i), end=", ")
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
Временная сложность - линейная по n.
%timeit fib_iter(20)
100000 loops, best of 3: 2.71 µs per loop
Пример. Вычисление элементов последовательности Фибоначчи (рекурсивная версия)
def fib_recur(n):
if n <= 1:
return 1
else:
return fib_recur(n - 1) + fib_recur(n - 2)
for i in range(11):
print(fib_recur(i), end=", ")
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,
Временная сложность - экспоненциальная по n.
Доказательство (метод математической индукции)
Уравнение рекурии $T(n) = T(n-1) + T(n-2) + O(1)$. Обозначение O - пояснение на Википедии
$T(n \leq 1) = O(1)$
Пусть $T(n - 1) = O(2^{n-1})$
Тогда $T(n) = T(n-1) + T(n-2) + O(1) = O(\frac{2^{n}}{2}) + O(2^{n-2}) + O(1) = O(2^n)$
%timeit fib_recur(40)
1 loops, best of 3: 1min 22s per loop
Пример. Метод сортировки QuickSort
def qs(a_list):
if len(a_list) <= 1:
return a_list
else:
el0 = a_list[0]
left, right = [], []
for elem in a_list[1:]:
if elem < el0:
left.append(elem)
else:
right.append(elem)
return qs(left) + [el0] + qs(right)
qs([9, 8, 7, 6, 5, 4])
[4, 5, 6, 7, 8, 9]
from random import choice
def quick_sort(a_list):
if len(a_list) <= 1:
return a_list
pivot = choice(range(len(a_list)))
return quick_sort([i for i in a_list[:pivot] + a_list[pivot+1:]
if i < a_list[pivot]]) + [a_list[pivot]] + \
quick_sort([i for i in a_list[:pivot] + a_list[pivot+1:]
if i >= a_list[pivot]])
quick_sort([3, 4, 2, 1, 6])
[1, 2, 3, 4, 6]
Временная сложность - $O(n*log(n))$
%timeit quick_sort([3, 4, 2, 1, 6, 145, 56, 23, 45, 234, 21])
10000 loops, best of 3: 60.3 µs per loop
Примеры дерева рекурсии QuickSort
Опорный элемент - всегда нулевой
T(n) = 2*T(n/2) + O(n)
При случайном выборе опорного элемента
Реализация, мимимизирующая потребление дополнительной памяти
import random
def sub_partition(array, start, end, idx_pivot):
'returns the position where the pivot winds up'
if not (start <= idx_pivot <= end):
raise ValueError('idx pivot must be between start and end')
array[start], array[idx_pivot] = array[idx_pivot], array[start]
pivot = array[start]
i = start + 1
j = start + 1
while j <= end:
if array[j] <= pivot:
array[j], array[i] = array[i], array[j]
i += 1
j += 1
array[start], array[i - 1] = array[i - 1], array[start]
return i - 1
def quicksort_inplace(array, start=0, end=None):
if end is None:
end = len(array) - 1
if end - start < 1:
return
idx_pivot = random.randint(start, end)
i = sub_partition(array, start, end, idx_pivot)
#print array, i, idx_pivot
quicksort_inplace(array, start, i - 1)
quicksort_inplace(array, i + 1, end)
a_list = [3, 4, 2, 1, 6, 7]
quicksort_inplace(a_list)
a_list
[1, 2, 3, 4, 6, 7]
Пример. Простая визуализация бинарного дерева
class BinaryTree:
def __init__(self, rootObj):
self.root = rootObj
self.leftChild = None
self.rightChild = None
def insertLeft(self, newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t
def insertRight(self,newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t
def getRightChild(self):
return self.rightChild
def getLeftChild(self):
return self.leftChild
def setRootVal(self,obj):
self.root = obj
def getRootVal(self):
return self.root
def __str__(self):
output = str(self.root)
if self.leftChild:
output = '/'.join([self.leftChild.__str__(), output])
else:
output = '[' + output
if self.rightChild:
output = '\\'.join([output, self.rightChild.__str__()])
else:
output = output + ']'
return output
r = BinaryTree('a')
r.insertLeft('b')
r.insertRight('c')
print("Root:", r.getRootVal())
print("Left child:", r.getLeftChild())
print("Tree:", r)
r.getLeftChild().insertLeft('d')
r.getLeftChild().insertRight('e')
print("Tree:", r)
r.getRightChild().insertLeft('f')
r.getRightChild().insertRight('g')
print("Tree:", r)
# a
# / \
# b c
# / \ / \
# d e f g
Root: a Left child: [b] Tree: [b]/a\[c] Tree: [d]/b\[e]/a\[c] Tree: [d]/b\[e]/a\[f]/c\[g]