Простой рекурсивный вызов: примеры рекурсивных методов в программировании

В контексте программирования «простой рекурсивный вызов» относится к рекурсивной функции или методу, который вызывает сам себя для решения проблемы. Вот несколько примеров методов, использующих простые рекурсивные вызовы:

  1. Вычисление факториала:
    Рекурсивный метод вычисления факториала числа. Факториал целого неотрицательного числа n обозначается через n! и является произведением всех натуральных чисел, меньших или равных n.

    def factorial(n):
       if n == 0:
           return 1
       else:
           return n * factorial(n-1)
  2. Последовательность Фибоначчи:
    Рекурсивный метод создания последовательности Фибоначчи. Последовательность начинается с 0 и 1, и каждое последующее число представляет собой сумму двух предыдущих.

    def fibonacci(n):
       if n <= 1:
           return n
       else:
           return fibonacci(n-1) + fibonacci(n-2)
  3. Двоичный поиск:
    Рекурсивный метод выполнения двоичного поиска в отсортированном массиве. Он делит массив пополам и сравнивает средний элемент с целевым, затем рекурсивно ищет левую или правую половину в зависимости от результата сравнения.

    def binary_search(arr, target, low, high):
       if low > high:
           return -1
       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)