Рекурсия

[prikolist]

Ребята! Вот дошёл до темы рекурсия, и вроде тему из школы роходили, но смотрю на программу, и что-то не могу понять вот эту строку:

Код: Выделить всё

answer = factr(n-1)*n;

из кода:

Код: Выделить всё

#include <iostream>
using namespace std;

int factr(int n);

int main()
{
	setlocale(0,"");
	
	//Использование рекурсивной версии
	cout<<"Факториал числа 4 равен "<<factr(4)<<'\n';

cin.get();
}

int factr(int n)
{
	int answer;
	if(n == 1) return(1);
	answer = factr(n-1)*n;
	return(answer);
}

Смотрите, за первым разом, если смотреть на строку answer = factr(n-1)*n; целой переменной answer присваивается (4-1)*4 = 12, за вторым: (3-1)*3 = 6 , третим разом: (2-1)*2 = 2

12*6*2 = ........как тогда получается результат 24 ?

[_SG]

Если напрячь мозг и память... То неверно. Рекурсию вроде бы от конца надо раскручивать. Останов будет при n=1 и дальше всё взад 1*2*3*4 в итоге.

[BBB]

Смотрите, за первым разом, если смотреть на строку answer = factr(n-1)*n; целой переменной answer присваивается (4-1)*4 = 12[/B]

"Если смотреть на строку", то целой переменной answer присваивается результат вызова ф-ии factr(4-1), умноженный на 4.

[prikolist]

Можно подробней. Как идёт за первым разом, за вторым.... Как происходит этот процес,хочется понять. Я понимаю что происходит такое,переменной answer
присваивается вот так:

Код: Выделить всё

(4-1)*4
(3-1)*3
(2-1)*2
(1-1)*1

А потом return(answer);
всё что в скобочках проигнорирует, а то что за скобочками умножит?
1*2*3*4

[BBB]

1) Из main происходит вызов factr (4)
2) Попадаем в функцию factr с параметром n, равным 4.
3) В ф-ии factr написано: если n != 1, то вернуть результат, равный (для случая n=4) четырем, умноженным на результат вызова factr (4-1)
4) Попадаем в функцию factr с параметром n, равным 3.
5) В ф-ии factr написано: если n != 1, то вернуть результат, равный (для случая n=3) трем, умноженным на результат вызова factr (3-1)
6) Попадаем в функцию factr с параметром n, равным 2.
7) В ф-ии factr написано: если n != 1, то вернуть результат, равный (для случая n=2) двум, умноженным на результат вызова factr (2-1)
8) Попадаем в функцию factr с параметром n, равным 1.
9) В ф-ии factr написано: если n = 1, то вернуть 1. Возвращаем (в factr) 1.
10) Возвращаем (в factr) 2 * <результат п.9, т.е. 1)>, т.е. 2
11) Возвращаем (в factr) 3 * <результат п.10, т.е. 2)>, т.е. 6
12) Возвращаем (уже в main) 4 * <результат п.11, т.е. 6)>, т.е. 24.

[prikolist]

Что интересно, значение в скобочке,как-бы игнорируется
Тоесть:

Начальное возвращение:

Код: Выделить всё

(5-1) * 5
(4-1) * 4
(3-1) * 3
(2-1) * 2

Конечное возвращение:

Код: Выделить всё

 1*2 = 2
 2*3 = 6
 6*4 = 24       а не 3*4 =12
24*5 = 120    а не 4*5 = 20,если смотреть в скобочки 

[Romeo]

Лучше всего понять следующим образом.

Известно, что:

Код: Выделить всё

fact(n) = fact(n-1) * n, для n>1.
fact(n) = 1, для n=1.
fact(n) = undefined, для n<=0

Из этого следует.

Код: Выделить всё

fact(4) = fact(4-1)*4 = (fact(3-1)*3)*4 = ((fact(2-1)*2)*3)*4 = /после расрытия скобок/ = 1*2*3*4 = 24