<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">import java.util.*;
/** Demo the development of recursive methods */
public class D {
    /** An implict precondition of all String parameters is that they are not null. */
    
    /** = the length of s --without using function s.length. */
    public static int len(String s) {
        if (s.equals("")) return 0;
        
        // s has at least 1 char   s[0] + s[1..]
        // length of s is 1 + length of s[1..]
        
        return 1 + len(s.substring(1));
    }
    
    /** = number of the digits in the decimal representation of n.
      e.g. numDigits(0) = 1, numDigits(3) = 1, numDigits(34) = 2. 
      numDigits(1356) = 4.
      Precondition: n &gt;= 0. */
    public static int numDigits(int n) {
        
        if (n &lt; 10) return 1;
        
        // n has at least 2 digits
        // number of digits in n is 1 + number of digits in (n/10)
        return 1 + numDigits(n/10);
    }
    
    /** = a copy of s with adjacent duplicates removed.
      Example: for s = "abbcccdeaaa", the answer is "abcdea".*/
    public static String rem1(String s) {
        if (s.length() &lt;= 1) return s;
        
        // s is  s[0] + s[1] + s[2..]
        
        if (s.charAt(0) == s.charAt(1)) {
            // s with dups removed  is  s[1..] with dups removed
            return rem1(s.substring(1));
        }
        
        // answer is s[0] + (s[1..] with dups removed) 
        return s.charAt(0) + rem1(s.substring(1));
    }
    
    /** = s with every char duplicated. */
    public static String dup(String s) {
        return  "";
    }
    
    /** = "s is a palindrome" --reads the same backward and forward. */
    public static boolean isPal(String s) {
        if (s.length() &lt;= 1) return true;
        
        // s has at least 2 chars
        //  s has the form  char1 + string + char2
        // char1 + string + char2  is a pal. when char1 = char2 AND string is a pal
        int n= s.length() -1;
        return s.charAt(0) == s.charAt(n)  &amp;&amp;  D.isPal(s.substring(1,n));
    }
    
    
    /** = the reverse of s */
    public static String rev(String s) {
        return "";
    }
    
    /** = b^c. Precondition c &gt;= 0.
      Properties: b^0 = 0.
      b^c = b*b^(c-1)  for c &gt; 0.
      b^c = (b*b)^(c/2) for even c. 
      3*8 = 3*3*3*3*3*3*3*3 =  (3*3) * (3*3) * (3*3) * (3*3)  = (3*3)^4*/
    public static double exp(double b, int c) {
        if (c == 0) return 1;
        if (c%2 == 0) return exp(b*b, c/2);
        return b* exp(b, c-1);
    }
    
    /** = the permutations of s.
      e.g. the permutations of "abc" are 
      "abc", "acb", "bac", "bca", "cab", "cba"
      Precondition: the chars of s are all different.*/
    public static ArrayList&lt;String&gt; perms(String s) {
        ArrayList&lt;String&gt; ans= new ArrayList&lt;String&gt;();
        if (s.length() &lt;= 1) {
            ans.add(s);
            return ans;
        }
        
        // s has at least 2 chars. The answer is 
        // the permutations of s[1..], each with s[0] put in all
        // possible places --before a[0], a[1], ..., after the last
        // e.g. for s = "abc" for each permutation of "bc" produce
        // 3 permutations by putting 'a' before the first, after the first,
        // and after the second char.
        ArrayList&lt;String&gt; rest= perms(s.substring(1));
        for (String r : rest) {
            for (int k= 0; k &lt;= r.length(); k= k+1) {
                ans.add(r.substring(0,k) + s.charAt(0) + r.substring(k));
            }
        }
        return ans;
    }
    
}</pre></body></html>