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

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

Войти
Регистрация
Восстановить пароль
 
Ryuzaki2014
0 / 0 / 0
Регистрация: 26.01.2014
Сообщений: 8
#1

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

02.02.2014, 20:07. Просмотров 499. Ответов 10
Метки нет (Все метки)

Вот какой самый простой пример рекурсии я обнаружил в интернете:
Кликните здесь для просмотра всего текста
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. Спасибо заранее, понимаю, что тема возможно затертая до дыр, но я бы не писал сюда, если бы не потратил уйму времени.
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.02.2014, 20:07
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Рекурсия (C++):

Рекурсия - C++
Здравствуйте, писали на лабораторной программу с использованием рекурсии, о бъясните почему в ответе двойки выдает?? и что рекурсивная...

Рекурсия - C++
Помогите пожалуйста составить программу, с помощью рекурсии: Определить значение отношения максимального и минимального из...

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

Рекурсия - C++
Всем доброго времени суток! Прошу Вашей помощи! Задание такого: Вычислить, используя рекурсию, выражение: //и вот собственно...

Рекурсия - C++
Привет, помогите пожалуйста надо вычислить рекурсивную функцию : (x+a(x+(a-1)(x+(a-2)(x+...2(x+1)^2)^2)^2)^2)^2. Помогите пожалуйста ,...

Рекурсия - C++
Задан массив целых чисел: а0, а1 ..., аn-1. Известно, что один из элементов массива принимает нулевое значение. Найти номер данного...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
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 секунд
Или что надо то?
1
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 на клавиатуре), и смотри как меняются значения переменных
1
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.
Если есть вопросы, спрашивайте) рекурсия - это сложная штука)
1
Ryuzaki2014
0 / 0 / 0
Регистрация: 26.01.2014
Сообщений: 8
02.02.2014, 20:36  [ТС] #5
metaluga145, Опять не понял ничего... В циклах понятно за счет чего происходит выход из цикла, а тут я не пойму, может я не вижу скрытый счетчик ?! Это первый момент, второй я не понимаю каким образом работает рекурсия в этом судя по всему и проблема, потому что я подставляю числа вместо переменной и у меня даже близко не выходит то что должно быть.
0
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! все вызовы из твоего примера рассписал
1
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;
Что то в таком роде я просил с рекурсией т.е если мне не понятна программа я обычно пишу это как текст и пытаюсь разобрать все процессы, которые в обычном коде иногда трудновато проглядеть либо рисую блок схемы.
0
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

Тут все выражение по сути и есть вызывающая функция, но ее нельзя выполнить не получив значения тех, что вложены, то есть скобки.
Дебагером отследить - хорошая идея. На самом деле научиться им пользоваться гораздо проще, чем кажется.
Рекурсивный поиск факториала все-таки не самый хороший пример по моему мнению, так как не имеет смысла искать факториал рекурсией.
1
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, уже ничего не куда не передается, то есть, это минимальное значение. Прямо как в форе
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 секунд
Простите интернет глючит, два раза нажал отправить и создал дубль((
1
Ryuzaki2014
0 / 0 / 0
Регистрация: 26.01.2014
Сообщений: 8
02.02.2014, 21:13  [ТС] #11
http://cppstudio.com/wp-content/imag.../image26.5.png
Всем спасибо наконец то понял, благодаря этой иллюстрации и вашей помощи. Большое спасибо
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.02.2014, 21:13
Привет! Вот еще темы с ответами:

рекурсия - C++
Сделать рекурсию, кроме факториала!

Рекурсия - C++
Вопрос не по коду. Вот есть у меня рекурсивная функция, глубина рекурсии достигает 10 в среднем. Эта функция вызывается огромное (порядка...

Рекурсия - C++
Есть задача, написал решение но ответ неправильный. Задача: Решение: #include &lt;iostream&gt; using namespace std; int a, n, m, t,...

рекурсия - C++
Доброго времени суток. Уважаемые ГУРУ, есть одна проблема. Ниже представлен код, в котором параметр b должен быть всегда...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
02.02.2014, 21:13
Ответ Создать тему
Опции темы

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