Faktoriela

Rekurzivna definicija:

 

n!  =  n * (n-1) * (n-2) * … * 3 * 2 * 1

 

To lahko zapišemo tudi na drugi način:

 

n * (n-1) * (n-2) * … * 3 * 2 * 1 =

n * (n-1)!  

Primer:

Po predpostavki, da je 1! enaka 1 lahko zapišemo naslednji program:

 

int fac (int  n)
{

  if (n == 1) { return 1; }
  return  n * fac (n - 1);
}

 

Vzamimo klic funkcije fac(4):

 

{if (n==1)  return 1; else return  n*fac(n-1);}

{if (4==1) return 1; else return 4*fac(4-1);}

{if (0) return 1; else return 4*fac(4-1);}

4*fac(4-1)

4*fac(3)

4*{if (n==1) return 1; else return n*fac(n-1);}

4*{if (3==1) return 1; else return 3*fac(3-1);}


4*{if (3==1) return 1; else return 3*fac(3-1);}

4*{if (0) return 1; else return 3*fac(3-1);}

4*3*fac(3-1)

4*3*fac(2)

4*3*{if (n==1) return 1; else return n*fac(n-1);}

4*3*{if (2==1) return 1; else return 2*fac(2-1);}

4*3*{if (0) return 1; else return 2*fac(2-1);}

4*3*2*fac(2-1)

4*3*2*fac(1)

4*3*2*{if (n==1) return 1; else return n*fac(n-1);}

4*3*2*{if (1==1) return 1; else return n*fac(1-1);}

4*3*2*{if (1==1) return 1; else return n*fac(1-1);}

4*3*2*{if (1) return 1; else return n*fac(1-1);}

4*3*2*1

12*2*1

24*1

24

 

Alternativa

 

• Namesto, da izračunavamo:
                         n * fac ( n - 1)
  
  Lahko gremo v drugi smeri:

                              1 * 2 * 3 * 4 * … * ( n - 1 ) * n

                        (((((1) * 2) * 3) * 4 ) * … * (n - 1)) * n

 

• S števcem gremo od 1 do n
• Za vsako ko števec povečamo za 1, faktorieli pomnožimo vrednost števca.

Programski kod

 

int fac-iter (int produkt, int stevec, int max)
{

  if (stevec > max) { return produkt };
  return fac-iter ((stevec * produkt), (stevec + 1), max);

}

int fac (int n)
{
  return fac-iter (1, 1, n);
}

 

Uporabimo naslednji model zamenjave:

  

fac(4)

fac-iter(1, 1, n)

fac-iter(1, 1, 4)

{if (stevec > max) return produkt;

return fac-iter((stevec*produkt), (stevec+1), max);}

{if (1 > 4) return 1; return fac-iter((1*1), (1+1), 4);}

{if (0) return 1; return fac-iter((1*1), (1+1), 4);}

return (fac-iter(1, 2, 4);)

{if (stevec > max) return produkt;

return fac-iter((stevec*produkt), (stevec+1), max);}

{if (2 > 4) return 1; return fac-iter(2*1, 2+1, 4);}

return(fac-iter(2, 3, 4);)

{if (stevec > max) return produkt;

return fac-iter((stevec*produkt), (stevec+1), max);}

{if (3 > 4) return 2; return fac-iter(3*2, 3+1, 4);}

{if (0) return 2; return fac-iter(3*2, 3+1, 4);}

return(fac-iter(6, 4, 4);)

{if (stevec > max) return produkt;

return fac-iter((stevec*produkt), (stevec+1), max);}

{if (4 > 4) return 6; return fac-iter(4*6, 4+1, 4);}

{if (0) return 6; return fac-iter(4*6, 4+1, 4);}

{if (stevec > max) return produkt;

return fac-iter((stevec*produkt), (stevec+1), max);}

{if (5 > 4) return 24; return fac-iter((5*24), (5+1), 4);}

{if (1) return 24; return fac-iter((5*24), (5+1), 4);}

return( 24 )

24

 

Tej rekurziji pravimo tudi repna rekurzija .

Pri repni rekurziji se vse računske operacije izvedejo preden se izvede rekuzivni klic funkcije.