C# рекурсия проверка если даже

Question

Мне нужна помощь, понимая это. Я действительно не понимаю этот кусок кода, и кто-то здесь может объяснить, что происходит?

Так это код:

static bool IsEven(int n) 
{ 
    if (n == 0) return true; 

    if (IsEven(n - 1)) 
    { 
     return false; 
    } 
    else 
    { 
     return true; 
    } 
} 

И тогда я делаю это:

Console.WriteLine(IsEven(10));

Как это на самом деле работает? Если я вхожу в число 10, он печатает значение true. Если я ввожу номер 7, он выводит false. Но я не понимаю, почему это работает.

Он проверяет, является ли число 0, тогда оно возвращает true. Но я ввел 10 (что явно не 0), и он все еще распечатывается верно. Затем он проверяет номер -1.

Итак, это будет 10-1, что равно 9. Но откуда он знает, что 9 НЕ? (он возвращает false).

Я не понимаю этот код, но он работает. Я так смущен.

Answer 1

Пройдитесь по нему логически, используя меньшее число, например 3, чтобы не было столько рекурсий.

В первый раз мы называем IsEven(3); он делает это:

if (3 == 0) return true; 

Ну 3 не равно 0, так что по-прежнему с этим:

if (IsEven(3 - 1)) 

который так же, как:

if (IsEven(2)) 

Итак, теперь мы находимся в следующем звонке по номеру IsEven. Первая проверка - 2 == 0, которой, конечно же, нет, поэтому она продолжается с IsEven(2 - 1).

Теперь мы в третьем звоните по номеру IsEven с номером IsEven(1). Еще раз 1 == 0 не соответствует действительности, поэтому он продолжается с IsEven(1 - 1).

Теперь мы в заключительном (четвертом) звоните по номеру IsEven с номером IsEven(0). Хорошо, теперь 0 == 0 верен, поэтому мы возвращаемся к третьему вызову true.

Итак, теперь в третьем вызове IsEven(1 - 1) есть true, поэтому он выполняет действие в первом скобке, которое должно возвращать false.

Назад во втором звонке IsEven(2 - 1) в настоящее время false, поэтому он принимает действие во втором кронштейне, который возвращается true.

В первом звонке IsEven(3 - 1) истинно, поэтому он принимает действие в первом скобке, которое должно возвращать false, указывая, что 3 действительно даже нет.

Это как целое начало.

Конечно, реальный пример, вероятно, будет использовать оператор modulo %.

public static bool IsEven(int number) 
{ 
    return number % 2 == 0; 
} 

Answer 2

Думай об этом, как это:

IsEven(3) 
| IsEven(2) 
| | IsEven(1) 
| | | IsEven(0) 
| | | Return True 
| | Return False 
| Return True 
Return False 

Это всегда будет в конечном итоге получить до 0, если вход был неотрицательным и начать двигаться вверх по цепочке. IsEven(1) выше означает, что IsEven(2) и IsEven(3) все еще выполняется. Эти вызовы методов еще не закончились.

Что делает метод IsEven(n), возвращает противоположность нижнего номера. Передача в 4 означает, что он должен проверить, равно ли 3. Так как это не так, оно вернется для 4.

Как уже упоминалось, я бы предложил написать его, но я также предложил бы точку останова и используя команду ID IDE, чтобы перейти в метод IsEven, чтобы вы могли наблюдать изменение значения параметра и следить за потоком, происходит. Или, по крайней мере, добавить несколько Console.WriteLine для просмотра.

Answer 3

Давайте попробуем разобраться в этом, начиная с математики. 0 даже по определению. Мы знаем, что каждое добавление 1 будет переворачивать «четность» номера. Таким образом, мы можем написать reursive правило следующим образом:

Base case: IsEven(0) = true 
Induction: IsEven(n) = NOT(IsEven(n-1)) ; for n > 0 

Таким образом, мы можем легко кодировать его:

static bool IsEven(int n) 
{ 
    if (n == 0) return true; 
    return (!IsEven(n - 1)); 
} 

До сих пор так хорошо. Но заметьте, (!A) можно переписать вместо как это неудобное условие:

if (A) 
{ 
    return false; 
} 
else 
{ 
    return true; 
} 

Вы можете убедить себя, подставляя A с true или false.

Теперь мы просто заменить A с IsEven(n-1) и вставить его в коде выше и получить оригинальный

static bool IsEven(int n) 
{ 
    if (n == 0) return true; 

    if (IsEven(n - 1)) 
    { 
     return false; 
    } 
    else 
    { 
     return true; 
    } 
}