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

Recursivitat seguiment codi

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

1a)

def p1(num):
   if (num>0):
      print(num+” “)
      p1(num-1)
   else:
      print(“final”)

1b)

def p1(num):
   if (num>0):
     print(num+” “)
     p1(num-1)
   else:
     print(“final”)
   print(num+” “)
   print(”final de veritat “)

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

2a)

def p2( num1 , num2):
   if (num1%num2!=0):
      print(num1+” “)
      p2(num1+1,num2)
   else:
      print(“final”)

2b)

def p2(num1 , num2):
   if (num1%num2!=0):
      print(num1+” “)
      p2(num1+1,num2)
   print(“final”)

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

3)

def p3(num1, num2):
   if (num1 > 0):
      p3(num1-1,num2+num1)
   else:
      print(num2+” “)

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 i in range(1,6):
   print (“p3 (“+ i+”):”)
   p3 (i,0)

4a)

def p4 (num):
   if (num> 0):
      p4(num-1)
      print(num+” “)
   else:
      print(”fi? “)

4b)

def p4 (num):
   if (num> 0):
      p4(num-1)
      print(num+” “)
   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