Как преобразовать цикл в рекурсию, если нам нужно использовать индекс как условие? - PullRequest
Новая
       8

Как преобразовать цикл в рекурсию, если нам нужно использовать индекс как условие?

2 голосов
/ 24 октября 2019

Допустим, мы хотим реализовать алгоритм sum, я использую C # в качестве иллюстрации здесь: 

// Iterative
int sum(int[] array) {
    int result = 0;
    foreach(int item in array) {
        result += item;
    }
    return item;
}

, что эквивалентно 

// Recursive
int sum(int[] array) {
    if(array.Length == 0) {
        return 0;
    }
    // suppose there is a SubArray function here
    return array[0] + sum(array.SubArray(1));
}

Это просто.

Однако, если мы хотим добавить в алгоритм условие, в котором мы не хотим добавлять целое число с индексом 2 к нашему результату, нам нужно добавить только один условный оператор в нашу первую (итеративную) реализацию.

В: Есть ли адаптация к нашему рекурсивному, чтобы он работал?

Ответы [ 2 ]

1 голос
/ 26 октября 2019

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

В C #: 

private static int SumSkipIndex(int[] arr, int skip, int i) 
{
    if (i >= arr.Length) return 0;

    return (i == skip ? 0 : arr[i]) + SumSkipIndex(arr, skip, i + 1);
}

Если вам не нравится добавленный параметр i, который изменяет заголовок функции, просто напишите отдельную частную рекурсивную «вспомогательную» функцию, которую можно вызывать из оболочки с вашим предпочтительным заголовком.

Я также предполагаю, что вы не хотите жесткий код index 2 в алгоритм (если вы это сделаете, удалите параметр skip и замените i == skip на i == 2). 

using System;

class MainClass 
{
    private static int SumSkipIndex(int[] arr, int skip, int i) 
    {
        if (i >= arr.Length) return 0;

        return (i == skip ? 0 : arr[i]) + SumSkipIndex(arr, skip, i + 1);
    }

    public static int SumSkipIndex(int[] arr, int skip) 
    {
        return SumSkipIndex(arr, skip, 0);
    }

    public static void Main(string[] args) 
    {
        Console.WriteLine(SumSkipIndex(new int[]{16, 11, 23, 3}, 1)); // => 42
    }
}

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

0 голосов
/ 26 октября 2019

Консусное решение может быть сделано в C # 8 с использованием срезов массива. 

public static int SumArray(int[] arr, int exclude){
  if(arr.Length == 0){
    return 0;
  }
  return (exclude==0?0:arr[0]) + SumArray(arr[1..], exclude-1);
}

Тернарный оператор проверяет, равен ли индекс пропуска 0, а если нет, уменьшит индекс пропуска дляследующий рекурсивный вызов. Массив уменьшается с использованием среза, который должен быть более производительным, чем SubArray. (Кто-то на самом деле проверит меня на последнем)

РЕДАКТИРОВАТЬ: Как и предполагал другой ответ, это вызывает вздутие живота кадров стека из-за отсутствия рекурсии хвостового вызова. Приведенное ниже решение позволит смягчить проблему с помощью оптимизации хвостового вызова, добавив вместо нее переменную суммы. Это означает, что рекурсивный вызов может использовать тот же кадр стека, а не создавать новый, чтобы ожидать возвращаемое значение до завершения суммы. 

public static int SumArray(int[] arr, int exclude, int sum=0){
  if(arr.Length == 0){
    return sum;
  }
  return SumArray(arr[1..], exclude-1, sum + (exclude==0?0: arr[0]));
}
...