Obliczanie wartości potęgi o podstawie i wykładniku naturalnym

Specyfikacja problemu:

Dane:

• p – podstawa potęgi; liczba naturalna, p > 0

• w – wykładnik potęgi; liczba naturalna

Wynik:

• wynik – wynik potęgowania; liczba naturalna

Sposób iteracyjny

Napiszemy funkcję obliczającą wartość potęgi o wykładniku naturalnym. Zaczniemy od nadania jej nazwy. Będziemy również potrzebować dwóch parametrówparametr funkcjiparametrów – jeden z nich będzie odpowiadać za wartość podstawy, a drugi za wartość wykładnika. Nazwiemy je odpowiednio p i w. Obu parametrom nadamy typ int.

int iteracja(int p, int w)
{
}

Teraz w ciele funkcji zadeklarujemy zmienną wynik o typie całkowitym. Przypiszemy jej wartość: 1. Następnie utworzymy pętlę while, która będzie wykonywana, dopóki w jest większe od zera.

int wynik = 1;
while (w > 0)
{
}

W środku pętli będziemy mnożyć zmienną wynik przez p, a następnie dekrementowaćdekrementacjadekrementować zmienną w.

wynik *= p;
w--;

Skoro w zmiennej wynik mamy już wyliczoną odpowiednią wartość, możemy ją zwrócić.

return wynik;

W ten sposób udało się nam napisać funkcję potęgującą sposobem iteracyjnym.

Gotowa funkcja wygląda następująco:

int iteracja(int p, int w)
{
    int wynik = 1;
    while (w > 0)
    {
    	wynik *= p;
		w--;
    }
    return wynik;
}

Sposób rekurencyjny

Napiszmy funkcję obliczającą wartość potęgi metodą rekurencyjną. Funkcja będzie miała dwa parametry typu int, przechowujące informacje: podstawę i wykładnik potęgi. Nazwiemy je odpowiednio p i w.

int rekurencja(int p, int w)
{
}

We wnętrzu funkcji rozważymy dwa przypadki. Pierwszy to warunek przerywania rekurencji (warunek podstawowy), który zwróci wartość i zakończy wykonywanie funkcji. Do jego zdefiniowania użyjemy instrukcji warunkowej if, gdzie w teście logicznym sprawdzimy, czy zmienna w jest równa 0. W sytuacji, gdy taka zależność będzie zachodzić, funkcja zwróci 1. W pozostałych przypadkach funkcja zwróci iloczyn zmiennej p i siebie samej z argumentami p i w - 1.

if (w == 0) return 1;
else return p * rekurencja(p, w - 1);

Tym sposobem napisaliśmy funkcję potęgującą z wykorzystaniem rekurencji.

int rekurencja(int p, int w)
{
    if (w == 0) return 1;
    else return p * rekurencja(p, w - 1);
}

Jak możemy łatwo zauważyć, wymagała ona napisania znacznie krótszego kodu w porównaniu do wariantu iteracyjnego.

Dla pełnego zrozumienia sposobu działania funkcji rekurencyjnej przeanalizujemy działanie tej funkcji dla podstawy równej 2 i wykładnika o wartości 3.

1. Zaczynamy ze zmienną p = 2 i w = 3. Ponieważ w nie jest równe 0, wywołujemy p * rekurencja (p, w - 1), czyli 2 * rekurencja (2, 2).

2. W wywołaniu funkcji rekurencja (2, 2), w dalszym ciągu w nie równa się 0, więc ponownie wywołujemy funkcję: 2 * rekurencja (2, 1).

3. W przypadku wywołania funkcji rekurencja (2, 1), w nadal nie równa się 0, wywołujemy zatem po raz ostatni funkcję – tym razem będzie to 2 * rekurencja (2, 0).

Funkcja rekurencja (2, 0) zwróci nam wartość 1. Teraz, gdy mamy już wartość z warunku podstawowego (początkowego), możemy obliczyć wszystkie użyte wywołania funkcji potęga. Składają się one razem na odpowiedź na zadane pytanie o wartość liczby 2 podniesionej do potęgi 3.

1. rekurencja (2, 1) to 2 * rekurencja (2, 0), czyli 2.

2. rekurencja (2, 2) to 2 * rekurencja (2, 1), czyli 4.

3. rekurencja (2, 3) to 2 * rekurencja (2, 2), czyli 8.

Tym samym udało nam się przeanalizować działanie funkcji rekurencyjnej rekurencja oraz otrzymać poprawny wynik, czyli 8.

Obliczanie silni

Specyfikacja problemu:

Dane:

• liczba – liczba naturalna

Wynik:

• silnia – iloczyn liczb od 1 do liczba; liczba naturalna

Sposób iteracyjny

int silnia_iteracyjna(int liczba)
{
    long long silnia = 1;

    for (int i = 1; i <= liczba; i++)

        silnia *= i;

    return silnia;
}

Sposób rekurencyjny

int silnia_rekurencyjna (int liczba)
{
    if (liczba < 2) 
    {
        return 1;
    }
    return liczba * silnia_rekurencyjna(liczba - 1);
}

Słownik