Страница 1 из 1
Рекурсия
Добавлено: 15 сен 2009, 00:45
prikolist
Ребята! Вот дошёл до темы рекурсия, и вроде тему из школы роходили, но смотрю на программу, и что-то не могу понять вот эту строку:
из кода:
Код: Выделить всё
#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 ?
Re: Рекурсия
Добавлено: 15 сен 2009, 07:51
_SG
Если напрячь мозг и память... То неверно. Рекурсию вроде бы от конца надо раскручивать. Останов будет при n=1 и дальше всё взад 1*2*3*4 в итоге.
Re: Рекурсия
Добавлено: 15 сен 2009, 09:24
BBB
prikolist писал(а):Смотрите, за первым разом, если смотреть на строку answer = factr(n-1)*n; целой переменной answer присваивается (4-1)*4 = 12[/B]
"Если смотреть на строку", то целой переменной
answer присваивается результат вызова ф-ии factr(4-1), умноженный на 4.
Re: Рекурсия
Добавлено: 15 сен 2009, 13:56
prikolist
Можно подробней. Как идёт за первым разом, за вторым.... Как происходит этот процес,хочется понять. Я понимаю что происходит такое,переменной
answer
присваивается вот так:
Код: Выделить всё
(4-1)*4
(3-1)*3
(2-1)*2
(1-1)*1
А потом return(answer);
всё что в скобочках проигнорирует, а то что за скобочками умножит?
1*2*3*4
Re: Рекурсия
Добавлено: 15 сен 2009, 15:53
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.
Re: Рекурсия
Добавлено: 15 сен 2009, 16:10
prikolist
Что интересно, значение в скобочке,как-бы игнорируется
Тоесть:
Начальное возвращение:
Конечное возвращение:
Код: Выделить всё
1*2 = 2
2*3 = 6
6*4 = 24 а не 3*4 =12
24*5 = 120 а не 4*5 = 20,если смотреть в скобочки
Re: Рекурсия
Добавлено: 15 сен 2009, 17:00
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