Zrozumienie rekurencji

Question

Witam , mam problem ze zrozumieniem rekurencji , w  algorytmie do potęgowania 

#include <stdio.h>
#include <stdlib.h>

int potega(int a, int n, int poziom);

int main ()
{
    int a = 5;
    int n = 4;

    printf("\n\n %d^%d = %d\n", a, n, potega(a, n, 1));

    return 0;
}

int potega(int a, int n, int poziom)
{
    int p;

    printf("%*c poziom %d: n = %d\n", poziom + 1, ' ', poziom, n);

    if (n == 0) {
        p = 1;
    } else {
        p = a * potega(4, n - 1, poziom + 1);
    }

    printf("%*c poziom %d: p = %d\n", poziom + 1, ' ', poziom, p);

    return p;
}

Wiem ,że to nie jest oryginalny algorytm ,ale dlaczego a * potęga(4, n-1) wypisuje potęge 4^2 = 16 i później 64 a na końcu wszystko mnoży przez 5 . jak dla mnie jest to kompletnie nie zrozumiałe zachowanie 

Answer 1

mnoży przez 5, bo idziesz od początku :) czyli ostatnia operacja jest tą która idąc w kodzie linijka po linijce jest pierwsza.
Stąd jak na początku masz a * coś tam... to a =5 na początku stąd w wyniku na końcu mnożysz wszystko przez 5,  poprzednie wyniki sa wynikami REUKRENCYJNYCH FUNKCJI czyli tego 
 

potega(4, n - 1, poziom + 1);

 i z każdym wywołaniem tej funkcji idziesz jakby w głąb, a błąd polega na tym że posyłasz ciągle tę samą wartość ...  czyli 4. 

potega(4, n - 1, poziom + 1);

a powinieneś potega(a, n - 1, poziom + 1);

Comments

Dzięki , opowiedziałeś na moje pytanie , nie chodziło mi  o to ,że  return potega jest zły ,bo wiem ,że jest zły ,ale raczej dlaczego  ostatni wynik jest mnożony przez 3 ,a nie przez 4 , już wiem ,bo ostatnią liczbą funkcji rekurencyjnej jest  zadeklarowane a ,czyli 3. Jest jeszcze jedna opcja, Napisanie  return 3 * potega(4, n - 1, poziom + 1); i tu wypisuje same potęgi 3 ,czyli 3 , 9 ,27  bo wykładnik to 3 ,ale dlaczego 4 nie ma znaczenia w tym przypadku , tzn ja moge zamiast 4 wpisać dowolną liczbę i ostatni wynik to 27 będzie cały czas

---

Jeśli wypisujeszcoś na końcu funkcji ... a masz rekurencje to zauważ że najbardziej  Z BRZEGU FUNKCJA, WYKONA SIĘ NA KOŃCU, bo do jej końca musi rekurencyjnie wywołać siebie- w śodku stąd "podająć jako pierwszy parametr liczbę 3 --- ona będzie na samym ko ncu" bo cześniej wykona się funkcja dla 2, 1, no i np. 0 bo działa rekurencja

---

co z tą 4 się dzieje ?

Answer 2

Jest oczywisty błąd. Powinno być a * potęga (a, n-1, poziom+1). Może dlatego trudno zrozumieć.