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

Рекурсия - C++

Восстановить пароль Регистрация
 
Ryuzaki2014
0 / 0 / 0
Регистрация: 26.01.2014
Сообщений: 8
02.02.2014, 20:07     Рекурсия #1
Вот какой самый простой пример рекурсии я обнаружил в интернете:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
int factorial(int n) {
    if (n == 1)
        return 1;
    else return factorial(n - 1)*n;
 
}
 
int main() {
    int n;
    cout << "Enter number";
    cin >> n;
    cout << factorial(n) << '\n';
    system("pause");
}



Как вы понимаете не черта я не понял...Во первых объясните куда сохраняется нужное нам значение (переменную), и для наглядности напишите псевдокодом как мы получаем факториал 5. Спасибо заранее, понимаю, что тема возможно затертая до дыр, но я бы не писал сюда, если бы не потратил уйму времени.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.02.2014, 20:07     Рекурсия
Посмотрите здесь:

РЕкурсия C++
Рекурсия (на С) C++
Рекурсия C++
рекурсия C++
Рекурсия C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
02.02.2014, 20:19     Рекурсия #2
Это вывод на печать cout << factorial(n) << '\n';. Смотри разбираем на примере 3 (иначе длинно):

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int factorial(3) {
    if (3 == 1)
        return 1;//не попадает сюда
    else return factorial(3 - 1)*3;// или return factorial(2)*3 т.е. обращается сама к себе и возвращает 2*3 (6) см. ниже
 
}
int factorial(2) {
    if (2 == 1)
        return 1;//не попадает сюда опять
    else return factorial(2 - 1)*2;// или return factorial(1)*2 т.е. обращается сама к себе опять и дает ответ 1*2 (см. ниже) возвращает (2)
 
}
 
int factorial(1) {
    if (1 == 1)
        return 1;//попадает сюда возвращает 1
    else return factorial(1 - 1)*1;// сюда не попадает
 
}
Цитата Сообщение от Ryuzaki2014 Посмотреть сообщение
для наглядности напишите псевдокодом
факториал 5!=1*2*3*4*5;
Или
C++
1
2
int ot=1;
for (int i=1 ;i<=n; i++) ot*=i;
Добавлено через 26 секунд
Или что надо то?
vovacreme
-16 / 61 / 13
Регистрация: 14.01.2014
Сообщений: 145
02.02.2014, 20:19     Рекурсия #3
Цитата Сообщение от Ryuzaki2014 Посмотреть сообщение
Вот какой самый простой пример рекурсии я обнаружил в интернете:
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
int factorial(int n) {
    if (n == 1)
        return 1;
    else return factorial(n - 1)*n;
 
}
 
int main() {
    int n;
    cout << "Enter number";
    cin >> n;
    cout << factorial(n) << '\n';
    system("pause");
}



Как вы понимаете не черта я не понял...Во первых объясните куда сохраняется нужное нам значение (переменную), и для наглядности напишите псевдокодом как мы получаем факториал 5. Спасибо заранее, понимаю, что тема возможно затертая до дыр, но я бы не писал сюда, если бы не потратил уйму времени.
Используй в Visual Studio команду "Шаг с заходом" (F11 на клавиатуре), и смотри как меняются значения переменных
metaluga145
243 / 244 / 20
Регистрация: 08.04.2013
Сообщений: 927
02.02.2014, 20:23     Рекурсия #4
Ryuzaki2014,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
int factorial(int n) {
    if (n == 1)
        return 1;
    else 
    {
       int tmp = factorial (n -1);
       tmp = tmp*n;
       return tmp;
     }
 
}
 
int main() {
    int n;
    cout << "Enter number";
    cin >> n;
    cout << factorial(n) << '\n';
    system("pause");
}
Я немного переписал функцию для удобства. Надеюсь понятно что я сделал. В данном случае, в функцию передается n, если n не 1, тогда функция вызывает саму себя и передает уже значение n-1, и так пока n не станет 1. Давайте теперь посмотрим что происходит, когда n=1(назовем это первым шагом), функция возвращает 1, на шаг выше в tmp записывается 1, так как в функцию передается n-1, то можно понять, что n=2 на втором шаге. 1*2 = 2 - функция вернула 2 на втором шаге, то есть, на третьем шаге в tmp попало значение 2, а n=3 на этом шаге, потом функция вернет 3*2 = 6, и это значение будет записано в tmp на четвертом шаге. и так дальше.
Точно так же работает Ваша функция, только там опущен момент с tmp.
Если есть вопросы, спрашивайте) рекурсия - это сложная штука)
Ryuzaki2014
0 / 0 / 0
Регистрация: 26.01.2014
Сообщений: 8
02.02.2014, 20:36  [ТС]     Рекурсия #5
metaluga145, Опять не понял ничего... В циклах понятно за счет чего происходит выход из цикла, а тут я не пойму, может я не вижу скрытый счетчик ?! Это первый момент, второй я не понимаю каким образом работает рекурсия в этом судя по всему и проблема, потому что я подставляю числа вместо переменной и у меня даже близко не выходит то что должно быть.
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
02.02.2014, 20:46     Рекурсия #6
Рекурсия вызывает сама себя с изменением параметра. Тут использовалась свойство факториала
n!=(n-1)!*n если n>1 и n!=1 если n=1. Посмотри мой пост я там на примере 3! все вызовы из твоего примера рассписал

