Шаг 183.
Рекурсия на Python.
Вложенная рекурсия и снова хвостовая. Примеры задач
На этом шаге мы рассмотрим несколько заданий и приведем их решения.
Приведем несколько примеров решения задач.
Задание 1.
Отталкиваясь от итерационного решения, реализуйте хвостовой рекурсивный алгоритм, вычисляющий сумму первых n (n > 0) положительных целых чисел.
Выведите хвостовой рекурсивный алгоритм с использованием обобщённой функции.
Раскрыть/скрыть решение и комментарии.
Тексты функций достаточно просты. Оставляем разбор приведенных решений за вами.
Задание 1.
Хвостовой рекурсивный алгоритм:
1
2
3
4
5 |
def summ_rec(n):
if n == 0:
return 0
else:
return n + summ_rec(n - 1)
|
Хвостовой рекурсивный алгоритм с использованием обобщённой функции.
1
2
3
4
5
6
7
8
9 |
def summ_tail(n, s):
if n == 0:
return s
else:
return summ_tail(n - 1, s + n)
def summ_tail_recursive_wrapper(n):
return summ_tail(n, 0)
|
Архив с файлом можно взять
здесь.
Задание 2.
Рассмотрите задачу сложения элементов списка a из n чисел. Создайте хвостовую рекурсивную функцию, применив обобщения. После чего преобразуйте её в итерационную.
Раскрыть/скрыть решение и комментарии.
Данная задача перекликается с предыдущей. Приведем ее текст.
Задание 2.
Хвостовой рекурсивный алгоритм с использованием обобщённой функции.
1
2
3
4
5
6
7
8
9 |
def summ_tail_list(a, s):
if len(a) == 0:
return s
else:
return summ_tail_list(a[1:], s + a[0])
def summ_list_tail_recursive_wrapper(a):
return summ_tail_list(a, 0)
|
Итерационная функция.
1
2
3
4
5 |
def summ_list(a):
sm = 0
for i in a:
sm += i
return sm
|
Архив с файлом можно взять
здесь.
Задание 3.
Применив обобщение, создайте хвостовую рекурсивную функцию, вычисляющую степень bn, где b - вещественное число, а n - неотрицательное целое число.
После этого преобразуйте её в итерационную.
Раскрыть/скрыть решение и комментарии.
Приведем тексты требуемых функций.
Задание 3.
Хвостовой рекурсивный алгоритм с использованием обобщённой функции.
1
2
3
4
5
6
7
8
9 |
def pow_tail(b, n, p):
if n == 0:
return p
else:
return pow_tail(b, n - 1, p * b)
def pow_tail_recursive_wrapper(b, n):
return pow_tail(b, n, 1)
|
Итерационная функция.
1
2
3
4
5 |
def pow_iter(b, n):
p = 1
for i in range(n):
p *= b
return p
|
Архив с файлом можно взять
здесь.
Со следующего шага мы вернемся к множественной рекурсии.
Предыдущий шаг 
Содержание
Следующий шаг