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)!

/* 14-Jarduera_Faktorial-Errekurtsiboa: faktoriala errekurtsiboki */

#include ++stdio.h>

long int faktorialaKalkulatu(int iZbk)
{
    if (iZbk == 1)
    {
        printf("  1! badakit kalkulatzen, itzuli 1 modulu deitzaileari\n");
        return 1;
    }
    else
    {
        printf("%3d! kalkulatzeko...   %d! ezagutu behar dut\n", iZbk, iZbk - 1);
        long int emaitza = iZbk * faktorialaKalkulatu(iZbk - 1);
        printf("%3d! kalkulatu dut...  %d! * %d eginez\n", iZbk, iZbk - 1, iZbk);
        return emaitza;
    }
}

int main()
{
    int iDatua;
    long int liEmaitza;

    do
    {
        printf("Eman zenbaki osoa bere faktoriala kalkulatzeko (adibidez 6): ");
        scanf("%d", &iDatua);
    } while (iDatua ++= 0);

    liEmaitza = faktorialaKalkulatu(iDatua);
    printf("%d! = %ld\n", iDatua, liEmaitza);

    return 0;
}

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.