Шаг 75.
Рекурсия на Python.
Линейная рекурсия I: основные алгоритмы. Примеры задач
На этом шаге мы рассмотрим несколько простых заданий и приведем их решения.
Приведем несколько примеров решения задач.
Задание 1.
Определите и закодируйте функцию вычисления количества цифр в неотрицательном целом числе n.
Раскрыть/скрыть решение и комментарии.
Функция должна возвращать 1 если само число не превосходит 10. В противном случае к единице прибавляем результат вызова этой же фунции, передавая ей число без последней цифры.
1, если n < 10
f(n) =
1 + f(n // 10), если n ≥ 10
Вот текст программы:
Задание 1.
1
2
3
4
5 |
def number_of_digits(n):
if n < 10:
return 1
else:
return 1 + number_of_digits(n // 10)
|
Архив с файлом можно взять
здесь.
Задание 2.
Закодируйте рекурсивную функцию, возвращающую количество гласных в заданной строке.
Раскрыть/скрыть решение и комментарии.
Условие выхода из рекурсии будет следующим: если строка пустая, то возвращается 0.
Разберем, как поступать, если строка не пуста. В этом случае, если первая буква гласная, то к результату прибавляем 1 и вызываем функцию, передавая в нее строку без первой буквы. В
противном случае просто вызываем функцию, передавая строку без первой буквы.
Вот текст программы:
Задание 1.
1
2
3
4
5
6
7
8 |
def number_of_vowels(s):
if s == '':
return 0
else:
if s[0] in 'ауоыиэяюёе':
return 1 + number_of_vowels(s[1:])
else:
return number_of_vowels(s[1:])
|
Архив с файлом можно взять
здесь.
Задание 3. В языке Python, как и в других языках программирования, метод может быть параметром другого метода. Определите и закодируйте общую рекурсивную функцию вычисления суммы:
n
g(m, n, f) = ∑ f(i) = f(m) + f(m + 1) + ... + f(n - 1) + f(n) ,
i=m
где
m и
n – целые числа, а
f – функция. Используйте её для вычисления и печати результата функции:
для
n = 0, …, 4.
Раскрыть/скрыть решение и комментарии.
Из приведенного условия следует, что рекурсию нужно закончить тогда, когда n == m. В этом случае возвращается значение, например, f(n).
Будем увеличивать m на 1. Следовательно, в случае n ≠ m будет возвращаться значение следующего выражения: f(m) + g(m + 1, n, f).
Вот текст приложения:
Задание 3.
1
2
3
4
5
6
7
8
9
10
11
12 |
def f(n):
s = 0
for i in range(1, n + 1):
s += i ** 3
return s
def g(m, n, f):
if m == n:
return f(n)
else:
return f(m) + g(m + 1, n, f)
|
Архив с файлом можно взять
здесь.
Вызов
приведет к выводу на экран числа 146.
Со следующего шага мы начнем рассматривать хвостовую рекурсию.
Предыдущий шаг 
Содержание
Следующий шаг