Rekurencja, problem ze zrozumieniem.

Question

Mam problem ze zrozumieniem działania rekurencji. U mnie w liceum (rozszerzona informatyka) nauczyciel niestety zna podstawy podstaw C++ i od niego nic nie mogę się dowiedzieć. 

Podam przykład:

#include <iostream>
using namespace std;

int suma (int a)
{
    if (a<1)
    return 0;



    return a+suma(a-1);
}


int main()
{
    int a;
    cout << "Podaj ilosc liczb naturalnych: ";
    cin >> a;

    cout << "Suma " << a << " liczb naturalnych wynosi: " << suma(a);
    return 0;
}

Nie rozumiem tego w jaki sposób ta funkcja żyje. Jest to program do liczenia sumy a początkowych liczb naturalnych. Na przykład wpiszę 3. Napiszę listę kroków jak ja to rozumiem, a wy mnie poprawcie. 

1. 3 >= 1 więc suma nie zwraca 0

2. zwracana wartość 3+suma(3-1) = 5

3. i dalej co?

No i ja nie rozumiem tego dlaczego ta funkcja się zachowuje jak pętla. Mogłby mi ktoś w liście kroków napisać jak ta funkcja przebiega?

Answer 1

Pan Mirosław Zelent poświecił jeden z swoich filmów temu zagadnienu: http://youtube.com/watch?v=jNi_X5bvmQ

Answer 2

W 13 odcinku kursu programowania miroslawa zelenta na youtube jest to naprawde dobrze wytlumaczone, zajrzyj

Answer 3

ta funkcja wywołuje samą siebie, do momentu aż warunek się spełni, potem od końca wypisuje wyniki

Answer 4

To taka zaawansowana pętla. Jedziemy od 3. Potem 2 potem 1 i gdy jes zero to jest zero. Czyli 3+2+1+0=6

Answer 5

Żeby to łatwo zrozumieć musisz sobie zawsze rozpisywać po kolei co, kiedy i dla czego. W przypadku sumowania "a" pierwszych wyrazów trzeba się zastanowić jaki jest początkowy wyraz. Jest nim liczba 1 więc suma np. 3 pierwszych liczb to 1+2+3=6. Podając funkcji argument podajesz na którym stopniu takiej drabinki stoisz. Poprzedni stopień zawsze jest równy sumie n-1 a obecny (n-1)+n. Żeby obliczyć n-1 musisz spowrotem wywołać funkcje itd.

Moze to troche zagmatwałem ale na przykładzie: Funkcja dostaje argument 3, sprawdza czy jest równy 1 (najmniejszej możliwej wartości/wartości początkowej), jeśli jest to zwraca (return) właśnie tą liczbe czyli w tym przypadku jeden, jeśli nie jest równe 1 to (else) wywołuje samą siebie żeby obliczyć 3-1 czyli jako argument podaje właśnie 2. 

Dla 2 funkcja dalej będzie musiała wywołać samą siebie ale już dla 2-1 czyli 1. Teraz zostaje spełniony warunek (if funkcji) ponieważ 1=1 i funkcja zwraca wartość 1, niby nic ale zwrócona wartość jest podstawiana wyzej ( w lini "else return funkcja(n-1)+n") i zwraca wartość 1+2 czyli 3, zwrócona wartość podstawiona jest wyżej i pętla zwraca końcową wartość czyli 3+3=6 dla trzeciego wyrazu ciągu zaczynajacego się od 1.

int suma ( int a ){
if ( a==1 ) return 1;
else return suma ( a-1 )+a;
}