Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Golovastik
11 / 11 / 0
Регистрация: 25.05.2009
Сообщений: 435
#1

Как работает рекурсия? - C++

14.09.2009, 23:28. Просмотров 931. Ответов 13
Метки нет (Все метки)

Ребята! Вот дошёл до темы рекурсия, и вроде тему из школы роходили, но смотрю на программу, и что-то не могу понять вот эту строку:
C++
1
answer = factr(n-1)*n;
из кода:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#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 ?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
14.09.2009, 23:28     Как работает рекурсия?
Посмотрите здесь:

Обьясните как работает рекурсия - C++
#include &lt;iostream&gt; using namespace std; int Multiply(int, int); int main() { int number; int exponent; cout&lt;&lt;&quot;Enter...

Не понимаю как работает рекурсия - C++
Привет. Знаю, что таких тем много (Я читал их). Не нужно кидать ссылки. Я знаю что такое рекурсия, но не понимаю как она работает. int...

Как работает рекурсия в цикле - C++
Всем привет! Подскажите пожалуйста как работает рекурсия в цикле, типа вот такого bool test(long long value,int n) { bool res =...

Объясните как работает рекурсия - C++
#include &lt;iostream&gt; #include &lt;iomanip&gt; using namespace std; void print(int a, int b); int main() { print(0,...

Обьясните как работает рекурсия в данной задаче - C++
есть вот такая програмка: #include &lt;stdio.h&gt; #include &lt;conio.h&gt; int a,cnt=0,N,K; void fun(long S, int tek) { ...

Не работает рекурсия - C++
Помогите пожалуйста, не считает рекурсией формулу: x-x^2/2+x^3/3-...-&gt;ln(1+x) Сумму ряда я решил, а рекурсию не считает(( double...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Gravity
562 / 556 / 39
Регистрация: 29.01.2009
Сообщений: 1,274
14.09.2009, 23:55     Как работает рекурсия? #2
Цитата Сообщение от Golovastik Посмотреть сообщение
Смотрите, за первым разом, если смотреть на строку answer = factr(n-1)*n; целой переменной answer присваивается (4-1)*4 = 12, за вторым: (3-1)*3 = 6 , третим разом: (2-1)*2 = 2
Не, присвоение происходит с нижнего уровня рекурсии, т.е. если представить схематично, то так:
Код
factr(4-1)*4  == 24
       ^      
       | == 6  
       |      
factr(3-1)*3  
       ^      
       | == 2  
       |      
factr(2-1)*2  
       ^      
       |
       1
Golovastik
11 / 11 / 0
Регистрация: 25.05.2009
Сообщений: 435
15.09.2009, 00:47  [ТС]     Как работает рекурсия? #3
Что-то я вас не до конца понимаю.
Вот так будет что ли происходить возвращение вы имеете ввиду:
(4-1)*4
(3-1)*3
(2-1)*2
(1-1)*1

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

Добавлено через 27 минут
C++
1
Не, присвоение происходит с нижнего уровня рекурсии
Каким образом?
accept
4820 / 3240 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
15.09.2009, 10:32     Как работает рекурсия? #4
Цитата Сообщение от Golovastik
целой переменной answer присваивается (4-1)*4 = 12
потерял факториал

там
answer = factr(4-1)*4

то есть это answer = factr(3)*4;
функция запускается снова, создаётся новый answer, ему присваивается новое значение
Monte-Cristo
2787 / 1373 / 30
Регистрация: 07.03.2009
Сообщений: 4,446
15.09.2009, 10:43     Как работает рекурсия? #5
Golovastik, смотри:

у тебя есть
answer = factr(3)*4
а что такое factr(3)? это factr(2)*3. а factr(2) = factr(1)*2. factr(1) = 1;

то есть, если и сделать подстановку:

answer = factr(3)*4
answer = factr(2)*3*4
answer = factr(1)*2*3*4
answer = 1*2*3*4
Golovastik
11 / 11 / 0
Регистрация: 25.05.2009
Сообщений: 435
15.09.2009, 14:00  [ТС]     Как работает рекурсия? #6
Вроде понятно, но не до конца.
C++
1
присвоение переменной answer происходит с нижнего уровня рекурсии
Как это понимать?
zim22
depict1
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
15.09.2009, 14:02     Как работает рекурсия? #7
Цитата Сообщение от Golovastik Посмотреть сообщение
Как это понимать?
это когда return вызовется
Golovastik
11 / 11 / 0
Регистрация: 25.05.2009
Сообщений: 435
15.09.2009, 14:17  [ТС]     Как работает рекурсия? #8
Можно,на примере, последовательно, как всё идёт это процесс.
zim22
depict1
276 / 141 / 2
Регистрация: 11.07.2009
Сообщений: 606
15.09.2009, 14:48     Как работает рекурсия? #9
Цитата Сообщение от Golovastik Посмотреть сообщение
Можно,на примере, последовательно, как всё идёт это процесс.
запусти программу в дебаггере - всё увидишь сам.
mamedovvms
2916 / 837 / 93
Регистрация: 30.04.2009
Сообщений: 2,624
15.09.2009, 14:59     Как работает рекурсия? #10
например тебе надо вычислить факториал 5 то будет действовать прога так
вызовит функцию factr(5), но так как у нас n=5 то эта функция вызовит функцию factr(4)*5 опять n не равно 1 и так далее когда n будет равно 1 то factr(1) возвратит нам 1 а
в функции 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
то что тебе и выведет функция factr(5)

Добавлено через 1 минуту
ну по моему все должно быть предельно ясно, как еще объяснить не знаю
Golovastik
11 / 11 / 0
Регистрация: 25.05.2009
Сообщений: 435
15.09.2009, 15:53  [ТС]     Как работает рекурсия? #11
Спасибо всем за ответы.
Тоесть в рекурсии как-бы происходит возвращение вперёд, а затем раскрутка с конца до начала.
Смотрю из вашего примера:
Код
в функции 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
А я думал, что должно было происходить вот так:
Код
в функции 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
Теперь уяснил.

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

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

Код
(5-1) * 5
(4-1) * 4
(3-1) * 3
(2-1) * 2
Конечное возвращение:
Код
 1*2 = 2
 2*3 = 6
 6*4 = 24     [B]  а не 3*4 =12[/B]
24*5 = 120   [B] а не 4*5 = 20,если смотреть в скобочки[/B]
M128K145
Эксперт С++
8283 / 3502 / 143
Регистрация: 03.07.2009
Сообщений: 10,706
15.09.2009, 15:55     Как работает рекурсия? #12
Golovastik, вот, посмотри
так
C++
1
2
3
4
5
6
7
8
9
10
11
12
int factr(int n)
{
    int answer;
    if(n == 1)
    {
        std::cout<<1<<'\n';
        return(1);
    }
    answer = factr(n-1)*n;
    std::cout<<answer<<'\n';
    return(answer);
}
. В дебаггере будет не очень интересно, хотя и надо учится ним пользоваться
Evg
Эксперт CАвтор FAQ
17470 / 5708 / 363
Регистрация: 30.03.2009
Сообщений: 15,677
Записей в блоге: 26
15.09.2009, 17:28     Как работает рекурсия? #13
Цитата Сообщение от Golovastik Посмотреть сообщение
Что интересно, значение в скобочке,как-бы игнорируется
Не игнорируется, а передаётся в процедуру. Грубо говоря, при вычислении factr(5) твоя программа работает аналогично нижеприведённому коду

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int factrA(int n)
{
        return(1);
}
 
int factrB(int n)
{
        int answer;
        answer = factrA(n-1)*n; // по сути factrA(1)*2
        return(answer);
}
 
int factrC(int n)
{
        int answer;
        answer = factrB(n-1)*n; // по сути factrB(2)*3
        return(answer);
}
 
int factrD(int n)
{
        int answer;
        answer = factrC(n-1)*n; // по сути factrC(3)*4
        return(answer);
}
 
int factr(int n)
{
        int answer;
        answer = factrD(n-1)*n; // по сути factrD(4)*5
        return(answer);
}
 
int main()
{
  factr(5);
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.09.2009, 07:50     Как работает рекурсия?
Еще ссылки по теме:

C++. Рекурсия не работает - C++
Есть функция #include &lt;iostream&gt; #include &lt;cmath&gt; #include &lt;iomanip&gt; using namespace std; double y(int); int main () { ...

Рекурсия - работает, нет результата - C++
Всем привет. У меня есть программа которая предназначена для Задан массив целых. Построить из них любую последовательность таким образом,...

Не работает программа(рекурсия)(код в нутри) - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; using namespace std; char shest; int i; void vvod() {

Вложенные циклы и рекурсия. Не работает табулирование. - C++
Необходимо вычислить значение функции, решая задачу табулирования. ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
accept
4820 / 3240 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
16.09.2009, 07:50     Как работает рекурсия? #14
Цитата Сообщение от Golovastik
Тоесть в рекурсии как-бы происходит возвращение вперёд, а затем раскрутка с конца до начала.
сначала раскрутка, потом вычисления
answer'ы независимые, так как это одноимённые различные переменные разных блоков
Yandex
Объявления
16.09.2009, 07:50     Как работает рекурсия?
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru