Recursión Directa Una función es de recursión directa si contiene una llamada explícita a si misma int foo (int x) { if ( x 1 if (n & 1) return elevar_aux(x*prod, x*x, n >> 1); // n/2 else return elevar_aux( prod, x*x, n >> 1); // n/2 } int elevar(int x, int n) { return elevar_aux(1, x, n); // recursion de cola } CI-2126 V. Theoktisto 38

Recursión lineal Una función recursiva se dice “linealmente recursiva” cuando no hay una operación pendiente adicional que invoque otra llamada recursiva a la función.

int factorial (int n) { if (n == 0) return 1; return n * factorial ( n – 1); } CI-2126 V. Theoktisto 39

Count_reps es Lineal Recursivo // Cuenta cuantas veces está repetido un valor int count_reps(int array[ ], int n, int value) { if (n == 0) return 0; if (array[n-1] != value) { return ( count_reps(array, n-1, value ) ); } return ( 1 + count_reps(array, n-1, value) ); } CI-2126 V. Theoktisto 40

Count_reps es Lineal Recursivo // Versión con Recursión de cola int count_reps_aux(int sum, int array[ ], int n, int value) { if (n == 0) return sum; return count_reps_aux(sum + (array[n-1] == value), array, n-1, value); } int count_reps(int array[ ], int n, int value) { return ( count_reps_aux(0, array, n-1, value); }

CI-2126 V. Theoktisto 41

Recursión No Lineal Una función recursiva se dice no-lineal recursiva o con recursión de árbol si la operación pendiente involucra otra llamada recursive a la función. La función de Fibonacci fib provee un ejemplo clásico de recursión de árbol.

CI-2126 V. Theoktisto 42

Secuencia de Fibonacci Los números de Fibonacci se definen recursivamente por reglas :

si n = 0 0,  Fib(n) = 1, si n = 1  Fib(n − 1 ) + Fib(n − 2 ) si n > 1  Por ejemplo, los primeros SIETE números de Fibonacci son Fib(0) = 0 Fib(1) = 1 Fib(2) = Fib(1) + Fib(0) = 1 Fib(3) = Fib(2) + Fib(1) = 2 Fib(4) = Fib(3) + Fib(2) = 3 Fib(5) = Fib(4) + Fib(3) = 5 Fib(6) = Fib(5) + Fib(4) = 8 CI-2126 V. Theoktisto 43

Fibonacci con Recursión de árbol // Notar como la operación pendiente (el +) // necesita una 2nd recursiva para llamar a la FIB int fibonacci(int n) { _pre( !(n < 0) ); if (n < 2) return n; else return fibonacci1(n - 1) + fibonacci1(n - 2); } CI-2126 V. Theoktisto 44

Count_reps con Recursión de árbol int count_reps (int array[ ], int low, int high, int value) { if ((low > high) or (low == high and array[low] != value)) { return 0 ; } if ((low == high) and array[low] == value) { return 1; } return (count_reps(array, low, (low + high)/2) + count_reps (array, 1 + (low + high)/2, high)) ); } CI-2126 V. Theoktisto 45

Fibonacci con recursión de Cola int fibo_aux(int f0, int f1, int n) { if (n == 1) return f1; return fibo_aux(f1, f0 + f1, n - 1); } int fibonacci(int n) { _pre( !(n < 0) ); if (n == 0) return 0; return fibo_aux(0, 1, n); } CI-2126 V. Theoktisto 46

En General, la forma de una función recursiva de cola es: Asumimos que la podemos exponer de esta forma F(x){ if ( P( x ) ) return G( x ); return F ( H( x ) ); } CI-2126 V. Theoktisto 47

Un ejercicio para la clase Convertir este for loop para que sea de recursión de cola. Calcula el máximo de un arreglo como de recursión de cola. int nums[MAX]; // Otra función lo rellena int max_num = nums[ 0 ]; for (j = 0; j < MAX; j++) max_num = max (max_num, nums[ j ] );

CI-2126 V. Theoktisto 48