Tema 1. Recursividad - us

Tema 1. RecursividadAnálisis y Diseño de Algoritmos

ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA INFORMÁTICA

Departamento de Lenguajes y Sistemas InformáticosCurso 2010-2011

Índice

1. Concepto2. Tipos de Recursividad3. Recursividad lineal

3.1. No final3.2. Final

4. Recursividad Múltiple

Análisis y Diseño de Algoritmos 2

4. Recursividad Múltiple5. Transformación Recursión-Iteración

5.1 Iteración Lineal Final5.2 Iteración Lineal No Final5.3 Recursividad Múltiple e Iteraciones

6. Ejercicios

1. Concepto

� Un algoritmo recursivo es aquél que expresa lasolución de un problema en términos de llamada ollamadas a sí mismo. Cada llamada a sí mismo sedenomina llamada recursiva.

T2 f( T1 n){

...


� Los algoritmos recursivos son apropiados si la definicióndel problema está planteada de forma recursiva.

� La recursividad es una alternativa a la iteración, comoveremos más adelante.

...

v = f(...);

...

}

2. Tipos de recursividad

�Según el número de llamadas,� Recursividad simple o lineal : en cada llamada recursiva se

ejecuta, a lo sumo, una llamada a la propia función. Se puederepresentar gráficamente mediante una lista. Algunosejemplos son el factorial o la búsqueda dicotómica.


� Recursividad múltiple : en cada llamada recursiva puedenejecutarse más de una llamada a la propia función. En estetema se considerarán sólo algoritmos recursivos múltiplescon 2 llamadas recursivas dentro de la misma función,aunque pudiera haber más. Este tipo de recursividad sepuede representar gráficamente mediante un árbol binario.Algunos ejemplos son el Quicksort o el cálculo del número deFibonacci.

3. Recursividad Lineal


Recursividad Lineal

� En una definición recursiva se distinguen, como mínimo, 2 partes:caso trivial o base y caso recursivo.

� Según la posición de la llamada recursiva, para el caso de larecursividad lineal se distinguen:a. Recursividad no final : tras la llamada recursiva se realiza un

6

a. Recursividad no final : tras la llamada recursiva se realiza unprocesamiento hasta llegar al resultado de la llamada.

b. Recursividad final : no hay procesamiento. El resultado de la llamadarecursiva coincide con el resultado final buscado.

Recursividad Lineal

a. Definición recursiva de Factorial (Rec. no final):

n! =1 si n= 0

n (n-1)! si n >0 Caso RecursivoCaso Base

7

b. Definición ecursiva del Máximo Común Divisor (Rec. Final):

mcd(a,b) = a si b = 0

mcd(b,a%b) si b >0 Caso Recursivo

Caso Base

Recursividad Lineal No Final

� Representación gráfica del cálculo del Factorial para n = 4, donde cadanodo representa una llamada recursiva y tiene dos parámetros, n y r. Lafunción siguiente va transformando los datos de entrada. En este caso,siguiente(n) = n-1.

Caso base

4, r 3, r1 2, r2 1, r3 0, 1

siguiente(4) siguiente(3) siguiente(2) siguiente(1)


� Una vez que se llega al caso base, si estamos en recursividad final, ya setiene el resultado. En cambio, si es no final, es necesario iterar hacia atráspara ir generando los resultados requeridos, como es el caso del factorial.En este caso, combina(n,r)=n*r

4, r 3, r1 2, r2 1, r3 0, 1

Caso base

4, 24 3, 6 2, 2 1, 1 0, 1

combina(1,1)combina(2,1)combina(3,2)combina(4,6)

Recursividad Lineal Final

� Representación gráfica del cálculo del máximo común divisorde 20 y 15.

� Llamada inicial mcd(20,15).� Función siguiente(a,b) = <b,a%b>� siguiente(20,15) = <15,5>� siguiente(20,15) = <15,5>


Caso base

(20,15) (15, 5) (5, 0)

siguiente(20,15) siguiente(15,5)

Recursividad Lineal

� En general, calcular recursivamente una solución consiste en:� En el caso de la recursividad final, ir calculando el siguiente

problema y realizar llamadas recursivas hasta que lleguemos alcaso base (ya tenemos el resultado requerido).

� En el caso de la recursividad no final, ir calculando el siguienteproblema y realizar llamadas recursivas hasta que lleguemos alcaso base, tras lo cual es necesario ir combinando los resultadosparciales hasta obtener el resultado requerido.


