Ćwiczenia z informatyki

Rekurencja zwana rekursją, polega na wywołaniu przez funkcję samej siebie.
Algorytmy rekurencyjne zastępują w pewnym sensie iteracje.
Niekiedy problemy rozwiązywane tą techniką będą nieznacznie wolniejsze (wiąże się to z wywoływaniem funkcji), natomiast rozwiązanie niektórych problemów jest dużo prostrze w implementacji.

Przykład 1 - zamiana liczby dziesiętnej na binarną

Algorytm zamiany opisałem w dziale systemy liczbowe
Do rozwiązania problemu użyjemy rekurencji z nawrotami.
Funkcja będzie wywoływać samą siebie, i w momencie gdy już "głębiej" się nie zagnieździ będzie powracać aby wykonać pozostałe instrukcje.
Dzięki temu wypisane bity będą w prawidłowej kolejności.

Działanie funkcji można przedstawić na diagramie: diagram dec2bin rekurencja

Implementacja przedstawia się następująco:

#include <iostream>
using namespace std;
 
void dec2bin(int n)
{                    
    if(n==0) return;  //jesli n == 0 to zawracamy
    dec2bin(n/2); //zagnieżdżamy rekurencję
    cout<<n%2; //przy powrocie 
}
 
int main()
{
    int n;
    cout<<"Podaj liczbę naturalną: ";
    cin>>n;
    cout<<"Postać binarna liczby "<<n<<": ";
    if(n==0) 
        cout<<0;
    else 
        dec2bin(n);
    
    return 0;
}

ćwiczenie

Napisz procedurę suma(int n), która poda sumę liczb od 0 do n.

Przykład 2 - NWD - algorytm Euklidesa

Algorytm wyszukiwania oraz kod iteracyjny opisałem w dziale NWD - metoda modulo

#include<iostream>
using namespace std;
 
int NWD(int a, int b)
{
    if(b!=0)
        return NWD(b,a%b);   
    return a;
}
 
int main()
{
    int a, b;
 
    cout<<"Podaj dwie liczby: ";
    cin>>a>>b;
 
    cout<<"NWD("<<a<<","<<b<<") = "<<NWD(a,b)<<endl;

    return 0;
}

Przykład 3 - ciąg Fibonacciego

Rekurencja jest metodą, która nie wszędzie ma zastosowanie.
Przykładem jest ciąg Fibonacciego.

#include <iostream>
using namespace std;
unsigned fib( unsigned n )
{
    if( n == 0 ) return 0;  
    if( n <= 2 ) return 1;
    return fib( n - 1 ) + fib( n - 2 );
}

int main()
{
    cout << fib( 6 );
}

Procedura ta podaje n-ty element ciągu. W przypadku elementu szóstego ilość wywołań przedstawia się następująco: rekurencja Widać zatem, że jest bardzo nieoptymalna.

Dla wskazania elementu 10-tego: rekurencja ale już 15-tego:

Porównanie czas dla: 45, 47 i 50 elementu (czas podany jest w milisekundach): rekurencja Widać, że dla większych wartości praktycznie czas wykonania uniemożliwia podanie wyniku.
Procedura iteracyjna wyświetlająca wszystkie elementy wykonuje się w 6 ms - różnica jest zatem znacząca.

zadania

Wykorzystując metodę rekurencji napisz następujące procedury.
Umieść je w pliku rekurencja.cpp

Napisz procedurę silnia(n) obliczającą iloczyn liczb z zakresu: <1..n>.
silnia(0)=1
Zwróć uwagę, że: od pewnej wartości (tu 21) następuje przekroczenie zakresu liczb.
Napisz procedurę malejaco_rosnaco(n) wyświetlającą liczby od n do 0, następnie od 0 do n.
Napisz procedurę suma_cyfr(n), która wyznaczy sumę cyfr liczby naturalnej z zakresu [0...10²⁰].
Wskazówka:
Aby wyłuskać cyfrę jedności danej liczby należy wykonać operację:
cyfra=n mod 10
gdzie mod oznacza resztę z dzielenia.
Następnym krokiem jest skrócenie liczby o jedną cyfrę wykonując operację
n=n div 10
gdzie div oznacza dzielenie całkowite.
Powtarzamy te operacje do momentu otrzymania liczby 0.
Napisz procedurę dec2sys(liczba, podstawa) zamieniającą liczbę na liczbę systemu podstawa.