Возможна ли вложенная рекурсия или мы должны избегать рекурсии?

Question

Я сталкивался с таким вопросом

• F (1) = 1
• F (2n) = F (n)
• F (2n +1) = F (n) + F (n + 1)

Разработать рекурсивную программу для вычисления F

Некоторые пользователи упомянули использование двух рекурсивных вызовов функций:

def calc(n):
  if n=1 :
    return 1
  else if(n%2)==0:
    return calc(n/2)
  else :
    return calc(n/2)+calc(n/2+1)  **NESTED RECURSION**

Это правильная логика?Не будет ли алгоритм экспоненциально большим?Я подумал о простом коде вроде:

def calc(count):
  result[1]=1
  n=2
  for range(1,count):
      if n%2=0:
          result.append(result[n])
      else :
          result.append(result[n/2]+result[n/2+1])
  return result

Answer 1

Оба эти подхода верны. Действительно допустимо иметь несколько рекурсивных вызовов из функции, и смысл в том, что вы думаете - просто выполните один вызов, затем следующий, затем следующий и т. Д.

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

T(1) = 1
T(2) = 1
T(n) <= T(n / 2) + T(n / 2 + 1) + 1

Я использую «меньше или равно здесь», чтобы сказать, что в лучшем случае вы могли бы просто сделать один звонок, но в худшем случае вы сделаете максимум два.

Я хочу доказать, что эта функция T (n) <= max {cn + d, a} для некоторых констант c, d и a. Это докажет, что T (n) = O (n) и, таким образом, делает самое большее линейно много вызовов. В качестве нашего базового случая мы имеем, что </p>

T(1) = 1
T(2) = 1

так что давайте установим a = 1. Для индуктивного шага мы рассмотрим три случая. Сначала рассмотрим, когда floor (n / 2) <= 2 и floor (n / 2 + 1) <= 2: </p>

T(n) <= T(n / 2) + T(n / 2 + 1) + 1
     <= 1 + 1 + 1
     <= 3

Если предположить, что cn + d> = 3, когда n = 3 или n = 4, то это работает правильно. В частности, это означает, что 3c + d> = 3 и 4c + d> = 3.

В следующем случае, давайте посмотрим, что произойдет, если floor (n / 2) <= 2 и floor (n / 2 + 1)> = 2. Тогда мы получим это

T(n) <= T(n / 2) + T(n / 2 + 1) + 1
     <= 1 + max{c(n / 2 + 1) + d, 1} + 1
     <= 2 + max{c(n / 2 + 1) + d, 1}
     <= 3 + c(n / 2 + 1) + d

Итак, если у нас есть 3 + c (n / 2 + 1) + d <= cn + d, это утверждение остается в силе. Обратите внимание, что мы только в этом случае, если n = 5, и это означает, что мы должны иметь это </p>

3 + c(n / 2 + 1) + d <= cn + d
3 + c(n / 2 + 1)     <= cn
3 + c(5 / 2 + 1)     <= 5c
3 + 5c/2 + c         <= 5c
3 + 7c/2             <= 5c
4                    <= 3c / 2
8 / 3                <= c

Итак, мы должны иметь это с> = 8/3.

И, наконец, случай, когда ни n / 2, ни n / 2 + 1 не меньше трех:

T(n) <= T(n / 2) + T(n / 2 + 1) + 1
     <= c(n / 2) + d + c(n / 2 + 1) + d + 1
     <= cn / 2 + cn / 2 + c + 2d + 1
      = cn + c + 2d + 1

Это меньше, чем cn + d, если

 cn + c + 2d + 1 <= cn + d
      c + 2d + 1 <=      d
      c +  d + 1 <= 0

Это работает, если d = -c - 1.

Ранее мы знали, что 3c + d> = 3, что работает, если 2c - 1> = 3 или 2c> = 4, поэтому c> = 2. У нас также есть 4c + d> = 3, что также работает, если c> = 2. Допуская c = 8/3, мы получаем, что d = -11 / 3, поэтому

T(n) <= max{8n/3 - 11/3, 1}

Так что T (n) = O (n) и рекурсия делает только линейно много вызовов.

---

Короткая версия этого заключается в том, что и рекурсивная, и итерационная версии требуют линейного времени. Не бойтесь экспоненциального разрыва рекурсии, не будучи уверенным, что он экспоненциальный. :-) Хотя по общему признанию, в этом случае мне действительно больше нравится итеративная версия. Это более понятно, более интуитивно понятно и более быстро O (n).

Answer 2

Вы можете написать рекурсивную версию, которая на самом деле является сублинейной (O (log n)).

Ключ должен заметить, что вы можете вычислить два значения для n и n + 1, учитывая два значения для [n / 2] и [n / 2] + 1.

Итак, если вы думаете о двух значениях как one tuple T (n) = (F (n), F (n + 1)), то с учетом T ([n / 2]), Вы можете вычислить T (n).

То есть ваша функция будет выглядеть примерно так:

Tuple F(int n) {
    // Base cases:

    Tuple result;
    if (n is even) {
        Tuple t = F(n/2);
        result.First = t.First;
        result.Second =t.First + t.Second;

        return result;
    }

    if (n is odd) {

        Tuple t = F((n-1)/2);
        result.First = t.First + t.Second;
        result.Second = t.Second;
        return result;
    } 
}

Таким образом, вы в конечном итоге делаете только один рекурсивный вызов, и, поскольку вы вдвое уменьшаете размер ввода для каждого вызова, он становится рекурсивным и O (logn).

Упражнение : Дайте алгоритм времени O (log n) для чисел Фибоначчи, используя этот трюк.

Подсказка: используйте тождества:

Answer 3

Проще оценить производительность вашего второго алгоритма: он явно равен O (n) в пространстве и времени с небольшой константой. Но это не значит, что второй алгоритм быстрее первого. На самом деле это не так!

В Python 2.6.5 ваш второй алгоритм в 25x медленнее , чем первый при вычислении calc(1000), в 80 раз медленнее при вычислении calc(10000) и в 1712 раз медленнее при вычислении calc(65535).

Кажется, что наихудшее поведение для первого алгоритма относится к числам вроде 54613 = 1101010101010101 ₂ . Для этого значения первый алгоритм только в 16 раз быстрее второго.

В простом рекурсивном алгоритме calc(1000) включает только 50 вызовов calc, и даже calc(54613) требует только 5166.

Этот алгоритм O (log n) еще быстрее:

def C(x):
    a = 1
    b = 0
    # Loop invariant: we are going to return a*C(x) + b*C(x + 1).
    while x >= 2:
        if x % 2 == 0:
            a += b
        else:
            b += a
        x //= 2
    return a + b

Производительность этого алгоритма легко оценить, но его правильность - нет. ; -)

Answer 4

Рекурсия неплохая. Думайте о рекурсии как о инструменте. Некоторые проблемы могут быть решены довольно хорошо с помощью рекурсии (например, числа Фибоначчи), в то время как другие проблемы не имеют рекурсивного изгиба (алгоритм типа рабочего списка).

Почему люди ошибаются с рекурсией, потому что они думают, что рекурсивное решение даст им хорошую репутацию. Я бы сказал, решить проблему с помощью самого простого подхода.

Иногда такой подход - рекурсия, иногда - нет.

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