parciales hasta obtener el resultado requerido.� La recursividad final puede verse como un caso particular de

la recursividad no final en el que combina(n, r) = r.� En general, para resolver problemas recursivos se propone

trabajar con:� Fichero de cabecera (.h): Incluye la definición de tipos y la

declaración de prototipos para las funciones.� Fichero fuente (.c): Incluye el código para las distintas funciones.� Programa principal (main).


RecLinealNoFinal.h

typedef enum{false, true} logico;T2 f( T1 n);logico esCasoBase (T1 n);T2 solucionBase (T1 n);T1 siguiente (T1 n);

Definición de tipos.

Declaración de prototipos.


T1 siguiente (T1 n);T2 combina (T1 n, T2 rSig );

Para resolver un problema concreto, en el archivo “.h” T1 será reemplazado por el tipo del parámetro de entrada, mientras T2 por el tipo del parámetro de salida.


RecLinealNoFinal.c#include “RecLinealNoFinal.h”

// Esquema general para cualquier problema Rec No Final (común)

T2 f( T1 n) {

T1 nSig;

T2 r,rSig;

if ( esCasoBase (n)) {

Para resolver un problema concreto, en el archivo “.c” T1 será reemplazado por el tipo del



r = solucionBase(n);

}

else {

nSig = siguiente(n);

rSig = f(nSig);

r = combina(n, rSig);

}

return r;

}

…

será reemplazado por el tipo del parámetro de entrada, mientras T2 por el tipo del parámetro de salida.


RecLinealNoFinal.c…

// Métodos específicos para el problema a resolver

logico esCasoBase( T1 n) {

…

}

T2 solucionBase( T1 n) {




…

}

T1 siguiente( T1 n) {

…

}

T2 combina( T1 n, T2 rSig) {

…

}

será reemplazado por el tipo del parámetro de entrada, mientras T2 por el tipo del parámetro de salida. Además, se les dará código a los distintos métodos.


Principal.c#include <stdio.h>

#include “RecLinealNoFinal.h”

void main ( void ) {

T1 n;

Para resolver un problema concreto, en el archivo “.c” T1 será reemplazado por el tipo del parámetro de entrada, mientras T2 por el tipo del parámetro de salida.


T2 r;

printf (“Introduzca el valor para la entrada: ”);

scanf (“%efT1”, &n);

r = f (n);

printf (“El resultado de la función recursiva para la entrada %efT1 es %efT2”,n,r);

} Especificadores de formato: %c carácter %d int%ld long %f float%lf double %s cadena de carácteres

Ejemplo Rec No Final: Factorial

Factorial.h

typedef enum{false, true} logico ;int f( int n);logico esCasoBase (int n);int solucionBase (int n);int siguiente (int n);


int siguiente (int n);int combina (int n, int rSig );

T1 y T2 han sido sustituidos por int .


Factorial.c#include “Factorial.h”

// Esquema general para cualquier problema Rec No Final (común)

int f( int n) {

int nSig;

int r,rSig;






}

else {

nSig = siguiente(n);

rSig = f(nSig);

r = combina(n, rSig);

}

return r;

}

…


Factorial.c…


logico esCasoBase( int n) {

return n == 0 ;

}

int solucionBase( int n) {

T1 y T2 han sido sustituidos por int y los métodos han sido implementados.


int solucionBase( int n) {

return 1;

}

int siguiente( int n) {

return n - 1 ;

}

int combina( int n, int rSig) {

return n * rSig ;

}

implementados.



#include “Factorial.h”


int n;



int r;


scanf (“%d”, &n);

r = f (n);

printf (“El resultado de la función recursiva para la entrada %d es %d”,n,r);

}

Especificadores de formato adecuados (%d int)



int n, r;


� La metodología anterior nos permite seguir unos pasos para resolver elproblema: esCasoBase, Siguiente, Combina, …� Una vez seguidos los pasos podemos desplegar las funciones del esquema yquedarnos con un método que resuelve el problema, sustituyendo en elesquema cada función (esCasoBase, …) por su cuerpo.



scanf (“%d”, &n);

r = factorialRec (n);

printf (“El resultado para la entrada %d es %d”, n, r);

} int factorialRec( int n){

int r; if (n == 0)

r = 1;else

r = n * factorialRec (n - 1);return r;

}

Recursividad Lineal Final

