Serie de Fibonacci usando función recursiva

La implementación de la serie de Fibonacci en Java es una pregunta frecuente durante una entrevista de nivel más nuevo. Además, es un ejemplo muy famoso para mostrar cómo usar la función recursiva en Java.

Índice
  1. Enfoque recursivo
  2. Enfoque dinámico

Enfoque recursivo

public class Fibonacci {

	public static void main(String[] args) {
		fibonacci(10);
	}

	/**
	 * print fibonacci series from 0 to n
	 * @param n
	 */
	private static void fibonacci(int n) {
		for (int i = 0; i <= n; i++) {
			System.out.print(fib(i) + ", ");
		}
	}

	/**
	 * Recursive approach f(n) = f(n-1) + f(n-2)
	 * @param n
	 * @return
	 */
	public static int fib(int n) {
		if (n <= 1) {
			return n;
		}
		return fib(n - 1) + fib(n - 2);
	}
}

Output

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,

La complejidad del tiempo de aproximación recursiva es aproximadamente 𝘖(2ⁿ)

Enfoque dinámico

Podemos usar un enfoque dinámico para la complejidad del tiempo lineal, es decir 𝘖(n)

public static int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    int[] fib = new int[n + 1];
    fib[0] = 0;
    fib[1] = 1;
    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    return fib[n];
}

Si quieres conocer otros artículos parecidos a Serie de Fibonacci usando función recursiva puedes visitar la categoría Tutoriales.

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Subir

Esta página web utiliza cookies para analizar de forma anónima y estadística el uso que haces de la web, mejorar los contenidos y tu experiencia de navegación. Para más información accede a la Política de Cookies . Ver mas