Рекурсия в 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

  ⇑

---

Связанные темы

• Понятие функции. Общая форма. Примеры объявления и использования функций
• Передача аргументов в функцию. Изменение аргументов в теле функции

  ⇑

---