Проблемы с пониманием того, как recursion работает на C

Я изучаю функции в C из книги C Programming: A Modern Approach . Он содержит следующую функцию:

int fact(int n) { if (n <= 1) return 1; else return n * fact(n - 1); } 

со следующим объяснением:

Чтобы увидеть, как работают рекурсии, давайте проследим за выполнением оператора i = fact(3); вот что происходит: ”

 fact(3) finds that 3 is not equal or less than 1, so it calls fact(2)which finds that 2 is not equal or less than 1, so it calls fact(1) which finds that 1 is equal or less than 1, so it returns 1,causing fact(2) to return 2 x 1 = 2, causing fact(3) to return 3 x 2 = 6 

Я действительно смущен, почему он делает все эти действия, если он не находится внутри цикла? почему он продолжает делать 3 все меньше и меньше, пока не будет соответствовать аргументу в функции if?

Символ * означает, что n в факте (n) теперь составляет 3 – 1, и в основном он говорит, что он делает это снова и снова?

Рекурсия – это процесс, когда функция вызывает себя. В определении функции вы можете увидеть вызов fact(n-1) , это означает, что сама функция снова вызвана.

 int fact(int n) //return value is an integer, name of function is "fact", input argument is an integer named n { if (n <= 1) // if the input arg equals 1, return 1 return 1; else return n * fact(n - 1); //else, return n (input arg of this fact) times the return value of fact(n - 1) } 

Предполагается, что факт (3) должен возвращать 3 * 2 * 1 = 6. Что происходит при выполнении процесса int a = fact(3) :

 fact(3) //dive into this function: { if (n <= 1) //n is not 1 return 1; else return n * fact(n - 1); //now we call fact(2) } 

мы называем факт (2):

 { if (n <= 1) //n is not 1 return 1; else return n * fact(n - 1); //now we call fact(1) } 

мы называем факт (1):

 { if (n <= 1) //n equals 1 return 1; //return 1 else return n * fact(n - 1); } 

Теперь функция fact(1) возвращает 1 к точке, где ее вызвано, что находится внутри fact(2) . Если быть точным, утверждение return 2*fact(1); , это возвращается к утверждению return 3*fact(2); который возвращается к нашему начальному вызову функции, а наше целое число «a» получает значение 6.

Надеюсь, это сделало это более ясным для вас, если у вас остались вопросы, вы можете попросить.

Просто перейдем к вашему примеру, чтобы найти факториал из 3

Первый вызов – fact(3)

n = 3 так что выполняется условие else

 3 * fact(2) 

n = 2 так что выполняется условие else

 2 * fact(1) 

n = 1 теперь, если условие проходит так, что оно возвращает 1

Так что вместе

 3 * fact(2) 3 * 2 * fact(1) 3 * 2 * 1 = 6 

В рекурсии должно быть условие выхода.

 if(n = 1) /* 0! = 1 So you have reached the last iteration and you are good to return */ 

Если вы вызываете функцию изнутри, она называется рекурсией. Так как вы возвращаете значение, возвращаемое из внутреннего вызова, функция получает оценку до тех пор, пока она больше не будет вызывать себя, т. Е. Когда n <= 1 , < просто для учета 0! == 1 0! == 1 .

Это делает 3 или n меньше и меньше из-за

 fact(n - 1) // n - 1 < n 

Рекурсия возникает, когда вызывается fact(n-1) . Там сама функция снова вызвана, поэтому код повторяется без необходимости цикла. Значение аргумента изменяется, потому что функция вызывается с другим аргументом каждый раз.

Btw, символ * означает умножение.