ASIX-M3-UF2-A3.1-Exercicis recursivitat

Recursivitat seguiment codi

Indicar quina serà la sortida dels procediments següents:

1a)

void p1( int a ) {
   if (a>0) {
      System.out.print(a+” “);
      p1(a-1);
   }
   else {
      system.out.print(“final”)
   }
}

1b)

void p1( int a ) {
   if (a>0) {
     System.out.print(a+” “);
     p1(a-1);
   }
   else {
     System.out.print(“final”)
   }
   System.out.print(a+” “);
   System.out.print(”final de veritat “);
}

Quina seria la sortida si executéssim p1(6)?

2a)

void p2( int a , int b) {
   if (a%b!=0) {
      System.out.print(a+” “);
      p2(a+1,b);
   }
   else {
      System.out.print(“final”);
   }
}

2b)

void p2( int a , int b) {
   if (a%b!=0) {
      System.out.print(a+” “);
      p2(a+1,b);
   }
   System.out.print(“final”);
}

Quina seria la sortida si executéssim p2(10,8)?

3)

void p3(int a, int b ){
   if (a > 0){
      p3(a-1,b+a);
   }
   else
   {
      System.out.print(b+” “);
   }
}

Quina seria la sortida si executéssim p3(5,3)?

Quina seria la sortida si eliminéssim el else ( fent sempre el print ) i des del programa principal féssim:

for (int i=1;i<=5;i++){
   System.out.print (“p3 (“+ i+”):”);
   p3 (i,0);
}

4a)

void p4 ( int a) {
   if (a> 0) {
      p4(a-1);
      System.out.print(a+” “);
   }
   else {
      System.out.print(”fi? “);
   }
}

4b)

void p4 ( int a) {
   if (a> 0) {
      p4(a-1);
      System.out.print(a+” “);
   }
   System.out.print(”fi? “);
}

Quina seria la sortida si executéssim p4(5)?

5)

void p5( int a ) {
   if (a>0 {
      System.out.print(a+” “);
      a=a-1;
      p5(a);
   }
   System.out.print(a+” “);
}

Quina seria la sortida si executéssim p5(5)?

6)

void p6(int a ){
   System.out.print(a+” “);
   for ( int i =a; i>0;i--){
      p6(i-1);
   }
}

Quina seria la sortida si executéssim p6(4)?

7)

int f1 ( int a ) {
   int f;
   if ( a>0) f= f1(a-1) + 1;
   else f=0;
   return f;
}

Que retornaria f1(10)?

8 )

int f2 ( int a ) {
   int f;
   if ( a>0) f= f2(a-1) + a;
   else f=0;
   return f;
}

Que retornaria f2(10)?

9)

int f3 ( int a ) {
   int r,i,f;
   if (a>0) {
      r=a;
      for ( i= a-1;i>0;i--){
         r= r + f3(i);
      }
      f=r;
   }
   else f=a;
   return f;
}

Què retorna f3(6)?

Trobar el cas general (què fa la funció) i escriure-la d’una altra forma més senzilla

10)

int f4( int x ){
   int f;
   if (x> 100)  f=x-10;
   else f= f4(f4(x+11));
   return f;
}

Què retorna f4(100), i f4(0)? Fer el programa més senzill.

Recursivitat codi

1. Torres de Hanoi (amb N introduïda per l’usuari com a paràmetre). S’ha d’anar visualitzant la solució per pantalla.

2. Escriure una funció recursiva que donat un número N (N ≥ 0) passat com a paràmetre calculi la suma de tots els números enters fins a N inclòs.

3. Escriure una funció recursiva que calculi el resultat de X elevat a N amb N >0, sabent que X0 = 1.

4. Escriu una funció recursiva per calcular la suma digital d’un número natural. Per exemple, la suma digital de 18624 és: 4 + 2 + 6 + 8 + 1 = 21

5. Dissenyeu un algoritme recursiu que calculi el màxim comú divisor de dos enters positius, sabent que :

     MCD( X, Y) = MCD (X-Y, Y) SI X > Y
     MCD (X, Y-X) SI Y > X
     X SI X = Y

6. Fes la funció recursiva float SumaHarmonica ( int n ) que retorna la suma :

     1 + 1/2 +1/3 + ... + 1/n

7. Fes una funció recursiva que vaig imprimint la descomposició factorial d’un número enter.

8. Fes una funció recursiva booleana que donats un número i un dígit retorni si aquest dígit pertany al número. Per exemple existeix (1234,3) → true, existeix (1234,7) → false

9. Fes una funció que calculi el producte segons el mètode rus que diu que:

     x*y = ((2*x) *(y/2)) SI y es parell
     x*y =((2*x) *(y/2))+ x SI y és senar.

     Quan y val 1, el resultat és x.

10. Fes una funció recursiva que ompli un tauler n-goro. Un tauler n-goro és una matriu de n files i n+1 columnes que s'omple consecutivament en diagonal i quan ens sortim per una banda entrem per l'altra. L'últim element que s'omple serà l'extrem inferior dret.

     Per exemple amb n=3

       1 10 7 4
       5 2 11 8
       9 6 3 12

     Amb n = 4

       1 17 13 9 5
       6 2 18 14 10
       11 7 3 19 15
       16 12 8 4 20