На этом шаге мы рассмотрим несколько простых заданий и приведем их решения.

    Приведем несколько примеров решения задач.

    Задание 1. Рассмотрим функцию суммирования первых n положительных целых чисел (1.5). Определите обобщённую функцию, которая применима также ко всем неотрицательным целым числам. Другими словами, измените функцию с учётом того, что она может получать в качестве аргумента n = 0. После этого закодируйте функцию.

Раскрыть/скрыть решение и комментарии.

        0, если n = 0
S(n) =                                      
        S(n - 1) + n, если n > 0

def f_1(n):
    if n == 0:
        return 0
    else:
        return n + f_1(n - 1)  

    Задание 2. Рассмотрим задачу вывода на экран цифр некоторого неотрицательного целого числа n вертикально в прямом порядке, где старший разряд должен появиться в 1-й строке, следующий за ним – во 2-й и т. д. Например, если n = 2743, программа должна выдать на экран следующие строки:

2
7
4
3

Раскрыть/скрыть решение и комментарии.

def f_2(n):
    if n < 10:
        print(n)
    else:
        print(n // 10 ** (len(str(n)) - 1))  
        f_2(n % 10 ** (len(str(n)) - 1))

    Задание 3. Определите рекурсивную функцию, вычисляющую наибольшее значение в списке из n элементов, когда декомпозиция просто уменьшает размер задачи на 1.

Раскрыть/скрыть решение и комментарии.

def f_3(a):
    if len(a) == 1:
        return a[0]
    else:
        return max(f_3(a[0:len(a) - 1]), a[len(a) - 1])  


# Some list:
v = [5, -1, 3, 2, 4, 7, 2]
print(f_3(v))

    Со следующего шага мы начнем рассматривать анализ времени выполнения рекурсивных алгоритмов.

Предыдущий шаг Содержание Следующий шаг