� Para el caso de la recursividad lineal final, se seguiría elmismo esquema que para la no final, con laparticularidad de que el método combina presentasiempre la misma forma, independientemente delproblema que se esté resolviendo.


// Método combina Rec Lineal Final

T2 combina( T1 n, T2 rSig) {return rSig;

}

Múltiples parámetros de entrada

�Cuando el número de datos de entrada es mayorque uno, se proponen dos enfoques:� Usar un tipo auxiliar para gestionar dichos parámetros de

forma conjunta, empaquetando varios datos en uno através del uso de estructuras.través del uso de estructuras.

� Enfoque clásico: Definir tantos parámetros en el métodocomo datos de entrada se requieran.

�A continuación se verán ambos enfoques aplicadosal problema del cálculo del máximo común divisor(Rec. Lineal Final).


Datos complejos: Estructuras

typedef struct{

T1 c1 ;

T2 c2 ;

� En función del número y tipo de los parámetros de entrada,se definen las estructuras DosDatos, TresDatos, … NDatos.


T2 c2 ;

…

TN cn ;

} NDatos;

NDatos var ;

Uso de estructuras para el mcd

Mcd.h

� Para el caso del mcd(a,b) , el tipo del parámetro de entrada(T1) es DosDatosInt , mientras el de salida (T2) es int .

� El par (a,b) se representa como una variable de tipoDosDatosInt , donde c1 representa al valor a, mientras c2representa a b.


Mcd.htypedef enum{false, true} logico ;typedef struct{

int c1;int c2;

} DosDatosInt;int f (DosDatosInt n);logico esCasoBase (DosDatosInt n);int solucionBase (DosDatosInt n);DosDatosInt siguiente (DosDatosInt n);int combina (DosDatosInt n, int rSig );


Mcd.c#include “mcd.h”

int f (DosDatosInt n) {DosDatosInt nSig;int r,rSig;if (esCasoBase(n)) {



r = solucionBase(n);}else {

nSig = siguiente(n);rSig = f(nSig);r = combina(n, rSig);

}return r;

} …


Mcd.c…logico esCasoBase (DosDatosInt n) {

return n.c2 == 0;} int solucionBase (DosDatosInt n) {

return n.c1;}

Mediante el operador “.” se accede a los miembros de la estructura.


}DosDatosInt siguiente (DosDatosInt n) {

DosDatosInt nSig = {n.c2,n.c1%n.c2}; return nSig;

} int combina (DosDatosInt n, int rSig ) {

return rSig;}


Ppal.c#include <stdio.h>#include "mcd.h"

void main (void) {DosDatosInt n;int r ;printf ("Introduzca los valores para la entrada: ");


printf ("Introduzca los valores para la entrada: ");scanf ("%d %d", &(n.c1), &(n.c2)); r = f (n);printf ("El resultado de la función recursiva es %d", r);

}


void main (void) {

DosDatosInt n;

int r;

printf ("Introduzca los valores para la entrada: ");

scanf ("%d %d", &(n.c1), &(n.c2));

r = mcdRec(n);

� Nuevamente, desplegando las funciones del esquemaobtenemos un único método que resuelve el problema.


r = mcdRec(n);

printf ("El resultado es %d", r);

}

int mcdRec(DosDatosInt n){

int r;

if (n.c2 == 0) {

r = n.c1;

}

else {

DosDatosInt nSig = {n.c2,n.c1%n.c2};

r = mcdRec(nSig);

}

return r;

}

Enfoque clásico para el mcd

� En el enfoque clásico, el dato de entrada se maneja comodos parámetros de tipo int .� Cuando dichos datos son el parámetro de salida de algúnmétodo (ej. siguiente ), es necesario pasarlos comoparámetros de entrada salida (por referencia).


Mcd.htypedef enum{false, true} logico ;int f (int nC1, int nC2);logico esCasoBase (int nC1, int nC2);int solucionBase (int nC1, int nC2);void siguiente (int nC1, int nC2, int * nSigC1 , int * nSigC2 );int combina (int nC1, int nC2, int rSig );

Paso de parámetros por referencia.


Mcd.c#include "mcd.h"

int f( int nC1, int nC2) {int nSigC1, nSigC2; int r,rSig;if ( esCasoBase (nC1,nC2)) {

r = solucionBase (nC1,nC2); Parámetros de entrada salida


r = solucionBase (nC1,nC2);}else {

siguiente (nC1,nC2,&nSigC1,&nSigC2);rSig = f (nSigC1,nSigC2);r = combina (nC1,nC2,rSig);

}return r;

}…

