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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 30, средняя оценка - 4.77
Valera59
1 / 1 / 0
Регистрация: 12.08.2012
Сообщений: 20
#1

Рекурсия, факториал - C++

03.09.2012, 18:35. Просмотров 4720. Ответов 14
Метки нет (Все метки)

Недавно увидел как пример рекурсии:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
using namespace std;
 
int f(int n)
{
    if (n == 1)
        return 1;
    return f(n-1)*n;
}
 
int main()
{
    setlocale(0,"");
 
    cout<<f(5);
 
    cin.get();
}
программа должна выдавать факториал 5 и она действительно это делает но я не могу понять почему она это делает.Точнее не понимаю строку 8 чему равно f, и почему программа выполняет ее 5 раз?
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.09.2012, 18:35
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Рекурсия, факториал (C++):

Рекурсия: факториал числа - C++
#include &lt;iostream&gt; using namespace std; int factorial(int n); int main() { cout &lt;&lt; &quot;at main&quot; &lt;&lt; endl; cout &lt;&lt;...

Двойной факториал VS рекурсия - C++
Доброго времени суток. Программа которая считает двойной факториал есть: int df(int x) { if (x&lt;3) { return x; } ...

Описать рекурсивные функции вещественного типа, вычисляющие факториал и двойной факториал заданного числа - C++
Описать рекурсивные функции Fact(N) и Fact2(N) вещественного типа, вычисляющие значения факториала N! и двойного факториала N!!...

Факториал - C++
Здравствуйте Всем!!! Меня зовут Наталья. Помогите решить задание на С++: Дано натуральное число n; найти n!. Использовать программу,...

факториал - C++
Я только начал изучать С++ и вот столкнулся с проблемой: дано положительное число A&gt;=10.Найти такое число k, что (k-1)!&lt;=A&lt;=k! ...

Факториал - C++
Помогите написать программу: Составить функцию, которая вычисляет сумму К слагаемых. В вызывающей функции main() организовать контроль...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Invader_Zim
Twilight Parasite
153 / 149 / 2
Регистрация: 21.07.2011
Сообщений: 908
03.09.2012, 18:38 #2
все элементарно, когда n=1 то выход из функции, иначе фигарим ту функцию еще раз, только с другим аргументом
1
Valera59
1 / 1 / 0
Регистрация: 12.08.2012
Сообщений: 20
03.09.2012, 18:42  [ТС] #3
Цитата Сообщение от Invader_Zim Посмотреть сообщение
все элементарно, когда n=1 то выход из функции, иначе фигарим ту функцию еще раз, только с другим аргументом
Спасибо дошло!
0
Байт
Эксперт C
16061 / 10330 / 1540
Регистрация: 24.12.2010
Сообщений: 19,451
03.09.2012, 20:11 #4
Вот еще хороший пример использования рекурсии
C
1
2
3
4
5
6
7
8
9
Peano(unsigned int n)
{
   if (n==0) return 0;
   return Peano(n-1) + 1;
}
main()
{
  cout<< Peano(5);
}
Должен выдать 5.
Правда, не проверял.
0
Invader_Zim
Twilight Parasite
153 / 149 / 2
Регистрация: 21.07.2011
Сообщений: 908
03.09.2012, 20:15 #5
и самое банальное вешающее систему:

C++
1
int main(){double *p=new[1000];main();}
1
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6467 / 3115 / 306
Регистрация: 04.12.2011
Сообщений: 8,590
Записей в блоге: 4
03.09.2012, 21:22 #6
Цитата Сообщение от Valera59 Посмотреть сообщение
Недавно увидел как пример рекурсии:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
using namespace std;
 
int f(int n)
{
    if (n == 1)
        return 1;
    return f(n-1)*n;
}
 
int main()
{
    setlocale(0,"");
 
    cout<<f(5);
 
    cin.get();
}
программа должна выдавать факториал 5 и она действительно это делает но я не могу понять почему она это делает.Точнее не понимаю строку 8 чему равно f, и почему программа выполняет ее 5 раз?
Valera59, как я понимаю, функция это ссылка на возвращаемое значение, если требуется результат (rvalue). Поэтому каждый раз этот адрес заносится в стек, как и инструкция умножить на n и следует новый вызов. Пока не будет достигнут return. После этого вычисления проводятся в обратном порядке (как в польской нотации), то есть 1*2*3*4*5. Единица умножается на n 5 раз, но n каждый раз на 1 больше (как и сохранялось). То есть стек выгружается (исполняется) пока не будет достигнут адрес первого (внешнего) вызова.

Не по теме:

Может сумбурно как-то сказал.



Добавлено через 16 минут
Цитата Сообщение от IGPIGP Посмотреть сообщение
Valera59, как я понимаю, функция это ссылка на возвращаемое значение, если требуется результат (rvalue). Поэтому каждый раз этот адрес заносится в стек, как и инструкция умножить на n и следует новый вызов.
Правильно скорее:
Valera59, как я понимаю, функция это возвращаемое значение, если требуется результат (rvalue).
Поскольку вызывая себя функция не возвращает значение то в стек заносится инструкция умножить на n и следует новый вызов.
Насочинял...
1
Thinker
Эксперт C++
4226 / 2200 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
03.09.2012, 22:16 #7
Вот неплохой пример с рекурсией
Удаление нулевой(-ых) строчки и столбца из матрицы
начните с простого. вывод чисел от 1 до n рекурсивно. найти сумму от 1 до n рекурсивно и т.д.
0
Day
1158 / 963 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
05.09.2012, 01:02 #8
Цитата Сообщение от Invader_Zim Посмотреть сообщение
и самое банальное вешающее систему:

Код C++
Тут вы совершенно правы. Рекурсия - чрезвычайно изящная, но и столь же опасная штука. Я прекрасно понимаю стремление преподавателей обьяснить ее на несколько экзотичном факториале. Но сам, конечно, никогда в жизни вещи, которые можно вычислить иттерационно, не стану делать рекурсивно. Рекурсия использует стек, чье поведение слабо контролируется, и который жрет самое дорогое - память (причем, бесконтрольно). Ну что произойдет, если я иттерационной функции fact дам на вход слишком большое число? Ну, будет неверный результат (такой же будет и у рекурсивной, если она сумеет доработать). А рекурсивная fact просто вылетит с трудно понимаемыми сообщениями.
Кстати, Д.Кнут в своей попытке энциклопедии явно рекурсивные алгоритмы реализовывал БЕЗ рекурсии! Правда, ему пришлось вводить такие массивы, как Stek1, StekOut и т.п...

Добавлено через 12 минут
Не думаю, что Д.Кнут не знал о рекурсии. Конечно, прекрасно знал! Но он рассматривал свою энциклопедию, как Учебник, и не хотел учить ОПАСНОМУ.
А вот чего он, кажется, не знал, так это СТРУКТУР (ничего не говоря уже о классах), поэтому его великолепные алгоритмы выглядят весьма неуклюже.
2
Intel~lect
135 / 124 / 2
Регистрация: 03.07.2012
Сообщений: 355
05.09.2012, 16:22 #9
Valera59, Вот небольшую схему сделал что происходит при вызове функции f(5) А вместо всех переменных сразу подставил их числовые значения.
2
Миниатюры
Рекурсия, факториал  
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6467 / 3115 / 306
Регистрация: 04.12.2011
Сообщений: 8,590
Записей в блоге: 4
05.09.2012, 17:56 #10
Да, все это складывается и раскручивается в обратном порядке.
Я тут порезвился на тему заполнения и выгрузки стека вызовов, при рекурсии. Вы уж простите. Бываю несдержан. Конечно, теоретически (гипотетически), мудрый компилятор смог бы скомпилировать даже инлайн-функцию, в последовательный код при, наперед, известном количестве рекурсий (тривиально и не бывает), но на практике даже это, скорее всего не случается. Поэтому использование стека, путем сохранения промежуточных результатов, напоминает фрагменты активационных записей для нерекурсивных (обычных) функций. При итеративных (последовательных) вызовах обычных функций, заполнение и очистка стека происходит обычным образом и это безопаснее.
0
ForEveR
В астрале
Эксперт С++
7972 / 4734 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
05.09.2012, 18:07 #11
Invader_Zim, Даже не в том дело, что код вешает систему (хотя определенно повесит), проблема больше в том, что вызов main-а явно - UB, если говорить о С++.
0
OhMyGodSoLong
~ Эврика! ~
1243 / 992 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
05.09.2012, 19:43 #12
Цитата Сообщение от IGPIGP Посмотреть сообщение
Поэтому использование стека, путем сохранения промежуточных результатов, напоминает фрагменты активационных записей для нерекурсивных (обычных) функций.
Не напоминает, а это они есть: записи активаций, они же фреймы стека, хранящие локальные переменные функций, которые ещё не завершили работу (активны) и могут вернуть результат.
0
IGPIGP
Комп_Оратор)
Эксперт по математике/физике
6467 / 3115 / 306
Регистрация: 04.12.2011
Сообщений: 8,590
Записей в блоге: 4
05.09.2012, 21:27 #13
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
Не напоминает, а это они есть: записи активаций, они же фреймы стека, хранящие локальные переменные функций, которые ещё не завершили работу (активны) и могут вернуть результат.
Наверное. Но очистка от такой записи происходит лишь когда функция полностью заканчивает вызов. То есть когда функция с типом возврата выполняет команду return. А в записи ведь не только локальные переменные и аргументы. Хорошо когда как в функции n! одна локальная переменная n, а если там, хотя бы, более или менее, сложное арифметическое выражение из локальных переменных? Вообще, у меня сложилось впечатление, что рекурсия реализована для сохранения возможностей С, где ее мощь проявляется в работе с битами и количество вызовов ограничено разрядностью обрабатываемого числа, например. А n! - удобный пример для объяснения и понимания.
0
OhMyGodSoLong
~ Эврика! ~
1243 / 992 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
05.09.2012, 21:41 #14
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от IGPIGP Посмотреть сообщение
А n! - удобный пример для объяснения и понимания.
Лично я считаю это ужасным примером. Хуже может быть только
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool isOdd(unsigned);
 