Добавлено через 15 секунд
Рекурсия вызывает сама себя с изменением параметра. Тут использовалась свойство факториала
n!=(n-1)!*n если n>1 и n!=1 если n=1. Посмотри мой пост я там на примере 3! все вызовы из твоего примера рассписал
Ryuzaki2014
0 / 0 / 0
Регистрация: 26.01.2014
Сообщений: 8
02.02.2014, 20:46  [ТС]     Рекурсия #7
mustimur,либо я понимаю под псевдокодом что то иное либо вы меня не поняли. Ну к примеру мое понимание псевдокода такое для нахождение суммы двух чисел:
C++
1
2
3
Объявление двух переменных a и b;
Запрос на ввод a и b;
Вывод a+b;
Что то в таком роде я просил с рекурсией т.е если мне не понятна программа я обычно пишу это как текст и пытаюсь разобрать все процессы, которые в обычном коде иногда трудновато проглядеть либо рисую блок схемы.
edwvee
19 / 19 / 2
Регистрация: 27.01.2014
Сообщений: 232
02.02.2014, 20:55     Рекурсия #8
Рекурсия это как бы как скобки в матвыражении: например
4*(5-6*(8+4*(2+3)))
И таким образом оно высчитывается
4*(5-6*(8+4*5))
4*(5-6*(8+20))
4*(5-6*28)
4*(5-138)
4*133
532

Тут все выражение по сути и есть вызывающая функция, но ее нельзя выполнить не получив значения тех, что вложены, то есть скобки.
Дебагером отследить - хорошая идея. На самом деле научиться им пользоваться гораздо проще, чем кажется.
Рекурсивный поиск факториала все-таки не самый хороший пример по моему мнению, так как не имеет смысла искать факториал рекурсией.
metaluga145
243 / 244 / 20
Регистрация: 08.04.2013
Сообщений: 927
02.02.2014, 20:58     Рекурсия #9
Ryuzaki2014,
C++
1
2
3
int fact = 1;
for (int i = 5; i > 0; i--)
     fact *= i;
Здесь i уменьшается от 5 до 1, фор выступает счетчиком. в Вашем примере рекурсии счетчиком выступает то, что Вы передаете каждый раз число на 1 меньше и, когда параметр равен 1, уже ничего не куда не передается, то есть, это минимальное значение. Прямо как в форе
mustimur
268 / 222 / 57
Регистрация: 22.11.2013
Сообщений: 832
Записей в блоге: 1
02.02.2014, 21:11     Рекурсия #10
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от Ryuzaki2014 Посмотреть сообщение
Ну к примеру мое понимание псевдокода такое для нахождение суммы двух чисел:
Твой код разбираю тело:
C++
1
2
3
объявление переменной n
Запрос на ввод переменной n
Вывод Factorial(n)
тело функции Factorial(n)
C++
1
2
3
4
сравнение n и 1: ****
если n=1 то функция возвращает 1,
если нет то возвращает n*Factorial(n-1), т.е. обращается опять сама к себе в строчку которую я отметил **** но при этом n уменьшилось 1
все это происходит до тех пор пока n>1
Добавлено через 18 секунд
Цитата Сообщение от Ryuzaki2014 Посмотреть сообщение
Ну к примеру мое понимание псевдокода такое для нахождение суммы двух чисел:
Твой код разбираю тело:
C++
1
2
3
объявление переменной n
Запрос на ввод переменной n
Вывод Factorial(n)
тело функции Factorial(n)
C++
1
2
3
4
сравнение n и 1: ****
если n=1 то функция возвращает 1,
если нет то возвращает n*Factorial(n-1), т.е. обращается опять сама к себе в строчку которую я отметил **** но при этом n уменьшилось 1
все это происходит до тех пор пока n>1
Добавлено через 7 минут
Простите интернет глючит, два раза нажал отправить и создал дубль((

Добавлено через 15 секунд
Простите интернет глючит, два раза нажал отправить и создал дубль((
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.02.2014, 21:13     Рекурсия
Еще ссылки по теме:

C++ Рекурсия
C++ Рекурсия
Рекурсия C++

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

Или воспользуйтесь поиском по форуму:
Ryuzaki2014
0 / 0 / 0
Регистрация: 26.01.2014
Сообщений: 8
02.02.2014, 21:13  [ТС]     Рекурсия #11
http://cppstudio.com/wp-content/imag.../image26.5.png
Всем спасибо наконец то понял, благодаря этой иллюстрации и вашей помощи. Большое спасибо
Yandex
Объявления
02.02.2014, 21:13     Рекурсия
Ответ Создать тему
Опции темы

Текущее время: 13:59. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru