/* Title: Rekurencyjny algorytm szybkiego potęgowania o złożoności O(log n) */ #include <stdio.h> int potegowanie(int podstawa, int wykladnik); int main() { int wynik = potegowanie( 2, 6 ); /* 2^6 */ printf( "Wynik potegowania 2^6: %i\n", wynik ); /* Wynik 64 */ return 0; } int potegowanie( int podstawa, int wykladnik ) { if( wykladnik == 0 ) /* Potęgowanie podstawy o wykładniku równym 0 */ { return 1; } else if( wykladnik % 2 == 1 ) /* Dla wykładnika nieparzystego */ { return podstawa * potegowanie( podstawa , wykladnik - 1 ); } else /* Dla wykładnika parzystego */ { return potegowanie( podstawa * podstawa, wykladnik / 2 ); } }