Рекурсия в Python. Примеры решения задач
Содержание
- 1. Понятие рекурсии. Рекурсивные функции
- 2. Примеры решения задач на рекурсию
- 2.1. Функция CalcSumNumbers(). Вычислить сумму элементов набора чисел
- 2.2. Функция CalcSumNegativeNumbers(). Вычислить количество отрицательных чисел в наборе
- 2.3. Функция CalcSumNumbers(). Вычисление суммы чисел с поддержкой вложенных списков
- 2.4. Функция GetFibonacciList(). Возврат ряда Фибоначчи
- 2.5. Функция ReverseNumber(). Реверсирование числа
- 2.6. Функция Power(x, y). Возведение числа x в степень y
- 2.7. Функция GetMaxList(). Определение максимального элемента списка
- 2.8. Функция Convert_10_to_2(). Перевод из десятичной системи исчисления в двоичную
- Связанные темы
Поиск на других ресурсах:
1. Понятие рекурсии. Рекурсивные функции
Рекурсия — это способ организации циклического процесса путем вызова рекурсивной функции. Рекурсивная функция — это функция, которая содержит код вызова самой себя с целью организации циклического процесса. С помощью рекурсивных функций можно с минимальным объемом кода решать некоторые задачи, обойдя использование (объявление) лишних структур данных. Рекурсию можно рассматривать как альтернативу циклам и итерациям.
⇑
2. Примеры решения задач на рекурсию
2.1. Функция CalcSumNumbers(). Вычислить сумму элементов набора чисел
В примере реализована рекурсивная функция CalcSumNumbers(), которая осуществляет суммирование чисел во входящем списке. В работе функции входящий список A разделяется на 2 части:
- первый элемент списка A[0];
- все остальные элементы списка кроме первого. Эти элементы выделяются при помощи среза A[1:].
Вытащив первый элемент из списка с помощью среза, можно передать этот новосозданный список в следующий рекурсивный вызов функции.
# Рекурсивная функция - возвращает сумму чисел во входящем наборе def CalcSumNumbers(A): if A == []: # если набор пуст, возвратить 0 return 0 else: # Вычислить сумму - прибавить первый элемент набора summ = CalcSumNumbers(A[1:]) # рекурсивный вызов этой же функции # Прибавить к общей сумме первый элемент summ = summ + A[0] return summ # Демонстрация использования функции CalcSumNumbers() # 1. Создать набор чисел L = [ 2, 3, 8, 11, 4, 6 ] # 2. Вызвать функцию summ = CalcSumNumbers(L) # 3. Распечатать сумму print("summ = ", summ)
Результат выполнения программы
summ = 34
⇑
2.2. Функция CalcSumNegativeNumbers(). Вычислить количество отрицательных чисел в наборе
По предыдущим примеру (п. 4.1) реализуется функция CalcSumNegativeNumbers(), которая вычисляет количество отрицательных чисел в списке (наборе). Опять же, из входного списка выделяется первый элемент и все другие элементы.
# Рекурсивная функция - возвращает количество отрицательных чисел в списке def CalcSumNegativeNumbers(A): if A == []: # если набор пуст, вернуть 0 return 0 else: # Вычислить количество, перейти к дальнейшей обработке # без без первого элемента count = CalcSumNegativeNumbers(A[1:]) # рекурсивный вызов этой же функции # Увеличить на 1 при условии, что текущее число отрицательно if A[0]<0: count = count + 1 return count # Демонстрация использования функции CalcSumNumbers() # 1. Создать набор чисел L = [ -2, 3, 8, -11, -4, 6 ] # 2. Вызвать функцию n = CalcSumNegativeNumbers(L) # 3. Распечатать сумму print("n = ", n)
Результат выполнения программы
n = 3
⇑
2.3. Функция CalcSumNumbers(). Вычисление суммы чисел с поддержкой вложенных списков
Если нужно, чтобы рекурсивная функция обрабатывала вложенные списки, то в теле функции нужно реализовать цикл обхода элементов списка. Затем этот элемент нужно проверять, является ли он списком по образцу
if not isinstance(t, list): ...
здесь t – элемент, который проверяется с помощью функции isinstance().
# Рекурсивная функция - возвращает сумму чисел, обрабатывает вложенные списки def CalcSumNumbers(A): summ = 0 # здесь нужно реализовать обход в цикле for t in A: # Обрабатывается элемент t if not isinstance(t, list): # проверить, есть ли t списком summ = summ + t # если t - не список, то прибавить его к сумме else: # получить сумму из следующих рекурсивных вызовов summ = summ + CalcSumNumbers(t) return summ # Демонстрация использования функции CalcSumNumbers() # 1. Создать набор чисел L = [ -2, 3, 8, 11, [-4, 6, [ 2, [-5, 4] ] ] ] # 2. Вызвать функцию summ = CalcSumNumbers(L) # 3. Распечатать сумму print("summ = ", summ)
Результат выполнения программы
summ = 23
⇑
2.4. Функция GetFibonacciList(). Возврат ряда Фибоначчи
Ряд Фибоначчи содержит числа, в которых следующее число определяется как сумма двух предыдущих чисел:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...
Нижеприведенная рекурсивная функция формирует ряд Фибоначчи в виде списка для заданного максимального значения в списке.
# Рекурсивная функция - возвращает ряд Фибоначчи в виде списка. # Параметр n - максимальное значение в списке. def GetFibonacciList(n, L): # Проверить, корректна ли длина списка count = len(L) if len(L)<2: return [] # Получить последние числа в списке L num1 = L[count-2] num2 = L[count-1] # Формула расчета следующего числа if (num1+num2) < n: L = L + [num1+num2] return GetFibonacciList(n, L) # вызвать рекурсивно функцию else: return L # если достигнут конец, то обычный выход # Вызвать функцию GetFibonacciList() LL = GetFibonacciList(100, [0, 1]) print("LL = ", LL)
Результат выполнения программы
LL = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
⇑
2.5. Функция ReverseNumber(). Реверсирование числа
В примере приводится функция ReverseNumber() представления числа в обратном порядке. Например, для числа 12345 результат будет 54321.
Функция получает входным параметром целое число number. Функция возвращает целое реверсированное число.
# Рекурсия. Реверсирование числа import math # Рекурсивная Функция def ReverseNumber(num): # 1. Проверка, корректно ли число if num<0: return -1 # 2. Проверка, равно ли число 0 if num==0: return 0 # 3. Если число корректно (num>0), то обработать его # 3.1. Определить порядок числа (количество цифр в числе) n_digit = 0 # порядок числа num2 = num # копия num while num2>0: n_digit = n_digit+1 num2 = num2//10 # 3.2. Взять последнюю цифру из числа t = num%10 # 123456 => 6 # 3.3. Умножить последнюю цифру на 10^n_digit res = t * int(math.pow(10, n_digit-1)) # 3.4. Вернуть сумму с вызовом рекурсивной функции return res + ReverseNumber(num//10) # Демонстрация использования функции num = 1234000567 rnum = ReverseNumber(num) # rnum = 7650004321 print("rnum = ", rnum)
Результат выполнения функции
rnum = 7650004321
⇑
2.6. Функция Power(x, y). Возведение числа x в степень y
Рекурсивная функция Power(x, y) возвращает результат возведения действительного числа x в целую степень y. Предварительно предполагается, что значение y>0.
# Рекурсия. Возведение числа x в степень y # Рекурсивная функция def Power(x, y): if y>0: return x * Power(x, y-1) else: return 1 # Демонстрация использования функции Power() x = 3 y = 4 res = Power(x, y) print("res = ", res)
Результат выполнения программы
res = 16
⇑
2.7. Функция GetMaxList(). Определение максимального элемента списка
В примере реализована функция GetMaxList(), которая вычисляет максимальный элемент списка. Вся работа функции разделена на 2 части:
- выполнение действий, если в списке два и более чисел;
- выполнение действий, если список заканчивается, то есть рассматривается последний элемент.
Каждый рекурсивный вызов функции рассматривает список как две составляющие:
- первый элемент списка (элемент с индексом 0);
- следующие за первым элементы списка (элементы с индексами 1, 2, и т.д.).
# Рекурсивная функция. Определить максимальный элемент списка def GetMaxList(L): if len(L)>1: # Получить максимум из следующих рекурсивных вызовов Max = GetMaxList(L[1:]) # Сравнить максимум с первым элементом списка if L[0]<Max: return Max else: return L[0] if len(L)==1: # последний элемент в списке return L[0] # вернуть этот элемент # Демонстрация использования функции Power() L = [ 500, 2300, 800, 114, 36] res = GetMaxList(L) print("res = ", res)
Результат выполнения программы
res = 2300
⇑
2.8. Функция Convert_10_to_2(). Перевод из десятичной системи исчисления в двоичную
В данном примере, с целью сравнения, реализованы 2 функции, которые конвертируют целое число из десятичной системы исчисления в его аналог в двоичной системе исчисления:
- Convert_10_to_2_R() — это рекурсивная функция конвертирования числа;
- Convert_10_to_2() — не рекурсивная функция.
Для обеспечения решении задачи, в нерекурсивной версии Convert_10_to_2() вводится дополнительная переменная k, которая определяет порядок полученного двоичного числа. Для того, чтобы сохранять этот порядок k в рекурсивной версии функции Convert_10_to_2_R(), нужно его передавать в эту функцию вторым параметром.
import math # Рекурсивная функция. Перевод числа из 10-й системы исчисления в двоичную. # Функция возвращает результат в виде числа: 13 => 1101. # Параметры: # - n - число в десятичной системе исчисления; # - k - текущий порядок (количество цифр) числа в двоичной системе. def Convert_10_to_2_R(n, k): if n>0: t = n%2 return Convert_10_to_2_R(n//2, k+1) + int(t*math.pow(10,k)) else: return 0 # Не рекусивная функция перевода def Convert_10_to_2(n): summ = 0 # сумма чисел: 5 => 100 + 0 + 1 => 101 k = 0 # порядок числа в двоичной системе исчисления while n>0: t = n%2 summ = summ + int(t*math.pow(10,k)) k = k+1 n = n//2 return summ # Демонстрация использования функций res1 = Convert_10_to_2_R(126, 0) # Вызов рекурсивной функции res2 = Convert_10_to_2(126) # Вызов нерекурсивной функции print("res1 = ", res1) print("res2 = ", res2)
Результат выполнения программы
res1 = 1111110 res2 = 1111110
⇑
Связанные темы
- Понятие функции. Общая форма. Примеры объявления и использования функций
- Передача аргументов в функцию. Изменение аргументов в теле функции
⇑