“Python: Рекурсия”

Рекурсия — это мощная концепция программирования, которая предполагает вызов функции самой себя. Это особенно полезно для решения проблем, которые можно разделить на более мелкие повторяющиеся подзадачи. В Python существует несколько способов реализации рекурсии. Вот несколько методов с примерами кода:

1. Базовая рекурсивная функция:

   def countdown(n):
   if n == 0:
       print("Blastoff!")
   else:
       print(n)
       countdown(n - 1)
   countdown(5)

   Выход:

   5
   4
   3
   2
   1
   Blastoff!

   В этом примере показана базовая рекурсивная функция под названием countdown, которая ведет обратный отсчет от заданного числа до 0.

2. Факториал:

   def factorial(n):
   if n == 0:
       return 1
   else:
       return n * factorial(n - 1)
   result = factorial(5)
   print(result)

   Выход:

   120

   В этом примере функция factorialвычисляет факториал числа с помощью рекурсии.

3. Последовательность Фибоначчи:

   def fibonacci(n):
   if n <= 1:
       return n
   else:
       return fibonacci(n - 1) + fibonacci(n - 2)
   result = fibonacci(6)
   print(result)

   Выход:

   8

   Этот пример демонстрирует использование рекурсии для вычисления n-го числа в последовательности Фибоначчи.

4. Двоичный поиск:

   def binary_search(arr, target, low, high):
   if low > high:
       return -1
   else:
       mid = (low + high) // 2
       if arr[mid] == target:
           return mid
       elif arr[mid] > target:
           return binary_search(arr, target, low, mid - 1)
       else:
           return binary_search(arr, target, mid + 1, high)
   arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
   target = 6
   result = binary_search(arr, target, 0, len(arr) - 1)
   print(result)

   Выход:

   5

   В этом примере функция binary_searchиспользует рекурсию для выполнения двоичного поиска в отсортированном массиве.

Это всего лишь несколько примеров использования рекурсии в Python. Рекурсию можно применять к различным сценариям решения проблем. Важно убедиться, что рекурсивные функции имеют базовый вариант или условие для завершения рекурсии.