Comptage des appels récursifs à la main

Question

Nouvel étudiant CS, étudiant pour une finale. J'essaie de comprendre combien de fois une méthode récursive sera appelée en général. Ajouté le code comme un exemple. Si je saisis abcd et efgh, combien d'appels basés sur la taille des chaînes? Si n est une taille de données, le nombre d'appels est n (?) Dans n'importe quelle méthode récursive.

public static String interweave(String s1, String s2) 
{ 
    if (s1.equals("")) return s2; 
    else if (s2.equals("")) return s1; 
    else return "" + interweave(s1.substring(0,s1.length()-1), s2.substring(0,s2.length()-1)) 
     +s1.charAt(s1.length()-1)+s2.charAt(s2.length()-1); 
} 

Answer 1

Notez que dans votre question, à chaque étape récursive vous réduisez par une la taille des deux chaînes jusqu'à ce que l'un d'entre eux a une longueur zéro (cas de base de la récursivité). Il est facile de voir que le nombre d'appels récursifs est min(m, n) + 1, où m est la longueur initiale de s1 et n est la longueur initiale de s2.

Par exemple, si s1 = "abc" et s2 = "de" il faudra 2 appels récursives à travers s2 (la chaîne avec la longueur minimum) plus un appel supplémentaire pour sortir du cas de base, donc min(s1.length(), s2.length()) + 1 == 3. Vous pouvez le tester par programme comme celui-ci:

static int counter; 

public static String interweave(String s1, String s2) { 
    counter++; 
    if (s1.equals("")) 
     return s2; 
    else if (s2.equals("")) 
     return s1; 
    else 
     return interweave(s1.substring(0, s1.length()-1), s2.substring(0, s2.length()-1)) 
     + s1.charAt(s1.length()-1)+s2.charAt(s2.length()-1); 
} 

public static int count(String s1, String s2) { 
    counter = 0; 
    interweave(s1, s2); 
    return counter; 
} 

Maintenant, lorsque vous exécutez les instructions suivantes, la formule fonctionne comme prévu:

// s1.length() == s2.length() 
System.out.println(count("abcde", "fghij")); 
> 6 

// s1.length() > s2.length() 
System.out.println(count("abcde", "fg")); 
> 3 

// s1.length() < s2.length() 
System.out.println(count("ab", "cdefg")); 
> 3 

Answer 2

Les caractères ne signifient rien que la longueur. Vous pouvez convertir à un problème numérique comme suit:

public static String interweave(int s1, int s2) 
{ 
    if (s1 == 0) return s2; 
    else if (s2 == 0) return s1; 
    else return interweave(s1-1, s2-1)+2; 
}