[C con Clase] Recursividad y static

[Steven Davidson]

Hola Alejandro,

El pasado 2007-03-17 17:06:02, Alejandro escribió:

A> Os comento un par de dudas sobre static y la recursividad que tengo:
A> 1. ¿Es muy importante lo de la recusividad? Es que ese tema me cuesta...

Es normal que te cueste entender este concepto, especialmente si es la primera vez que lo ves. La recursividad o recurrencia es una forma de implementar el concepto de relaciones recurrentes en las matemáticas. Por ejemplo,

n! = n*(n-1)!  donde n >= 0, y se define 0! = 1! = 1

Es más fácil implementar esta definición con recursividad o recurrencia en C/C++. Esto sería,

unsigned int factorial( unsigned int n )
{
  return n < 2 ? 1 : factorial(n-1);
}

Por supuesto, podemos redefinir la función para que sea iterativa y así no tenemos que usar recursividad. Esto siempre es posible, pero existen ciertos casos que tienden más a la recurrencia que a la iteración. Esto es porque es mucho más fácil establecer una definición recurrente que una iterativa. El típico ejemplo y ejercicio de recursividad es resolver el problema de las Torres de Hanoi. Se puede implementar una versión iterativa, pero es algo más difícil de definir que la versión recurrente.

Ahora bien, a nivel de recursos, la recursividad requiere más memoria y tiempo de ejecución, por lo que la mayoría de las ocasiones los diseñadores tienden más hacia la iteración. Por ello, hay que tener cuidado con usar recursividad o iteración. Por ejemplo, ciertos textos muestran equivocadamente como un ejemplo de recursividad implementar la función que elige un valor en la secuencia de Fibonacci. Esto no es un buen ejemplo de usar recursividad porque es completamente ineficiente. Una posible implementación podría ser la siguiente:

unsigned int fibonacci( unsigned int N )
{
  return N < 2 ? N : fibonacci(N-1) + fibonacci(N-2);
}

Esto es ineficiente porque estamos calculando fibonacci(N-2) dos veces por iteración, ya que lo volvemos a calcular bajo fibonacci(N-1).

Por último, bajo otros lenguajes, no existe la iteración, sino exclusivamente la recursividad, por lo que es recomendable aprender ambas técnicas.


Espero haber aclarado la inquietud.

Steven