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

@xADMIRALx · Регистрация: 09.06.2012

Студворк — интернет-сервис помощи студентам

Здравствуйте программисты,помнится давно давно изучал с++,и тут по новой начал читать книгу и дело дошло до факториала,есть способ через циклы и через рекурсию.Так вот : метод возвращает всё как положено,но вот только я не могу понять как?Как она это делает?так как в конце у нас 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;
 
}

@g-h · 29.06.2012, 14:29

В функции factr(int n) не везде return 1; Только при аргументе n == 1 возвращается единица. В других случаях высчитывается переменная answer

C++
1
2
answer = factr(n-1) * n;
return answer;

Которая в свою очередь опять вызывает эту же функцию, но с аргументом на 1 меньше.

Возьми вот такой маленький пример, как факториал 2!. И посмотри как он рассчитывается.

@xADMIRALx · 29.06.2012, 14:59 **[ТС]**

Блин капец щас башка взарьвется,офигеть кажется такое простое,не тут та было...эх...
сейчас попробывал схиматично посмтоить только щас вроде маленько дошло

@g-h · 29.06.2012, 15:18

Сообщение от xADMIRALx

а то блин я чуть монитор уже не выкинул в окно...

Меня эти рекурсивные функции тоже бесят.

@Kastaneda · 29.06.2012, 19:26

Объяснить рекурсию (на примере ханойской башни)

@taras atavin · 30.06.2012, 05:39

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 · 30.06.2012, 12:59

Вот быстрейшая и лучшая функция факториала!

C++
1
2
3
int factorial(int n) {
      return !n ? 1 : n * factorial(n - 1);
  }

silent_1991 · 30.06.2012, 14:16

SeryZone, по каким критериям вы определили её скорость и качество?

@taras atavin · 30.06.2012, 14:59

Сообщение от silent_1991

по каким критериям вы определили её скорость и качество?

Ни по каким. Начнём с того, что всякая рекурсия фактически равняется двум циклам: циклу вызовов и циклу подстановок, а работает только один. Так что даже без накладных на вызов/возврат можно явным циклом ту же задачу решить вдвое быстрей. Так ведь ещё вызов/возврат - не самые простые и далеко не быстрые операции даже из числа составных. Да и по памяти рекурсия - эталон прожорливости, что есть вторая пакость.

silent_1991 · 30.06.2012, 15:01

taras atavin, я разве вам вопрос задал?

@taras atavin · 30.06.2012, 15:06

Рекурсия хороша только тогда, когда рекурсивна сама задача, например, при работе с деревьями, при разборе инфиксных выражений, при парсинге xml. Но не в факториале. Рекурсия на ровном месте = наглядное пособие, как делать не надо.

Добавлено через 1 минуту

Сообщение от silent_1991

я разве вам вопрос задал?

Ну считай, что телепат детектед, хотя на самом деле телепания здесь ни при чём, достаточно прочитать его пост.

silent_1991 · 30.06.2012, 15:18

taras atavin, факториал рекурсивен, все формальные определения факториала, что я видел, определяются сами через себя. В свою очередь, разбор инфиксных выражений (да и вообще любых языков, грамматики которых контекстно свободны), лучше реализовать через магазинные автоматы (LA/LALR разбор). Это я к тому, что не обязательно для рекурсивных задач рекурсия является наилучшим вариантом.

@taras atavin · 30.06.2012, 15:30

Факториал есть произведение всех целых чисел от единицы до своего аргумента, а рекурсивное определение на посвящённой факториалу лекции по высшей математике выводится из этого. И это не я придумал, спроси у Льва Наумовича Гутмана, который ту лекцию читал (то есть вёл занятие). Свести к рекурсивной можно даже задачу вычисления среднего арифметического, а определитель матрицы вычислить не рекурсивно. Но это не означает, что среднее арифметическое надо считать рекурсивно.

Добавлено через 3 минуты

Сообщение от silent_1991

не обязательно для рекурсивных задач рекурсия является наилучшим вариантом.

Я и не имел ввиду, что это всегда абсолютно лучшее решение, у меня вообще есть свой явно-циклический преобразователь инфиксных выражений в постфиксные и не факт, что он хуже шилдовского рекурсивного парсера. Но в таких случаях рекурсивные решения не однозначно плохие, в отличие от рекурсии из принципа на пустом месте, а попытка из принципа от рекурсии избавиться там, где с ней получается хорошо, может добавить таких сложностей, что в итоге получится хуже не куда, а то и вовсе не получится. Если же рекурсивна не только задача, но и организация данных, то вообще сомнительно хорошее не рекурсивное решение.

