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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 30, средняя оценка - 4.77
Valera59
 Аватар для Valera59
1 / 1 / 0
Регистрация: 12.08.2012
Сообщений: 20
03.09.2012, 18:35     Рекурсия, факториал #1
Недавно увидел как пример рекурсии:
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 раз?
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.09.2012, 18:35     Рекурсия, факториал
Посмотрите здесь:

C++ Факториал в С
C++ Факториал
Факториал C++
C++ факториал
Факториал C++
C++ С++ Факториал
Двойной факториал VS рекурсия C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Invader_Zim
Twilight Parasite
 Аватар для Invader_Zim
153 / 149 / 2
Регистрация: 21.07.2011
Сообщений: 907
03.09.2012, 18:38     Рекурсия, факториал #2
все элементарно, когда n=1 то выход из функции, иначе фигарим ту функцию еще раз, только с другим аргументом
Valera59
 Аватар для Valera59
1 / 1 / 0
Регистрация: 12.08.2012
Сообщений: 20
03.09.2012, 18:42  [ТС]     Рекурсия, факториал #3
Цитата Сообщение от Invader_Zim Посмотреть сообщение
все элементарно, когда n=1 то выход из функции, иначе фигарим ту функцию еще раз, только с другим аргументом
Спасибо дошло!
Байт
 Аватар для Байт
14340 / 9171 / 1322
Регистрация: 24.12.2010
Сообщений: 16,782
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.
Правда, не проверял.
Invader_Zim
Twilight Parasite
 Аватар для Invader_Zim
153 / 149 / 2
Регистрация: 21.07.2011
Сообщений: 907
03.09.2012, 20:15     Рекурсия, факториал #5
и самое банальное вешающее систему:

C++
1
int main(){double *p=new[1000];main();}
IGPIGP
Комп_Оратор)
 Аватар для IGPIGP
6230 / 2959 / 287
Регистрация: 04.12.2011
Сообщений: 7,898
Записей в блоге: 3
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 и следует новый вызов.
Насочинял...
Thinker
Эксперт C++
 Аватар для Thinker
4216 / 2190 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
03.09.2012, 22:16     Рекурсия, факториал #7
Вот неплохой пример с рекурсией
Удаление нулевой(-ых) строчки и столбца из матрицы
начните с простого. вывод чисел от 1 до n рекурсивно. найти сумму от 1 до n рекурсивно и т.д.
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
05.09.2012, 01:02     Рекурсия, факториал #8
Цитата Сообщение от Invader_Zim Посмотреть сообщение
и самое банальное вешающее систему:

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

Добавлено через 12 минут
Не думаю, что Д.Кнут не знал о рекурсии. Конечно, прекрасно знал! Но он рассматривал свою энциклопедию, как Учебник, и не хотел учить ОПАСНОМУ.
А вот чего он, кажется, не знал, так это СТРУКТУР (ничего не говоря уже о классах), поэтому его великолепные алгоритмы выглядят весьма неуклюже.
Intel~lect
 Аватар для Intel~lect
135 / 124 / 2
Регистрация: 03.07.2012
Сообщений: 355
05.09.2012, 16:22     Рекурсия, факториал #9
Valera59, Вот небольшую схему сделал что происходит при вызове функции f(5) А вместо всех переменных сразу подставил их числовые значения.
Миниатюры
Рекурсия, факториал  
IGPIGP
Комп_Оратор)
 Аватар для IGPIGP
6230 / 2959 / 287
Регистрация: 04.12.2011
Сообщений: 7,898
Записей в блоге: 3
05.09.2012, 17:56     Рекурсия, факториал #10
Да, все это складывается и раскручивается в обратном порядке.
Я тут порезвился на тему заполнения и выгрузки стека вызовов, при рекурсии. Вы уж простите. Бываю несдержан. Конечно, теоретически (гипотетически), мудрый компилятор смог бы скомпилировать даже инлайн-функцию, в последовательный код при, наперед, известном количестве рекурсий (тривиально и не бывает), но на практике даже это, скорее всего не случается. Поэтому использование стека, путем сохранения промежуточных результатов, напоминает фрагменты активационных записей для нерекурсивных (обычных) функций. При итеративных (последовательных) вызовах обычных функций, заполнение и очистка стека происходит обычным образом и это безопаснее.
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7955 / 4717 / 318
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
05.09.2012, 18:07     Рекурсия, факториал #11
Invader_Zim, Даже не в том дело, что код вешает систему (хотя определенно повесит), проблема больше в том, что вызов main-а явно - UB, если говорить о С++.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1238 / 987 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
05.09.2012, 19:43     Рекурсия, факториал #12
Цитата Сообщение от IGPIGP Посмотреть сообщение
Поэтому использование стека, путем сохранения промежуточных результатов, напоминает фрагменты активационных записей для нерекурсивных (обычных) функций.
Не напоминает, а это они есть: записи активаций, они же фреймы стека, хранящие локальные переменные функций, которые ещё не завершили работу (активны) и могут вернуть результат.
IGPIGP
Комп_Оратор)
 Аватар для IGPIGP
6230 / 2959 / 287
Регистрация: 04.12.2011
Сообщений: 7,898
Записей в блоге: 3
05.09.2012, 21:27     Рекурсия, факториал #13
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
Не напоминает, а это они есть: записи активаций, они же фреймы стека, хранящие локальные переменные функций, которые ещё не завершили работу (активны) и могут вернуть результат.
Наверное. Но очистка от такой записи происходит лишь когда функция полностью заканчивает вызов. То есть когда функция с типом возврата выполняет команду return. А в записи ведь не только локальные переменные и аргументы. Хорошо когда как в функции n! одна локальная переменная n, а если там, хотя бы, более или менее, сложное арифметическое выражение из локальных переменных? Вообще, у меня сложилось впечатление, что рекурсия реализована для сохранения возможностей С, где ее мощь проявляется в работе с битами и количество вызовов ограничено разрядностью обрабатываемого числа, например. А n! - удобный пример для объяснения и понимания.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1238 / 987 / 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, ханойских башнях, поиске в дереве/графе.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.09.2012, 23:22     Рекурсия, факториал
Еще ссылки по теме:

C++ Факториал Си
Факториал C++
Факториал C++
C++ Рекурсия: факториал числа
C++ Факториал

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

Или воспользуйтесь поиском по форуму:
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
05.09.2012, 23:22     Рекурсия, факториал #15
~OhMyGodSoLong~, Именно это я и хотел сказать
Yandex
Объявления
05.09.2012, 23:22     Рекурсия, факториал
Ответ Создать тему
Опции темы

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