Funksionet rekursive

 

Funksionet therritese (Rekursiviteti) fq 253

 

Nje funksion quhet rekursiv nese ai therret vetveten.

 

Problemet qe zgjidhen me rekursivitet kane disa te perbashketa:

Zakonisht perdoret nje funksion rekursiv i cili di te zgjidhe vetem rastin me te thjeshte qe quhet "rasti baze"

 Nese funksioni do te thirret me rastin baze ai do te ktheje thjesht nje vlere. Nese funksioni thirret me nje problem me te komplikuar ai ndahet ne dy pjese:

 

1: rasti baze - qe funksioni di ta zgjidhe dhe kthen nje vlere.

2: rasti rekursiv i cili eshte si problemi fillestar por me shkalle veshtiresie me te zvogeluar.

Edhe ne kete rast funksioni do te kete return por brenda shprehjes se kthyer ai therret vetveten.

 

Funksioni perfundon ekzekutimin e tij kur pas shume zvogelimesh te rastit rekursiv vjen radha e rastit baze dhe ne ate moment dilet nga funksioni.

 

Ka shume probleme qe mund te zgjidhen shume me thjesht me ane te rekursivitetit sesa ne menyren perseritese  (me cikle).

Nje shembull i thjeshte i demostrimit te rekursivitetit eshte faktoriali:

 

             n! = n*(n-1)*(n-2)* . . . * 1

 

psh: 5! = 5*4*3*2*1

          = 5*(4*3*2*1)

          = 5*4!

 

Ne rastin e pergjithshem :

          n! = n * (n-1)!

 

Pra rasti baze: 0! = 1! = 1

dhe rasti rekursiv  n! = n * (n-1)!

 

Pra funksioni therret vetveten me nje numer me pak deri sa te arrihet ne rastin baze.

 

Pra 5! = 5 * 4!

       = 5 * 4 * 3!

       = 5 * 4 * 3 * 2!

       = 5 * 4 * 3 * 2 * 1!

       = 5 * 4 * 3 *2 * 1

// Fig. 3.14: fig03_14.cpp

// Zgjidhja rekursive e faktorialit

#include <iostream>

#include <iomanip>

using namespace std;

unsigned long faktorial( unsigned long );

 

int main()

{

   for ( int i = 0; i <= 10; i++ )

      cout << setw( 2 ) << i << "! = "

      << faktorial(i)<< endl;

system("pause");

   return 0;

}

// funksioni rekursiv

unsigned long faktorial(unsigned long number )

{

   if ( number <= 1 )  // rasti baze

      return 1;

   else                // rasti rekursiv

      return number * faktorial( number - 1 );

}