С++ (рекурсия) степень

[Sverest]

Как работает эта программа?

Используется синтаксис 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);

[hurtsy]

Sverest в сообщении #591621 писал(а):

Как работает эта программа?

Похоже на бесконечную рекурсию.
Раз рекурсия, можно "забить" на экономию памяти.
Вместо

cout << power3(2, 4)<<endl;

можно написать

 int   k= power3(2, 4);
        cout << k<<endl;
    

С уважением,

[Sverest]

hurtsy в сообщении #591742 писал(а):

Похоже на бесконечную рекурсию.

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

[Munin]

hurtsy в сообщении #591742 писал(а):

Похоже на бесконечную рекурсию.

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

[Maslov]

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; }

[Munin]

hurtsy в сообщении #591742 писал(а):

Раз рекурсия, можно "забить" на экономию памяти.

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

-- 03.07.2012 21:36:24 --

Maslov в сообщении #591751 писал(а):

Только лучше убрать лишние вызовы

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

[Joker_vD]

(Оффтоп)

Munin в сообщении #591752 писал(а):

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

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

[Munin]

(Оффтоп)

Joker_vD в сообщении #591894 писал(а):

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

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

Joker_vD в сообщении #591894 писал(а):

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

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

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

[Joker_vD]

(Оффтоп)

Munin в сообщении #591897 писал(а):

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

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

Munin в сообщении #591897 писал(а):

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

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

[Munin]

(Оффтоп)

Joker_vD в сообщении #591904 писал(а):

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

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

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

Joker_vD в сообщении #591904 писал(а):

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

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

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