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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 31, средняя оценка - 4.94
xADMIRALx
67 / 61 / 1
Регистрация: 09.06.2012
Сообщений: 291
#1

Рекурсия не могу понять - C++

29.06.2012, 14:10. Просмотров 3973. Ответов 26
Метки нет (Все метки)

Здравствуйте программисты,помнится давно давно изучал с++,и тут по новой начал читать книгу и дело дошло до факториала,есть способ через циклы и через рекурсию.Так вот : метод возвращает всё как положено,но вот только я не могу понять как?Как она это делает?так как в конце у нас return 1 почему когда я вывожу в cout у меня 2 6 24 120.Разъесните пожалуйста что как и где происходит,а то блин я чуть монитор уже не выкинул в окно...
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
#include <iostream>
#include <locale>
#include <stdlib>
 
 
using namespace std;
 
int factr(int n);
int main()
{
    setlocale(LC_ALL,".1251");
 
    cout << "Факториал числа 5 : " << factr(5)<< endl;
 
 
 
 
 
 
 
    system("PAUSE");
    return 0;
}
int factr(int n)//5
{
    int answer = 0;
 
    if (n == 1) return 1;
    cout << (answer = factr(n - 1) * n) << endl;
    return answer;
 
}
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.06.2012, 14:10
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Рекурсия не могу понять (C++):

Стек на основе массива структур - эт как понять читаю литературу и не могу понять! - C++
Стек статически (на основе массива структур). Пример структура &quot;Товар&quot; которая включает в себя: № по каталогу(ключ), Название, цена, срок...

Не могу сделать полиморфизм. Не могу до конца понять пример по этому поводу - C++
Есть такая задача: Класс Animal должен быть абстрактным, имеет имя и вес. Класс Reptile имеет habitate, который держит в себе среду...

не могу понять - C++
как сделать так чтобы B двигался по массиву? #include&lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; int main() { int...

не могу понять - C++
есть такой код void addElement(const T&amp; elem){ *(_pointer) = elem; // int t1 = _pointer &lt; &amp;_deque_data; // int t2 =...

Не могу понять ошибку - C++
#include&lt;iostream.h&gt; #include&lt;math.h&gt; #include&lt;conio.h&gt; #include&lt;stdio.h&gt; int main() { double x=3.741, y=-0.825,z=0.160, A,...

Не могу понять, почему? - C++
Доброго времени суток=) Такая печаль. Создается класс Окружность с полями радиус, площадь и длина окружности. Нужно создать функции...

26
g-h
67 / 67 / 1
Регистрация: 03.06.2012
Сообщений: 176
29.06.2012, 14:29 #2
В функции factr(int n) не везде return 1; Только при аргументе n == 1 возвращается единица. В других случаях высчитывается переменная answer
C++
1
2
answer = factr(n-1) * n;
return answer;
Которая в свою очередь опять вызывает эту же функцию, но с аргументом на 1 меньше.

Возьми вот такой маленький пример, как факториал 2!. И посмотри как он рассчитывается.
1
xADMIRALx
67 / 61 / 1
Регистрация: 09.06.2012
Сообщений: 291
29.06.2012, 14:59  [ТС] #3
Блин капец щас башка взарьвется,офигеть кажется такое простое,не тут та было...эх...
сейчас попробывал схиматично посмтоить только щас вроде маленько дошло
0
g-h
67 / 67 / 1
Регистрация: 03.06.2012
Сообщений: 176
29.06.2012, 15:18 #4
Цитата Сообщение от xADMIRALx Посмотреть сообщение
а то блин я чуть монитор уже не выкинул в окно...

Меня эти рекурсивные функции тоже бесят.
0
Kastaneda
Форумчанин
Эксперт С++
4655 / 2863 / 228
Регистрация: 12.12.2009
Сообщений: 7,274
Записей в блоге: 2
Завершенные тесты: 1
29.06.2012, 19:26 #5
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Объяснить рекурсию (на примере ханойской башни)
3
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
30.06.2012, 05:39 #6
xADMIRALx, при n!=1 вычиляется факториал, равный 1*2*3*4*....*(n-3)*(n-2)*(n-1)*n=(1*2*3*4*....*(n-3)*(n-2)*(n-1))*n, причём, вместо 1*2*3*4*....*(n-3)*(n-2)*(n-1) подставляеся факториал n-1 (а он раввен этому произведению, согласно определению факториала), а для его получения ещё раз вызвается сама функуция factr, в чём и состоит суть рекурсии. При рекурсии обязательно, чтоб в конце был вызван экземпляр функции, который пойдёт по не рекурсивной ветви, в случае факториала это
C++
1
return 1;
Добавлено через 1 минуту
Цитата Сообщение от xADMIRALx Посмотреть сообщение
: метод
Это не метод, а обычная глобальная функция. Метод есть функция-член класса, а у тебя она вне класса.
0
SeryZone
56 / 28 / 5
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
30.06.2012, 12:59 #7
Вот быстрейшая и лучшая функция факториала!
C++
1
2
3
int factorial(int n) {
      return !n ? 1 : n * factorial(n - 1);
  }
