Informatika 2023-24: Errekurtsibitatea zertan den

2024(e)ko otsailaren 28(a), asteazkena

Errekurtsibitatea zertan den

Ez dugu ariketa errekurtsibo asko aurkituko gure programetan, baina interesgarria da kontzeptu hori lantzea azpiprogramak aktibatzen direnean zer gertatzen den ikasteko.

Egoera errekurtsiboak bizitzan eta naturan ematen dira eta jarraian adibide grafikoak erakusten dira:

iZenbaki zenbaki baten faktoriala kalkulatzen duen funtzio errekurtsiboa erakusten da jarraian. Faktorialaren kalkulu errekurtsiboa algoritmo honetan oinarritzen da:

iZenbaki! = iZenbaki * (iZenbaki - 1)!

program FaktorialErrekurtsiboaAzaltzen ;

function fnliFaktorialaKalkulatu(iZbk: integer) : longint  ;
begin
   if iZbk = 1 then
   begin
      WriteLn('1! badakit kalkulatzen, itzuli 1 modulu deitzaileari') ;
      fnliFaktorialaKalkulatu := 1 ;
   end
   else
   begin
      writeln(iZbk, '! kalkulatzeko ', iZbk-1, '! ezagutu behar dut') ;
      fnliFaktorialaKalkulatu := iZbk * fnliFaktorialaKalkulatu(iZbk - 1) ;
      writeln(iZbk, '! kalkulatu dut ', iZbk-1, '! * ', iZbk, ' eginez') ;
   end ;
end ;


var
  liEmaitza : longint ;
  iDatua : integer ;

begin
   repeat
      write('Eman zenbaki osoa: ') ;
      readln(iDatua) ;
   until iDatua > 0 ;
   liEmaitza := fnliFaktorialaKalkulatu(iDatua) ;
   writeln(iDatua, '! = ', liEmaitza) ;
   readln ;
end.

FaktorialErrekurtsiboa.pas programa hartu eta zuk zeuk exekutatu.

Fibonacciren segidaren adierazpen orokorra gogoratuz:

$F_{n}={\begin{cases}0&n=0{\mbox{ bada}}\\1&n=1{\mbox{ bada}}\\F_{n-1}+F_{n-2}&n>1{\mbox{ bada}}\\\end{cases}}$

Hauxe da fniFibonacci funtzio errekurtsiboa:

{-------------------------FUNTZIO ERREKURTSIBOA-------------------------}
function fniFibonacci(iZbk: integer): integer ;
begin
   if (iZbk = 0) or (iZbk = 1) then
      fniFibonacci := iZbk
   else
      fniFibonacci := fniFibonacci(iZbk-1) + fniFibonacci(iZbk-2) ;
end ;

Teklatuaren bitartez iZenbat kopuru oso bat irakurri eta Fibonacci-ren lehen iZenbat zenbakiak pantailaratu. Hauxe da programa eta bere exekuzioaren irteera bat:

program FibonacciErrekurtsiboa ;
uses
   crt ;
const
   AZKENMUGA = 24 ;    { integer datu-motak ez du gehiago ematen }


{-------------------------FUNTZIO ERREKURTSIBOA-------------------------}
function fniFibonacci(iZbk: integer): integer ;
begin
   if (iZbk = 0) or (iZbk = 1) then
      fniFibonacci := iZbk
   else
      fniFibonacci := fniFibonacci(iZbk-1) + fniFibonacci(iZbk-2) ;
end ;


{---------------------------PROGRAMA NAGUSIA---------------------------}
var
   iZenbat, iKont: integer ;
   cErantzuna: char ;
begin
   writeln ;
   repeat
      repeat
         write('Eman Fibonacci segidaren zenbaki kopurua (1 eta ', AZKENMUGA,' artekoa): ') ;
         readln(iZenbat) ;
      until (iZenbat >= 1) and (iZenbat <= AZKENMUGA) ;

      writeln ;

      for iKont:=1 to iZenbat do
      begin
         if (iKont = 1) or (iKont = 2) then
            writeln(iKont:20, ' >>>>>> ', fniFibonacci(iKont-1))
         else
            writeln(iKont:20, ' -----> ', fniFibonacci(iKont-1)) ;
      end ;

      writeln ;

      write('Amaitu nahi duzu? (B/E): ') ;
      repeat
         cErantzuna := readkey ;
         writeln(cErantzuna) ;
         cErantzuna := upcase(cErantzuna) ;
      until (cErantzuna = 'B') or (cErantzuna = 'E') ;
      writeln ;
      writeln ;
   until cErantzuna = 'B' ;
   
   write('Programa bukatu da') ;
   
   repeat until keypressed ;
end.

Goiko programa hobeto ulertzeko, aztertu ere FibonacciErrekurtsiboa_formatua.pas bertsioa non pantailan idazketa batzuk egiten diren, eta horiei esker programa exekutatzean ikus daiteke kodearen zein puntutan aurkitzen garen.