Рекурсия - это своего рода вызов функции, при котором функция вызывает себя. Такие функции также называются рекурсивными функциями. Структурная рекурсия - это метод решения проблемы, при котором решение проблемы зависит от решения меньших экземпляров одной и той же проблемы.

Термин рекурсия описывает структуру кода, в которой функция потенциально вызывает себя. Такие функции также называются рекурсивными функциями.

Структурная рекурсия - это метод решения проблемы, при котором решение проблемы зависит от решения более мелких или более простых примеров одной и той же проблемы.

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

Некоторые функциональные языки программирования не определяют циклические конструкции, а полагаются исключительно на рекурсию для многократного вызова кода. Аналогично, в языках, которые предоставляют циклы, любая рекурсивная функция может быть написана с использованием циклов, не требуя рекурсии.

Это определяет два основных подхода для многократного вызова некоторого фрагмента кода.

  • Итерационный подход (Использование циклических конструкций)
  • Рекурсивный подход (Использование рекурсии)

В дополнение к программному коду рекурсия также может происходить в структурах данных, где вложенный объект или массив может содержать ссылку на элемент, расположенный далее в дереве данных.

Примеры на нескольких языках

С

void recursiveFunction(int num) {
   if (num < 4)
      recursiveFunction(num + 1);
   printf("%d\n", num);
}

C ++

void recursiveFunction(int num) {
   if (num < 4)
      recursiveFunction(num + 1);
   cout<<num;
}

Джава

public static int factorial(int N) { 
   if (N == 1) return 1; 
   return N * factorial(N-1); 
}

OCaml

let rec factorial n =
    if n <= 1 then 1 else n * factorial (n - 1)

Haskell

factorial n = if n == 0 then 1 else n * factorial (n - 1)

Perl

sub factorial {
  if ($_[0] > 1) {
    return $_[0] * &factorial($_[0] - 1);
  } else {
    return 1;
  }
}

Haxe

function factorial(num:Int) { 
   if (num == 1) return 1; 
   return num * factorial(num - 1); 
}

Python (2 или 3)

def factorial(n):
    return 1 if n <= 1 else n * factorial(n - 1)

Использование тегов

recursionдолжна использоваться для проблем, связанных с программированием, при использовании рекурсии на любом языке программирования. На переполнении стека, пожалуйста, избегайте теоретических вопросов, таких как "как работает рекурсия?"

Рекомендации

Дальнейшая информация