РЕКУРСИЯ

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

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

Основная рекурсия. Первый пример рекурсии — классическая функция факториала. Факториал числа n — это произведение всех положительных целых чисел, меньших или равных n.

function factorial(n) {
  if (n === 0) {
    return 1;
  } else {
    return n * factorial(n-1);
  }
}

A. Базовый вариант. Важно иметь базовый вариант в рекурсии, так как он предотвращает бесконечное выполнение функции. В приведенном выше примере базовый случай — это когда n == 0, а функция возвращает 1.

B. Рекурсивный случай. Рекурсивный случай — это когда функция вызывает сама себя с другим вводом. В факториальном примере рекурсивный случай — это когда функция вызывает себя с входом n-1.

C. Хвостовая рекурсия.Хвостовая рекурсия — это частный случай рекурсии, когда рекурсивный вызов — это последнее, что происходит в функции.

function tailFactorial(n, accumulator=1) {
    if (n === 0) {
        return accumulator;
    } else {
        return tailFactorial(n-1, n*accumulator);
    }
}

2.Мемоизация. Мемоизация — это метод, который можно использовать для оптимизации рекурсивных функций. Мемоизация сохраняет результаты предыдущих вызовов функций, поэтому функции не нужно повторно вычислять те же значения.

function fibonacci(n, memo = {}) {
    if (n === 0) {
        return 0;
    } else if (n === 1) {
        return 1;
    } else if (n in memo) {
        return memo[n];
    } else {
        memo[n] = fibonacci(n-1) + fibonacci(n-2);
        return memo[n];
    }
}

3. Разделяй и властвуй: Разделяй и властвуй — это метод, который можно использовать для рекурсивного решения проблем, разбивая их на более мелкие подзадачи.

function binarySearch(arr, x, low=0, high=-1) {
    if (high === -1) {
      high = arr.length - 1;
    }
    if (low > high) {
      return false;
    } else {
      var mid = Math.floor((low + high) / 2);
      if (arr[mid] === x) {
        return true;
      } else if (arr[mid] > x) {
        return binarySearch(arr, x, low, mid-1);
      } else {
        return binarySearch(arr, x, mid+1, high);
      }
    }
}

4. Отслеживание с возвратом. Отслеживание с возвратом – это метод, который можно использовать для поиска всех возможных решений проблемы путем последовательного построения решения и отмены предыдущих шагов, если они ведут в тупик.

function generatePermutations(arr, index = 0) {
    if (index === arr.length) {
        console.log(arr);
    } else {
        for (let i = index; i < arr.length; i++) {
            [arr[index], arr[i]] = [arr[i], arr[index]];
            generatePermutations(arr, index + 1);
            [arr[index], arr[i]] = [arr[i], arr[index]];
        }
    }
}

5.Динамическое программирование.Динамическое программирование – это метод, который можно использовать для рекурсивного решения задач путем разбиения их на более мелкие подзадачи и сохранения результатов предыдущих подзадач, чтобы избежать повторения. работа.

dfunction longestCommonSubsequence(str1, str2) {
    if (!str1 || !str2) {
        return "";
    } else if (str1[str1.length-1] === str2[str2.length-1]) {
        return longestCommonSubsequence(str1.slice(0, -1), str2.slice(0, -1)) + str1[str1.length-1];
    } else {
        var option1 = longestCommonSubsequence(str1, str2.slice(0, -1));
        var option2 = longestCommonSubsequence(str1.slice(0, -1), str2);
        return option1.length > option2.length ? option1 : option2;
    }
}

6. Рекурсивные структуры данных. Рекурсивные структуры данных — это структуры данных, определяемые рекурсивно, например связанные списки и деревья.

class Node {
  constructor(data, next = null) {
    this.data = data;
    this.next = next;
  }
}

class LinkedList {
  constructor(head = null) {
    this.head = head;
  }
}

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

РЕКУРСИЯ

Похожие вопросы