Базовый случай в рекурсивном методе

Question

Теоретический вопрос о базовом или остановочном случае в рекурсивном методе, каковы его стандарты?

Я имею в виду, это нормально, если в нем нет тела, просто выражение return ?

Всегда ли это так:

if (input operation value)
    return sth;

У вас есть другие мысли об этом?

Answer 1

Шаблон для рекурсивных функций таков, что они выглядят примерно так:

f( value ) 
   if ( test value )
      return value
   else
      return f( simplify value )

Не думаю, что вы можете сказать гораздо больше об общих случаях.

Answer 2

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

Например, это совершенно правильно:

int factorial (int n) {
  if (n <= 5) {
    // Not just a return statement
    int x = 1;
    while (n > 0) {
      x *= n;
      -- n;
    }
    return x;
  } else {
    return n * factorial(n-1);
  }
}

Answer 3

В некоторых случаях ваш базовый случай

return literal

В некоторых случаях ваш базовый случай - это не просто «вернуть литерал».

Не может быть «стандарта» - это зависит от вашей функции.

«Функция Сиракузы» http://en.wikipedia.org/wiki/Collatz_conjecture, например, не имеет тривиального базового случая или тривиального литерального значения.

"У тебя есть другие мысли об этом?" Это не очень разумный вопрос.

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

Answer 4

Это полностью зависит от конкретной рекурсивной функции. В общем, это не может быть пустой оператор return;, однако - для любой рекурсивной функции, которая возвращает значение, базовый случай также должен возвращать значение этого типа, поскольку func(base) также является совершенно допустимым вызовом. Например, рекурсивная функция factorial вернет 1 в качестве базового значения.