Manual del estudiante de Ingeniería en Sistemas de UTN/Diseño e Implementación de Estructuras de Datos/Guías prácticas/Recursividad/Solución al ejercicio 4 de recursividad

De Wikilibros, la colección de libros de texto de contenido libre.
1.
 import java.util.Vector;

 public class StringGenerator {
   
   private void generateR(String source, String partial,Vector out)
   {
     String newPartial=new String(partial);
     String newSource;
     if (source.length()==0)
     {
       out.addElement(newPartial);
       return;
     }
     for(int i=0;i<source.length();i++)
     {
       newPartial=partial.concat(source.substring(i,i+1));
       newSource=source.substring(0,i);
       if (i<(source.length()+1))
         newSource=newSource.concat(source.substring(i+1,source.length()));
       generateR(newSource, newPartial, out);
     }
   }
   
   public Vector generate(String source)
   {
     Vector out=new Vector();
     String partial=new String();
     generateR(source, partial, out);
     return out;
   }

   public static void main(String[] args)
   {
     StringGenerator a= new StringGenerator();
     Vector v=a.generate("Chau");
     for(int i=0;i<v.size();i++)
     {
       System.out.print((String)v.elementAt(i));
       System.out.print(", ");
     }      
   }
 }
2.

En el primer nivel, el algoritmo abre n-1 hijos, en el segundo, n-2, y así sucesivamente.

Si se mira de atrás hacia adelante, se verá que los términos corresponden primero a , y a medida que nos movemos a la izquierda, se le va quitando un término a , hasta llegar a , lo que podemos representar como:

Si denominamos a la serie vista alrevés

Para demostrar que el orden de la complejidad de este algoritmo es de , deberíamos demostrar que es una constante.

La serie de potencias:

tiene radio de convergencia infinito, de manera que


De manera que k converge y es menor que e, con lo que queda demostrado que