silent_1991 · 30.06.2012, 15:42

taras atavin, да, факториал можно вполне естественным образом определить итеративно через оператор произведения, согласен.

Сообщение от taras atavin

спроси у Льва Наумовича Гутмана

Воздержусь, пожалуй, вы не против?

Сообщение от taras atavin

а определитель матрицы вычислить не рекурсивно

Вот уж определитель вряд ли нормальный программист будет считать через миноры. Гаусс - наше всё.

Добавлено через 6 минут
taras atavin, в общем, не я сказал, что факториал через рекурсию уделывает все прочие решения, потому на этом предлагаю нашу дискуссию окончить. В свою очередь, жду ответ SeryZone на поставленный мною ранее вопрос.

@SeryZone · 01.07.2012, 08:34

Сообщение от silent_1991

SeryZone, по каким критериям вы определили её скорость и качество?

Я отправил задачу на тестирование. Сайт - e-olimp.com. Там эта функция показала лучшие результаты! Хотя заранее я отправлял другие коды вычисления факториала.

@Catstail · 01.07.2012, 09:12

Посмотри презентацию, которую я использовал на своих лекциях. Может, легче станет:

@taras atavin · 01.07.2012, 09:36

Сообщение от 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 · 01.07.2012, 09:49

Сообщение от taras atavin

так как аргумент всегда мал

Чем "ловить блох", попробуйте, например, вычислить 200! Могу заранее подсказать ответ:

7886578673647905035523632139321850622951 3597768717326329474253324435944996340334 2920304284011984623904177212138919638830 2576427902426371050619266249528299311134 6285727076331723739698894392244562145166 4240254033291864131227428294853277524242 4075739032403212574055795686602260319041 7032406235170085879617892222278962370389 7374720000000000000000000000000000000000 000000000000000

А чтобы замерить производительность короткого кода, погрузите его в цикл и выполните 10000 раз (или более). Так можно и два алгоритма сравнить (только цикл должен быть организован одинаково)...

@taras atavin · 01.07.2012, 09:58

Сообщение от Catstail

Чем "ловить блох", попробуйте, например, вычислить 200!

Про переполнение пропустил? А функции с поддержкой длинной арифметики медленны по определению, даже когда эти тормоза оправданы.

@Catstail · 01.07.2012, 10:13

Не пропустил, просто пошутил...

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

"Театр начинается с вешалки... но будущее все равно за кинематографом" В. Пелевин.

Новые блоги и статьи Все статьи Все блоги /
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .	PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .	Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .

@xADMIRALx 70 / 64 / 5 Регистрация: 09.06.2012 Сообщений: 291
	29.06.2012, 14:59 [ТС]
	Блин капец щас башка взарьвется,офигеть кажется такое простое,не тут та было...эх... сейчас попробывал схиматично посмтоить только щас вроде маленько дошло 0

@Kastaneda 5232 / 3205 / 362 Регистрация: 12.12.2009 Сообщений: 8,143 Записей в блоге: 2
	29.06.2012, 19:26
	Сообщение было отмечено как решение Решение Объяснить рекурсию (на примере ханойской башни) 3

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	30.06.2012, 14:16
	SeryZone, по каким критериям вы определили её скорость и качество? 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	30.06.2012, 15:01
	taras atavin, я разве вам вопрос задал? 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	30.06.2012, 15:18
	taras atavin, факториал рекурсивен, все формальные определения факториала, что я видел, определяются сами через себя. В свою очередь, разбор инфиксных выражений (да и вообще любых языков, грамматики которых контекстно свободны), лучше реализовать через магазинные автоматы (LA/LALR разбор). Это я к тому, что не обязательно для рекурсивных задач рекурсия является наилучшим вариантом. 0

@Catstail Супер-модератор 38163 / 21098 / 4306 Регистрация: 12.02.2012 Сообщений: 34,686 Записей в блоге: 14
	01.07.2012, 10:13
	Не пропустил, просто пошутил... Для чего могут понадобиться факториалы чисел в диапазоне до 15-20? Биномиальные коэфф-ты, спецфункции и т.д. Но в нормальных программах массив факториалов вычисляют один раз, а потом нужный факториал просто берут из соотв. ячейки (обращаясь по индексу), что всяко быстрее, чем вычислять его заново... "Театр начинается с вешалки... но будущее все равно за кинематографом" В. Пелевин. 0

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

Решение