bool isEven(unsigned x)
{
  if (x == 0) {
    return true;
  }
  else {
    return !isOdd(x - 1);
  }
}
 
bool isOdd(unsigned x)
{
  if (x == 1) {
    return true;
  }
  else {
    return !isEven(x - 1);
  }
}
Просто потому, что что-то можно выразить рекурсией, ещё не стоит так действительно делать. В императивных языках вроде Плюсов есть родные циклы, в которых факториал определяется не хуже как произведение чисел от единицы до n.

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

Лучше бы показывали рекурсию на естественно рекурсивных вещах: qsort, ханойских башнях, поиске в дереве/графе.
3
Day
1158 / 963 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
05.09.2012, 23:22 #15
~OhMyGodSoLong~, Именно это я и хотел сказать
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.09.2012, 23:22
Привет! Вот еще темы с ответами:

Факториал - C++
Пользователь вводит число и программа считает его факториал. Например 5! = 5*4*3*2*1 = 120. кто не помнит факториал считает так:...

Факториал - C++
Дано натуральное число n; найти n!. Использовать программу, включающую рекурсивную процедуру вычисления n!

факториал в с++ - C++
Дано целое число N (&gt;0). Используя один цикл, найти сумму 1!+2!+3!+....N! Выражение N! - N-факториал- обозначает произведение всех целых...

Факториал - C++
Нада зделать прогу штоби она виводила таким образом X 2 4 6 8 10 а Y 2! 4! 6! 8! 10! тоисть факториал от Х зделайте плз оч надо на С/С++


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

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

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