entrada salida


Mcd.c…logico esCasoBase( int nC1, int nC2){

return nC2 == 0;}int solucionBase( int nC1, int nC2){

return nC1;}


}void siguiente( int nC1, int nC2, int * nSigC1, int * nSigC2){

*nSigC1 = nC2;*nSigC2 = nC1%nC2;

}int combina( int nC1, int nC2, int rSig){

return rSig;}

Parámetros de entrada salida


Ppal.c#include <stdio.h>#include "mcd.h"

void main ( void ) {int nC1,nC2; int r;printf ("Introduzca los valores para la entrada: ");


printf ("Introduzca los valores para la entrada: ");scanf ("%d %d", &nC1, &nC2); r = f (nC1,nC2);printf ("El resultado de la función recursiva es %d", r);

}



int nC1, nC2;

int r;

printf ("Introduzca los valores para la entrada: ");

scanf ("%d %d", &nC1, &nC2);

r = mcdRec(nC1,nC2);



r = mcdRec(nC1,nC2);

}

int mcdRec( int nC1, int nC2){

int r;

if (nC2 == 0) {

r = nC1;

}

else {

int nSigC1 = nC2;

int nSigC2 = nC1%nC2;

r = mcdRec(nSigC1, nSigC2);

}

return r;

}

4. Recursividad Múltiple


Recursividad Múltiple

� Como se ha comentado anteriormente, la recursividad múltiple sepuede representar gráficamente mediante un árbol binario dondecada nodo representa una llamada recursiva y tiene dos parámetros,n y r. En este caso es necesario definir funciones similares a las quese han definido para la recursividad lineal, con la diferencia de queahora se necesitan dos funciones siguientes (ya que hay dos

34

ahora se necesitan dos funciones siguientes (ya que hay dosllamadas recursivas) que establezcan las llamadas recursivas.

� Definición recursiva del número de Fibonacci:

si 0 1( )

( 1) ( 2) si 1

n nfib n

fib n fib n n

≤ ≤= − + − > Caso Recursivo

Caso Base


� Representación gráfica del cálculo de fib(4),

4, r

3, r1


2, r2

1, r4



4, r

3, r1


2, r2

1, 1 0, r5



4, r

3, r1


2, r2

1, 1 0, 0



4, r

3, r1


2, 1

1, 1 0, 0



4, r

3, r1


2, 1 1, r3

1, 1 0, 0



4, r

3, r1


2, 1 1, 1

1, 1 0, 0



4, r

3, 2


2, 1 1, 1

1, 1 0, 0



4, r

3, 2 2, r6


2, 1 1, 1

1, 1 0, 0

1, r7



4, r

3, 2 2, r6


2, 1 1, 1

1, 1 0, 0

1, 1



4, r

3, 2 2, r6


2, 1 1, 1

1, 1 0, 0

1, 1 0, r8



4, r

3, 2 2, r6


2, 1 1, 1

1, 1 0, 0

1, 1 0, 0



4, r

3, 2 2, 1


2, 1 1, 1

1, 1 0, 0

1, 1 0, 0



4, 3

3, 2 2, 1


2, 1 1, 1

1, 1 0, 0

1, 1 0, 0



4, 3

3, 2 2, 1

sig1 sig2


2, 1 1, 1

1, 1 0, 0

1, 1 0, 0

sig2sig1 sig2 sig1

sig2sig1


RecMultiple.h

typedef enum{false, true} logico;T2 f( T1 n);logico esCasoBase( T1 n);T2 solucionBase( T1 n);T1 sig1( T1 n);




T1 sig1( T1 n);T1 sig2( T1 n);T2 combina( T1 n, T2 r1, T2 r2);


prototipos.


RecMultiple.c#include “RecMultiple.h”

// Esquema general para cualquier problema Rec Múlt iple (común)

T2 f( T1 n) { T2 r;if (esCasoBase(n)) {

r = solucionBase(n);}



}else {

T1 nSig1 = sig1(n);T2 r1 = f(nSig1);T1 nSig2 = sig2(n);T2 r2 = f(nSig2);r = combina(n, r1, r2);

}return r;

}

…


Recursividad MúltipleRecMultiple.c

…



…

}


…



…

}

T1 sig1( T1 n) {

…

}

T1 sig2( T1 n) {

…

}

T2 combina( T1 n, T2 r1, T2 r2){

…

}


