Описание тега recursion

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

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

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

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

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

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

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

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

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

C

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)

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

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

Ссылки

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