2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 С++ (рекурсия) степень
Сообщение03.07.2012, 15:07 
Аватара пользователя
Как работает эта программа?

код: [ скачать ] [ спрятать ]
Используется синтаксис C++
//вычисление степени числа
#include <iostream>
using namespace std;
int power3(int x, int n);

int main()
{
        cout << power3(2, 4)<<endl;
        system ("pause");
        return 0;
       
}

int power3(int x, int n)
{
        if(n==0) return 1;
        else if (n % 2 == 0)
                x=power3(x, n/2)*power3(x, n/2);

        else if (n % 2 !=0) x=power3(x, n/2)*power3(x, n/2)*x;

        return x;

}
 


вот здесь непонятно, как это работает:
Код:
x=power3(x, n/2)*power3(x, n/2);

 
 
 
 Re: С++ (рекурсия) степень
Сообщение03.07.2012, 20:15 
Sverest в сообщении #591621 писал(а):
Как работает эта программа?

Похоже на бесконечную рекурсию.
Раз рекурсия, можно "забить" на экономию памяти.
Вместо
Код:
cout << power3(2, 4)<<endl;

можно написать
Код:
int   k= power3(2, 4);
        cout << k<<endl;
   

С уважением,

 
 
 
 Re: С++ (рекурсия) степень
Сообщение03.07.2012, 20:19 
Аватара пользователя
hurtsy в сообщении #591742 писал(а):
Похоже на бесконечную рекурсию.


Программа работает, но не могу понять как.

 
 
 
 Re: С++ (рекурсия) степень
Сообщение03.07.2012, 20:31 
Аватара пользователя
hurtsy в сообщении #591742 писал(а):
Похоже на бесконечную рекурсию.

Смотрите внимательнее.

 
 
 
 Re: С++ (рекурсия) степень
Сообщение03.07.2012, 20:35 
hurtsy в сообщении #591742 писал(а):
Похоже на бесконечную рекурсию.
Да нет тут никакой бесконечной рекурсии: второй аргумент функции уменьшается минимум наполовину при каждом рекурсивном вызове.

Sverest в сообщении #591745 писал(а):
Программа работает, но не могу понять как.
Это быстрое возведение в степень. Например, $x^{11}$ вычисляется как $x (x (x^2)^2)^2$

Только лучше убрать лишние вызовы: заменить
Код:
x=power3(x, n/2)*power3(x, n/2);
на что-то типа
Код:
{ int p = power3(x, n/2); x = p*p; }

 
 
 
 Re: С++ (рекурсия) степень
Сообщение03.07.2012, 20:35 
Аватара пользователя
hurtsy в сообщении #591742 писал(а):
Раз рекурсия, можно "забить" на экономию памяти.

Глубина рекурсии здесь будет не больше 32 или 64, беспокоиться не о чем. Другое дело, что об экономии времени автор программы не позаботился, разбазарив весь выигрыш, полученный на остроумном построении рекурсии. И я не знаю, сумеют ли это дело сгрызть современные оптимайзеры, тут большая интеллектуальность нужна.

-- 03.07.2012 21:36:24 --

Maslov в сообщении #591751 писал(а):
Только лучше убрать лишние вызовы

А, ну вот, Maslov и подсказал...

 
 
 
 Re: С++ (рекурсия) степень
Сообщение04.07.2012, 01:21 

(Оффтоп)

Munin в сообщении #591752 писал(а):
И я не знаю, сумеют ли это дело сгрызть современные оптимайзеры, тут большая интеллектуальность нужна.

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

 
 
 
 Re: С++ (рекурсия) степень
Сообщение04.07.2012, 01:25 
Аватара пользователя

(Оффтоп)

Joker_vD в сообщении #591894 писал(а):
Любые оптимайзеры свято блюдут принцип "сколько программист вызовов функций указал, столько их и должно быть".

Пока не инлайнят.

Joker_vD в сообщении #591894 писал(а):
Откуда ему знать, что у функции отсутствуют побочные эффекты и сама она не обращается к глобальным переменным?

С данной функцией всё проще: весь её текст туточки, доступен для анализа.

Уж раскрывать рекурсию оптимайзеры в некоторых случаях научены. Как минимум, концевую, где реально можно, и часто нужно, сэкономить.

 
 
 
 Re: С++ (рекурсия) степень
Сообщение04.07.2012, 01:42 

(Оффтоп)

Munin в сообщении #591897 писал(а):
Пока не инлайнят.

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

Munin в сообщении #591897 писал(а):
С данной функцией всё проще: весь её текст туточки, доступен для анализа.

Т.е. вызовы функций из другой сборки/модуля не оптимизируем?

 
 
 
 Re: С++ (рекурсия) степень
Сообщение04.07.2012, 02:30 
Аватара пользователя

(Оффтоп)

Joker_vD в сообщении #591904 писал(а):
Хорошо, уточняю принцип: "сколько программист вызовов функций указал, столько раз тела этих функций и будут выполняться".

Не факт. Пусть инлайнится функция без побочных эффектов, и её возвращаемое значение умножается на нуль. Оптимайзер может совсем её выбросить.

Оптимайзеры свято блюдут другой принцип: что результат выполнения должен совпадать, а как это достигнуто - если бы надо было во всём программиста слушаться, то и оптимайзеры были бы не нужны.

Joker_vD в сообщении #591904 писал(а):
Т.е. вызовы функций из другой сборки/модуля не оптимизируем?

Обычно нет, или не настолько глубоко. Поэтому код, который можно интеллектуально соптимизировать, сгребают в одну единицу трансляции.

Впрочем, мои сведения могли устареть, и компиляторы, знающие, какие единицы трансляции входят в проект, могут уже научиться оптимизировать проект как целое.

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group