Theory and Tasks for Students - Spring 2019
Функции и рекурсия

Чтобы не повторять какой-то блок кода много раз, можно определить функцию. Следующая блок кода заполняет список значениями x2+2x-9: def f(x) : return x * x + 2 * x - 9; a = [f(i) for i in range(0, 101)];

В списке аргументов можно указать значения по умолчанию, такие аргументы будут необязательными: def myPrint(arr, sep = " ") : s = ""; for item in arr s += str(item) + sep; print(s); myPrint([1, 2]); #1 2 myPrint([1, 2], ", "); #1, 2

Так же функция можно принимать любое число аргументов, после обязательных и опциональных: def myPrint2(sep = " ", *items) : s = ""; for item in items s += str(item) + sep; print(s); myPrint(" ", 1, 2, 3); #1 2 3 myPrint(", ", 5, "abc"); #5, abc

При вызове функции можно указать конкретные имена аргументов для передачи значений. Таким образом аргументы можно перечислять в любом порядке: myPrint(sep = "\n", arr = [i for in range(100)]);

Как видно из примеров выше, одна функция может вызывать в своём теле любую другую функцию. Так же она может вызывать саму себя - это называется рекурсией. Простейшая рекурсия похожа на условный цикл: очередной вызов функции - итерация цикла, условие выхода из рекурсии - условие выхода из цикла. def factorial(n) : if (n == 0) : return 1; return n * factorial(n - 1); Однако, в таких простых случаях лучше использовать простой и понятный цикл - в т.ч. потому что он использует меньше ресурсов, а основная особенность - обратный ход по стеку рекурсии - не исползуется.

Другой пример использования рекурсии - обход дерева решений/переходов. Здесь список списков g содержит все возможные переходы из одного состояния в другое, т.е. g[i] содержит все номера состояний, доступные из состояния с номером i. Пример ниже представляет собой полную программу, вместе с чтением данных из файла: fin = open("a.in", "r"); str = fin.read(); fin.close(); lines = str.split("\n"); for i in range(len(lines)) : lines[i] = lines[i].split(" "); n = int(lines[0][0]); g = [[] for i in range(n)]; visited = [False] * n; for i in range(n) : for j in lines[i + 1] : if (len(j) != 0) : g[i].append(int(j)); def DFS(i, steps = 0) : global visited, g; visited[i] = True; for j in g[i] : if (not visited[j]) : print("Visiting %d" % (j)); DFS(j, steps + 1); print("Returning from %d" % (j)); else : print("%d already visited" % (j)); DFS(0); Если состояние не посещено, выполняется переход в него с увеличением длины пройденного пути на единицу. Таким образом каждый раз будут посещены все новые состояния. Если новых состояний нет, функция завершает работу - т.е. происходит возврат по стеку рекурсии. Этот алгоритм называется поиском/обходом в глубину - Depth First Search - он используется для решения некоторых простых задач на математической структуре называемой графом - множество вершин(состояний) и ребёр(переходов) их соединяющих.