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

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.

$C_{n}=n+n(n-1)+n(n-1)(n-2)+\cdots +n(n-1)(n-2)\cdots (2)(1)$

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

$C_{n}={\frac {n!}{(n-1)!}}+{\frac {n!}{(n-2)!}}+{\frac {n!}{(n-3)!}}+\cdots +{\frac {n!}{1!}}$

$C_{n}=n!({\frac {1}{(n-1)!}}+{\frac {1}{(n-2)!}}+{\frac {1}{(n-3)!}}+\cdots +{\frac {1}{1!}})$

Si denominamos $k$ a la serie vista alrevés

$k={\frac {1}{1!}}+{\frac {1}{2!}}+\cdots +{\frac {1}{(n-2)!}}+{\frac {1}{(n-1)!}}$

$C_{n}=n!k$

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

La serie de potencias:

$e^{x}=\sum _{i=0}^{\infty }{\frac {x^{i}}{i!}}$

tiene radio de convergencia infinito, de manera que

$e^{1}=\sum _{i=0}^{\infty }{\frac {1^{i}}{i!}}=1+1+{\frac {1}{2!}}+\cdots +{\frac {1}{(n-2)!}}+{\frac {1}{(n-1)!}}+{\frac {1}{(n)!}}+{\frac {1}{(n+1)!}}+\cdots$

$e=\sum _{i=0}^{\infty }{\frac {1^{i}}{i!}}=1+k+{\frac {1}{(n)!}}+{\frac {1}{(n+1)!}}+\cdots$

$k=e-1-{\frac {1}{(n)!}}+{\frac {1}{(n+1)!}}+\cdots$

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

$C_{n}=O(n!)$