Recursividad Multiple


#include “RecMultiple.h”


T1 n;

Para resolver un problema concreto, en el archivo “.c” T1 será reemplazado por el tipo del parámetro de entrada, mientras T2 por el tipo del parámetro de salida.


T2 r;


scanf (“%efT1”, &n);

r = f (n);

printf (“El resultado de la función recursiva para la entrada %efT1 es %efT2”,n,r);

} Especificadores de formato: %c carácter %d int%ld long %f float%lf double %s cadena de carácteres

Ejemplo Rec Múltiple: Fibonacci

Fibonacci.h

typedef enum{false, true} logico;int f (int n);logico esCasoBase (int n);int solucionBase (int n);int sig1 (int n);


int sig1 (int n);int sig2 (int n);int combina (int n, int r1 , int r2 );


Fibonacci.c#include “Fibonacci.h”

// Esquema general para cualquier problema Rec Múlt iple (común)

int f (int n) {

int r;


r = solucionBase (n);



}

else {

int nSig1 = sig1 (n);

int r1 = f (nSig1);

int nSig2 = sig2 (n);

int r2 = f (nSig2);

r = combina (n, r1, r2);

}

return r;

} …

Ejemplo Rec Múltiple: FibonacciFibonacci.c

…

logico esCasoBase (int n) {

return (n == 0 || n == 1);

}

int solucionBase (int n) {

return n;

}


}

int sig1 (int n) {

return n - 1;

}

int sig2 (int n) {

return n - 2;

}

int combina (int n, int r1 , int r2 ){

return r1 + r2;

}



#include “Fibonacci.h”

void main (void) {

int n;

int


int r;

printf ("Introduzca el valor para la entrada: ");

scanf ("%d", &n);

r = f (n);

printf ("El resultado de la funcion recursiva es %d",r);

}


void main (void) {

int n;

int r;

printf ("Introduzca el valor para la entrada: ");

scanf ("%d", &n);

r = fibRec (n);



r = fibRec (n);

printf ("El resultado de la funcion recursiva es %d",r);

}

int fibRec (int n){

int r;

if (n == 0 || n == 1) {

r = n;

}

else {

r = fibRec (n-1) + fibRec (n-2);

}

return r;

}

5. Transformación Recursivo 5. Transformación Recursivo Iterativo


Transformación Recursivo-Iterativo

� Calcular iterativamente un valor definido de formarecursiva consiste en:� En el caso de la recursividad final, iterar hacia delante hasta

llegar al caso base.� En el caso de la recursividad no final, iterar dos veces, primero

hacia delante (hasta llegar al caso base y obtener el resultado


hacia delante (hasta llegar al caso base y obtener el resultadobase) y después hacia atrás (combinando para obtener elresultado requerido).

Iteración Lineal Final

IterLinealFinal.h





T1 siguiente (T1 n);



IterLinealFinal.c#include “IterLinealFinal.h”

// Esquema general para cualquier problema Iter Lin eal Final

T2 f( T1 n) {

T2 r;

while (! esCasoBase (n)) {

n = siguiente (n);



}


return r;

}

…



IterLinealFinal.c…



…

}





…

}


…

}


Iteración Lineal No Final

� En el caso de la recursividad no final, es necesariodefinir un método anterior mediante el cual se vayanrecuperando los problemas en el orden inverso al que sehan ido generando.

� El método anterior debe ser el inverso del métodosiguiente .


siguiente .� A veces el inverso de una función matemática es muy

difícil de calcular e incluso imposible. Pero siempre esposible implementar adecuadamente el método anteriormediante una pila.


IterLinealNoFinal.h





T1 siguiente (T1 n); T1 anterior (T1 n); T2 combina (T1 n, T2 rSig );


prototipos.


IterLinealNoFinal.c#include “IterLinealNoFinal.h”

// Esquema general para cualquier problema Iter Lin eal No Final

T2 f( T1 n) { T1 nsig = n; // inicia();T2 r;while (! esCasoBase (nsig)) {

nsig = siguiente (nsig);



nsig = siguiente (nsig);}r = solucionBase (nsig); while (n != nsig) {

nsig = anterior (nsig); r = combina (nsig, r);

}return r;

}

…



IterLinealNoFinal.c…



…

}




…

}


…

}

T1 anterior( T1 n) {

…

}

T2 combina( T1 n, T2 rSig){

…

}


Recursividad múltiple e Iteraciones

