Рекурсия

[Golovastik]

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

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 ?

[Sazary]

Рассмотрим вызов функции:

factr(4) - вернет 4, умноженное на то, что вернет factr(4-1)
 factr(4-1)  -  вернет 3, умноженное на то, что вернет factr(3-1)
   factr(3-1)  -  вернет 2, умноженное на то, что вернет factr(2-1)
    factr(2-1)  -  вернет 1 и закончит рекурсивный спуск. Начинаем возвращаться     обратно.

Теперь проследите обратный путь и увидите, что на нижнем уровне будет возвращено 1, на следующем - 1*2, на следующем - 1*2*3 и так пока не дойдет до верха.

[GonZaleZ]

Смотри: факториал - это произведение всех целых чисел до данного числа, включая число. Тогда не сложно догадаться, что если факториал 3 умножить на 4, то получим факториал 4, если его умножить на 5, получим факториал пяти и т.д. Отсюда видим, что факториал какого-либо числа можно вычислить, зная факториал предыдущего числа. Т.е. 4! = 1*2*3*4 = 3!*4, т.к. 1*2*3 - это не что иное, как 3! Так же нам заведомо известно, что 1! = 1. Думаю, не надо объяснять почему))
А теперь смотрим, что говорится в функции: если требуется вычислить 1!, то возвращаем 1, но если же не 1, то берём факториал предыдущего числа [factr(n-1)] и умножаем его на данное число. В свою очередь, для этого мы вызываем ту же функцию factr(), которая считает 3! точно так же. И так до тех пор, пока мы не дойдём но 1, факториал которой нам уже известен. Т.е. функция как бы вызывает сама себя, это и есть рекурсия.
Теперь по поводу этого:

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

Тут ты немного не прав answer = factr(n-1)*n = factr(3) * 4. И всё.
3! = 1*2*3 = 6; 4! = 3!*4 = 6*4 = 24.
Здесь рекурсия как бы раскладывает этот факториал.
Давай посмотрим всё в развёрнутом виде:
Итак, factr(4) = factr(3)*4 = factr(2)*3*4 = factr(1)*2*3*4 = 1*2*3*4 = 24
Откуда взялось factr(3)*4 я уже говорил. Просто умножаем факториал предыдущего числа на само число.
Откуда взялось factr(3)*4 = factr(2)*3*4:
давай на мгновение забудем про четвёрку и вспомним только про 3!. factr(3) = factr(2)*3. А вот теперь вспоминаем про нашу четвёрку и домножаем всё это дело на 4: factr(2)*3*4.
Точно так же считается и 2!, а 1! нам уже известен заранее.
Надеюсь, доходчиво объяснил?

[Golovastik]

Что-то я вас не до конца понимаю.
Вот так будет что ли происходить возвращение вы имеете ввиду:
(4-1)*4
(3-1)*3
(2-1)*2
(1-1)*1

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


Извиняюсь, поздно задал. Ответ вверху, сейчас почитаю.

[GonZaleZ]

я как раз писал про это

[Golovastik]

Я думал, что должно было происходить вот так,если допустим нужно найти факторила !5:

в функции factr(2) answer = factr(1)*2 то есть answer бедет равен 1*2=2
в функции factr(3) answer = factr(2)*3 то есть answer бедет равен 2*3=6
в функции factr(4) answer = factr(3)*4 то есть answer бедет равен 3*4=12
в функции factr(5) answer = factr(4)*5 то есть answer бедет равен 4*5=20

А оказывается нужно вот так:

в функции factr(2) answer = factr(1)*2 то есть answer бедет равен 1*2=2
в функции factr(3) answer = factr(2)*3 то есть answer бедет равен 2*3=6
в функции factr(4) answer = factr(3)*4 то есть answer бедет равен 6*4=24
в функции factr(5) answer = factr(4)*5 то есть answer бедет равен 24*5=120

Тоесть в рекурсии как-бы происходит возвращение вперёд, а затем раскрутка с конца до начала. Что интересно, значение в скобочке,как-бы игнорируется
Тоесть:

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

(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,если смотреть в скобочки (5-1) * 5

[netrino]

Оно не игнорируется, а отправляется в функцию factr в качестве параметра... опять же, учите мат. часть

[GonZaleZ]

ничего не игнорируется. в данном случае скобки как бы раскрываются (вспоминаем школу) до того момента, пока не получится 1.
давайте рассмотрим 5! здесь равно я использую именно как равно, а не как присваивание:

factr(5) = factr(4) * 5 = factr(3)*4*5 = factr(2)*3*4*5 = factr(1)*2*3*4*5
т.к. factr(1) нам уже известен, то в результате получаем factr(5) = 1*2*3*4*5
в вышеприведённом выражении каждый факториал раскладывается на произведение факториала предыдущего числа на данное число. делается это до тех пор, пока нем не нужно будет найти 1!, результат которого уже заранее прописан в ветвлении.