Что такое и не рекурсия?

Question

Я пытаюсь понять, что именно является рекурсией и не удалось найти ответ на следующее.

Мое настоящее понимание рекурсии заключается в том, что это когда-либо метод вызывает себя.

т.е.

Menu() 
{ 
if(i<2) 
{Console.WriteLine();} 
else 
{Menu();}  
} 

Выше приведен пример рекурсии метод вызова себя.

То, что я не уверен, что это сценарий, как:

Menu() 
{ 
if(i<2) 
{Console.WriteLine();} 
else 
{Console.WriteLine("Something Went Wrong!"); MenuError();}  
} 

MenuError() 
{ 
Console.WriteLine("Something went wrong!"); 
Menu(); 
} 

Если метод вызывает метод, который затем вызывает его это еще рекурсии?

Answer 1

Мое нынешнее понимание рекурсии заключается в том, что это когда-либо вызов метода .

Это правильно. Рекурсивные определения являются определениями самореференции.

Два интересных свойства рекурсивных определений: Производительность и Прекращение. Программа продуктивна, если она по-прежнему дает выход, хотя полная выходная мощность может никогда не появиться (следовательно, она не может завершиться). Программа завершается, если она дает полный выход за конечное время.

Например, это продуктивно, не-терминатор программа:

Naturals(int i) { 
    Console.WriteLine(i); 
    Naturals(i + 1); 
} 

Это программа терминатор:

UpToTen(int i) { 
    Console.WriteLine(i); 
    if (i < 10) UpToTen(i + 1); 
} 

Это непродуктивный программа:

DoNothing() { 
    DoNothing(); 
} 

---

Если Menu звонки MenuError и MenuError звонки Menu, это иногда называют взаимной рекурсии. Единственная разница - наша организация; мы можем переписать код, чтобы иметь только один метод, введя в таблицу MenuError.

Menu() { 
    if (i < 2) { 
    Console.WriteLine(); 
    } 
    else { 
    Console.WriteLine("Something Went Wrong!"); 
    Console.WriteLine("Something went wrong!"); 
    Menu(); 
    } 
} 

Вы можете на самом деле абстрактная рекурсия сами:

// General definition 
A Fix<A>(Func<Func<A>,A> f) { 
    return f(() => Fix(f)); 
} 

// Special definition for void functions 
void Fix(Action<Action> f) { 
    f(() => Fix(f)); 
} 

void Menu(Action menu) { 
    if (i < 2) { 
    Console.WriteLine(); 
    } 
    else { 
    Console.WriteLine("Something Went Wrong!"); 
    Console.WriteLine("Something went wrong!"); 
    menu(); 
    } 
} 

Fix(Menu); 

Вот другой пример использования Fix определить функцию факториала.

Func<int, int> Fac(Func<Func<int, int>> fac) { 
    return i => i == 0 ? 1 : i * fac()(i - 1); 
} 

// Fix<Func<int, int>>(Fac) is the factorial function 

Вы можете задаться вопросом, почему Fix не имеет подписи A Fix<A>(Func<A,A> f) вместо этого. Это связано с тем, что C# является строгим языком, что означает, что он оценивает аргументы, прежде чем оценивать приложение функции. С более простой сигнатурой программа C# закончится бесконечной рекурсией.

Answer 2

Да, это еще рекурсия. Существуют различные типы рекурсии, такие как рекурсия хвоста, рекурсия деревьев и т. Д. Вы можете проверить google для отдыха.

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