0
silent_1991
Эксперт С++
4984 / 3041 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
30.06.2012, 14:16 #8
SeryZone, по каким критериям вы определили её скорость и качество?
0
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
30.06.2012, 14:59 #9
Цитата Сообщение от silent_1991 Посмотреть сообщение
по каким критериям вы определили её скорость и качество?
Ни по каким. Начнём с того, что всякая рекурсия фактически равняется двум циклам: циклу вызовов и циклу подстановок, а работает только один. Так что даже без накладных на вызов/возврат можно явным циклом ту же задачу решить вдвое быстрей. Так ведь ещё вызов/возврат - не самые простые и далеко не быстрые операции даже из числа составных. Да и по памяти рекурсия - эталон прожорливости, что есть вторая пакость.
0
silent_1991
Эксперт С++
4984 / 3041 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
30.06.2012, 15:01 #10
taras atavin, я разве вам вопрос задал?
0
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
30.06.2012, 15:06 #11
Рекурсия хороша только тогда, когда рекурсивна сама задача, например, при работе с деревьями, при разборе инфиксных выражений, при парсинге xml. Но не в факториале. Рекурсия на ровном месте = наглядное пособие, как делать не надо.

Добавлено через 1 минуту
Цитата Сообщение от silent_1991 Посмотреть сообщение
я разве вам вопрос задал?
Ну считай, что телепат детектед, хотя на самом деле телепания здесь ни при чём, достаточно прочитать его пост.
0
silent_1991
Эксперт С++
4984 / 3041 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
30.06.2012, 15:18 #12
taras atavin, факториал рекурсивен, все формальные определения факториала, что я видел, определяются сами через себя. В свою очередь, разбор инфиксных выражений (да и вообще любых языков, грамматики которых контекстно свободны), лучше реализовать через магазинные автоматы (LA/LALR разбор). Это я к тому, что не обязательно для рекурсивных задач рекурсия является наилучшим вариантом.
0
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
30.06.2012, 15:30 #13
Факториал есть произведение всех целых чисел от единицы до своего аргумента, а рекурсивное определение на посвящённой факториалу лекции по высшей математике выводится из этого. И это не я придумал, спроси у Льва Наумовича Гутмана, который ту лекцию читал (то есть вёл занятие). Свести к рекурсивной можно даже задачу вычисления среднего арифметического, а определитель матрицы вычислить не рекурсивно. Но это не означает, что среднее арифметическое надо считать рекурсивно.

Добавлено через 3 минуты
Цитата Сообщение от silent_1991 Посмотреть сообщение
не обязательно для рекурсивных задач рекурсия является наилучшим вариантом.
Я и не имел ввиду, что это всегда абсолютно лучшее решение, у меня вообще есть свой явно-циклический преобразователь инфиксных выражений в постфиксные и не факт, что он хуже шилдовского рекурсивного парсера. Но в таких случаях рекурсивные решения не однозначно плохие, в отличие от рекурсии из принципа на пустом месте, а попытка из принципа от рекурсии избавиться там, где с ней получается хорошо, может добавить таких сложностей, что в итоге получится хуже не куда, а то и вовсе не получится. Если же рекурсивна не только задача, но и организация данных, то вообще сомнительно хорошее не рекурсивное решение.
0
silent_1991
Эксперт С++
4984 / 3041 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
30.06.2012, 15:42 #14
taras atavin, да, факториал можно вполне естественным образом определить итеративно через оператор произведения, согласен.
Цитата Сообщение от taras atavin Посмотреть сообщение
спроси у Льва Наумовича Гутмана
Воздержусь, пожалуй, вы не против?
Цитата Сообщение от taras atavin Посмотреть сообщение
а определитель матрицы вычислить не рекурсивно
Вот уж определитель вряд ли нормальный программист будет считать через миноры. Гаусс - наше всё.

Добавлено через 6 минут
taras atavin, в общем, не я сказал, что факториал через рекурсию уделывает все прочие решения, потому на этом предлагаю нашу дискуссию окончить. В свою очередь, жду ответ SeryZone на поставленный мною ранее вопрос.
0
SeryZone
56 / 28 / 5
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
01.07.2012, 08:34 #15
Цитата Сообщение от silent_1991 Посмотреть сообщение
SeryZone, по каким критериям вы определили её скорость и качество?
Я отправил задачу на тестирование. Сайт - e-olimp.com. Там эта функция показала лучшие результаты! Хотя заранее я отправлял другие коды вычисления факториала.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.07.2012, 08:34
Привет! Вот еще темы с ответами:

Цикл do while не могу понять, - C++
программу которая принимает число N и выводит на экран N звездочек, использовать цикл do while

Указатели не могу понять - C++
Все вопросы указал в комментариях к коду. Не могу понять почему так #include &lt;iostream&gt; using namespace std; int main() { int...

не могу понять ошибку - C++
Народ, здарова, сижу над классами, конкретно наследование классов! Компилятор выдает ошибку: Unit1.cpp(143): E2285 Could not find a...

не могу понять ошыбки - C++
привет всем. помогите вычислить ошыбку, вроде маленькая но я все же хочу узнать какая проблема в этой проге. #include &quot;StdAfx.h&quot;...


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

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

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