� No hay métodos para transformar la recursividad múltiple eniteración.

� Esto sí es posible en el caso de ecuaciones de recurrencia.Para ello, los casos bases deben estar claramenteidentificados, y ser independientes del problema de entrada.Ejemplos: Factorial, Fibonacci. Contraejemplo: MáximoEjemplos: Factorial, Fibonacci. Contraejemplo: MáximoComún Divisor.

� Se trata de ir acumulando en una o más variables losvalores adecuados, de forma que se vaya actualizando elestado del algoritmo.

� Inicialmente, es necesario inicializar correctamente lasvariables que forman parte del estado del algoritmo.


Recursividad múltiple e Iteraciones

int fib( int n){

int a, b, a1, b1, n1;

if (n == 0 || n == 1) { return n; }

else {

n1 = 2;

a = 1; // Fib(n1)

b = 1; // Fib(n1 - 1)

Si es caso base, devuelve la solución para dicho valor .

Inicialización del estado.

Itera hasta que se alcanza while (n1 < n) {//Fin cuando n1 == n

a1 = a;

b1 = b;

a = a1 + b1;

b = a1;

n1 = n1 + 1;

}

}

return a; // a = Fib(n1) = Fib(n)

}


Itera hasta que se alcanza el problema inicial.

Actualiza el estado combinando los valores.

6. Ejercicios


6. Ejercicios

Ejercicios

� Para resolver cualquier problema recursivo mediante lasdistintas propuestas estudiadas, es importante identificar:� Cuándo estamos ante un caso base� Cuál es la solución para los casos base� Transformación a realizar en los datos de entrada para� Transformación a realizar en los datos de entrada para

realizar la/s llamada/s recursiva/s (métodos siguiente, sig1,sig2).

� Combinación del resultado de la llamada recursiva juntocon los datos de entrada actuales (combina)

� Si es posible, el inverso a siguiente (anterior)


Ejercicios

1. Cálculo de la n-ésima potencia de un número

1

1 si 0

si 0n

n

nx

x x n−

== ⋅ >


1 si 0nxx x n−= ⋅ >

Ejercicios

2. Potencia entera

2

1 si 0( , )

( , ) ( ( , / 2)) si 0

npot a n

cnd a n pot a n n

== ⋅ >

donde


1 si es par ( , )

si es impar

ncnd a n

a n

=

donde

Ejercicios

3. Suma Recursiva: A partir de un array de elementosenteros, calcular la suma de todos los componentesde dicho array.� El array “a” se puede declarar como variable global de forma

que no haya que pasarla como parámetro en cada llamada.

� El índice “i” indica los elementos del array que ya han sido


� El índice “i” indica los elementos del array que ya han sidosumados, de forma que sum(i) devuelve la suma de loselementos desde a[0] hasta a[i].

[ ] si i 0( )

[ ] ( 1) si i > 0

a isum i

a i sum i

== + −

Ejercicios

4. Calcular una cadena con la representación en binario deun entero, donde + representa la concatenación decadenas:

"" si 0( )

nbinario n

==


( )( / 2) ( ) si 0

binario nbinario n cnd n n

= + >

"0" si es par ( )

"1" si es impar

ncnd n

n

=

donde

Ejercicios

5. Calcular una cadena con la representación en binario de un entero, donde + representa la concatenación de cadenas:

si 0( , )

w nbinario n w

== >


( , )( / 2, ( , ) si 0

binario n wbinario n cnd n w n

= >

"0" si es par ( )

"1" si es impar

w ncnd n

w n

+= +

donde

Ejercicios

6. Algoritmo de Euclides para el cálculo del máximocomún divisor:

si 0( , )

( , mod ) si b 0

a bmcd a b

mcd b a b

== >


( , mod ) si b 0mcd b a b >

Ejercicios

7. Combinaciones sin repetición de n objetos tomados dek en k: nc(n,k)

nc(n,k) 1

0 si k > n

si k = 0 ó k = n


nc(n,k) 1

nc(n – 1, k) + nc(n - 1, k - 1)

si k = 0 ó k = n

en otro caso

Ejercicios

8. Cálculo de los números de Fibonacci:

si 0 1( )

( 1) ( 2) si 1

n nfib n

fib n fib n n

≤ ≤= − + − >


( 1) ( 2) si 1fib n fib n n − + − >

Tema 1. Recursividad - us

Documents

Transcript of Tema 1. Recursividad - us