Programowanie i algorytmy

Rekurencja w C++

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ą miały nieznacznie wolniejszy czas od iteracyjnego odpowiednika (wiąże się to z wywoływaniem funkcji), natomiast rozwiązanie niektórych problemów jest znacznie wygodniejsze.

Przykład 1

Prześledźmy program wyznaczający sumę n kolejnych liczb naturalnych.

#include <cstdlib>
#include <iostream>
 
using namespace std;
 
long long suma(int n)
{
  if(n<1) 
    return 0;
 
  return n+suma(n-1);
}
 
int main()
{
  int n;
 
  cout<<"Podaj liczbę: ";
  cin>>n;
 
  cout<<"Suma "<<n<<" kolejnych liczb naturalnych wynosi "
<<suma(n)<<endl;
 
  system("pause");
  return 0;
}
 

 

Załóżmy, że na wejściu podaliśmy liczbę 5 (program ma wyznaczyć sumę 1+ 2+ 3 + 4 + 5).

wynik = suma(5);

Funkcja suma(n), wywołała się z argumentem równym 5. Najpierw sprawdzamy, czy n< 1 (5 < 1). Warunek jest fałszywy, przechodzimy więc do następnej linijki return 5 + suma(5 - 1) . Funkcja suma wywołana została przez samą siebie z argumentem równym 4, a więc mamy:

wynik = suma(5) = 5 + suma(4),

daną czynność powtarzamy do momentu, gdy argument osiągnie wartość 0, wtedy funkcja zwróci 0 (0 < 1, prawda).

wynik = suma(5) = 5 + suma(4) = 5 + 4 + suma(3) = 5 + 4 + 3 + suma(2) = 5 + 4 + 3 + 2 + suma(1) =

5 + 4 + 3 + 2 + 1 + suma(0) = 5 + 4 + 3 + 2 + 1 + 0 = 15. 

Przykład 2

Wykonajmy zamianę liczby w systemie dziesiętnym na system dwójkowy. Algorytm jest wyjaśniony pod tym adresem.

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.

rekurencja z nawrotami 

Rozwiązanie w C++ (dla liczby 0 należy rozpatrzeć oddzielnie)

 

#include<iostream>
#include<cstdlib>
using namespace std;
 
void zamien(int n)
{
  //jesli n == 0 to zawracamy
  if(n==0)return;
 
  zamien(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 
      zamien(n);
 
   cout<<endl;
    system("pause");
    return 0;
}

 

Przykładowe algorytmy, które są realizowane tą techniką:

 

Zobacz podobne: