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

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

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

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

29.06.2012, 14:10. Просмотров 3896. Ответов 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;
 
}
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.06.2012, 14:10     Рекурсия не могу понять
Посмотрите здесь:

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

не могу понять программу - C++
есть программа, но она работает не коректно(по крайней мере в visual studio 2013 ultimate), я отключил проверку ошибок - вроде запускается ...

строки в С++.. не могу их понять.. - C++
задание такое преобразовать строку, содержащую выражение на Си с операциями (= , == , != , а+= , а-=), в строку содержащую эти же...

Не могу понять почему... - C++
#include &quot;stdafx.h&quot; void main() { funct(); _getch(); } void funct() {

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

Меня эти рекурсивные функции тоже бесят.
Kastaneda
Форумчанин
Эксперт С++
4479 / 2841 / 227
Регистрация: 12.12.2009
Сообщений: 7,224
Записей в блоге: 1
Завершенные тесты: 1
29.06.2012, 19:26     Рекурсия не могу понять #5
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Объяснить рекурсию (на примере ханойской башни)
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 Посмотреть сообщение
: метод
Это не метод, а обычная глобальная функция. Метод есть функция-член класса, а у тебя она вне класса.
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);
  }
silent_1991
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
30.06.2012, 14:16     Рекурсия не могу понять #8
SeryZone, по каким критериям вы определили её скорость и качество?
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
30.06.2012, 14:59     Рекурсия не могу понять #9
Цитата Сообщение от silent_1991 Посмотреть сообщение
по каким критериям вы определили её скорость и качество?
Ни по каким. Начнём с того, что всякая рекурсия фактически равняется двум циклам: циклу вызовов и циклу подстановок, а работает только один. Так что даже без накладных на вызов/возврат можно явным циклом ту же задачу решить вдвое быстрей. Так ведь ещё вызов/возврат - не самые простые и далеко не быстрые операции даже из числа составных. Да и по памяти рекурсия - эталон прожорливости, что есть вторая пакость.
silent_1991
Эксперт С++
4958 / 3034 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
30.06.2012, 15:01     Рекурсия не могу понять #10
taras atavin, я разве вам вопрос задал?
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
30.06.2012, 15:06     Рекурсия не могу понять #11
Рекурсия хороша только тогда, когда рекурсивна сама задача, например, при работе с деревьями, при разборе инфиксных выражений, при парсинге xml. Но не в факториале. Рекурсия на ровном месте = наглядное пособие, как делать не надо.

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

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

Добавлено через 6 минут
taras atavin, в общем, не я сказал, что факториал через рекурсию уделывает все прочие решения, потому на этом предлагаю нашу дискуссию окончить. В свою очередь, жду ответ SeryZone на поставленный мною ранее вопрос.
SeryZone
56 / 28 / 5
Регистрация: 09.03.2012
Сообщений: 726
Записей в блоге: 1
01.07.2012, 08:34     Рекурсия не могу понять #15
Цитата Сообщение от silent_1991 Посмотреть сообщение
SeryZone, по каким критериям вы определили её скорость и качество?
Я отправил задачу на тестирование. Сайт - e-olimp.com. Там эта функция показала лучшие результаты! Хотя заранее я отправлял другие коды вычисления факториала.
Catstail
Модератор
22445 / 10850 / 1766
Регистрация: 12.02.2012
Сообщений: 17,967
01.07.2012, 09:12     Рекурсия не могу понять #16
Посмотри презентацию, которую я использовал на своих лекциях. Может, легче станет:
Вложения
Тип файла: zip lec-05.zip (239.3 Кб, 17 просмотров)
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
01.07.2012, 09:36     Рекурсия не могу понять #17
Цитата Сообщение от SeryZone Посмотреть сообщение
Я отправил задачу на тестирование. Сайт - e-olimp.com. Там эта функция показала лучшие результаты! Хотя заранее я отправлял другие коды вычисления факториала.
И что? А сам то пробовал тестировать? На том кривосайте видимо вообще не было годных факториалов. А лучший вот:
C++
1
2
3
4
5
6
7
8
9
unsigned __int64 factorial(uint8_t n)
{
 unsigned __int64 Result=1;
 for (; n>0; --n)
 {
  Result*=n;
 }
 return Result;
}
. Кстати, декремент лучше вычитания. А лучший декремент - префиксный. Вот это действительно быстрейший факториал. А твой - эталон тормознутости. И при тестах факториала разрешение часов, или таймера не достаточно, надо сравнивать только по счётчику тактов, так как аргумент всегда мал и даже рекурсивная функция гарантировано уложится во временное разрешение остальных измерялок. А если увеличивать аргумент, то наткнёшься на переполнение типа и ни каких гвоздёв.
Catstail
Модератор
22445 / 10850 / 1766
Регистрация: 12.02.2012
Сообщений: 17,967
01.07.2012, 09:49     Рекурсия не могу понять #18
Цитата Сообщение от taras atavin Посмотреть сообщение
так как аргумент всегда мал
Чем "ловить блох", попробуйте, например, вычислить 200! Могу заранее подсказать ответ:

788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284011984623904177212138919638830257642790242637105061926624952829931113462857270763317237396988943922445621451664240254033291864131227428294853277524242407573903240321257405579568660226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000000000000000000

А чтобы замерить производительность короткого кода, погрузите его в цикл и выполните 10000 раз (или более). Так можно и два алгоритма сравнить (только цикл должен быть организован одинаково)...
taras atavin
Ушёл с форума.
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
01.07.2012, 09:58     Рекурсия не могу понять #19
Цитата Сообщение от Catstail Посмотреть сообщение
Чем "ловить блох", попробуйте, например, вычислить 200!
Про переполнение пропустил? А функции с поддержкой длинной арифметики медленны по определению, даже когда эти тормоза оправданы.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.07.2012, 10:13     Рекурсия не могу понять
Еще ссылки по теме:

Не могу понять запись на с++ - C++
Не могу понять запись на с++ там какието проценты обьясните.

Не могу понять условие - C++
Не могу понять что вводится в последней строке входных данных, если как описано в условии там время прихода рабочих, то почему там 6...

Не могу понять ошибку - C++
Пытаюсь решить вот эту задачу http://www.cyberforum.ru/cpp-beginners/thread356063.html Есть решения на бэйсике вот...

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

Не могу понять условие - C++
Скажите пожалуйста как понять это условие: if(pRC), где pRC - указатель


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

Или воспользуйтесь поиском по форуму:
Catstail
Модератор
22445 / 10850 / 1766
Регистрация: 12.02.2012
Сообщений: 17,967
01.07.2012, 10:13     Рекурсия не могу понять #20
Не пропустил, просто пошутил...

Для чего могут понадобиться факториалы чисел в диапазоне до 15-20? Биномиальные коэфф-ты, спецфункции и т.д. Но в нормальных программах массив факториалов вычисляют один раз, а потом нужный факториал просто берут из соотв. ячейки (обращаясь по индексу), что всяко быстрее, чем вычислять его заново...

"Театр начинается с вешалки... но будущее все равно за кинематографом" В. Пелевин.
Yandex
Объявления
01.07.2012, 10:13     Рекурсия не могу понять
Ответ Создать тему
Опции темы

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