Рекурсия функции C/C++

Question

Я пытался понять приведенный ниже фрагмент кода, но не совсем понял логику вывода.

int Func(int x, int y){ 
    if (x < y) 
     return 0; 
    else 
     return Func(x - y, y) + 1; 
} 

int main() 
{ 
    int x = 50, y=10; 
    printf("%d \n",Func(x,y)); 
    return 0; 
} 

Выход для вышеупомянутой программы, очевидно, 5. Может кто-нибудь тела мне, что "+1" (в return Func(x - y, y) + 1;) в методе типа рекурсии на самом деле означает и как это есть поток выполнения.?

Если я только что выполнил return Func(x-y,y);, тогда выход 0, это нормально. Но почему в первом случае выход равен 5?

Answer 1

рекурсии будет действовать следующим образом:.

Func(x = 50, y = 10) x >= y 
    Func(x = 40, y = 10) x >= y 
    Func(x = 30, y = 10) x >= y 
     Func(x = 20, y = 10) x >= y 
     Func(x = 10, y = 10) x >= y 
      Func(x = 0, y = 10) x < y 
      return 0 
     return Func(x = 0, y = 10) + 1 = 1 
     return Func(x = 10, y = 10) + 1 = 2 
    return Func(x = 20, y = 10) + 1 = 3 
    return Func(x = 30, y = 10) + 1 = 4 
return Func(x = 40, y = 10) + 1 = 5 

Где +1 используется, чтобы сказать: «добавить 1 к результату, вычисленному Func(x - y, y) в рекурсивном вызове».

Answer 2

Отдел - отличная субстанция, в конце ее. Это концепция, демонстрирующая этот метод. Во всяком случае, идея состоит в том, что функция вычитает второй параметр из первого и каждый раз добавляет к общей сумме 1. Таким образом, вы проверяете, сколько раз первый параметр вписывается в другой, или, другими словами, , вычесть. (:

Просто объяснить конкретную +1 части:

В конце концов, функция возвращает ноль - когда первый параметр ниже нуля Таким образом, вы знаете, когда остановиться

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

Answer 3

В базовом футляре Func() возвращает 0.

Если он повторяется один раз, он возвращает 0 + 1 = 1 (базовый случай плюс 1).

Если он повторяется дважды, он возвращает (0 + 1) + 1 = 2 (базовый корпус, плюс 1 случай, плюс 1).

И так далее. Таким образом, возвращаемое значение показывает, сколько раз функция вызывает себя, что (как говорит другой ответ) вычисляет деление, игнорируя остаток.

Answer 4

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

Вы называете Func (50, 10).

. Эти звонки Func (40, 10).

..Этот звонок Func (30, 10).

... Это называет Func (20, 10).

.... Это называет Func (10, 10).

..... Это называет Func (0, 10). Начиная с 0 < 10, он возвращает 0.

..... Func (0,10) возвращен 0. Добавьте 1 к нему и верните это.

.... Func (10,10) возвращается 1. Добавить 1 к нему и вернуть это.

... Func (20,10) вернулся 2. Добавить 1 к нему и вернуть это.

..Func (30,10) вернулся 3. Добавить 1 к нему и вернуть это.

.Func (40,10) возвращен 4. Добавьте 1 к нему и верните это. Поэтому

Func (50,10) вернулся 5.

Таким образом, по существу, результат 5 означает число рекурсивных вызовов он сделал, что на 5.

Answer 5

Просто проанализировать, как код идет. Сначала вы переходите к основному случаю (просто вызываете функцию). Теперь вы вызывали функцию пять раз, каждый раз разные аргументы. Когда x < y, вы возвращаетесь назад и получаете результат 0. Помните, что вы спустились 5 раз и ничего не делали, кроме изменения параметров. Теперь каждый раз, когда вы возвращаетесь назад, вы добавляете +1 к этому результату, поэтому в первый раз, когда вы возвращаетесь, вы добавляете +1 и получаете 0 + 1 = 1, а во второй раз, когда вы возвращаетесь, вы добавляете +1 к этому результату, и вы получаете 1 + 1 = 2, в следующий раз 2 + 1 = 3 и т. Д.