The ninth class 63:Recursion 递归

The tenth class 64:Data Protection, Ethics and Professional issues 数据保护、道德及专业问题

63.Recursion

递归 一般会考一道大题
Algorithms Design Techniques
没什么知识点，这里用大量题目显示递归的作用。
核心是：用方法，执行一次实现一次循环。 
public static long fact(int n) { 
if (n == 0) 
return 1; 
else 
return fact(n-1) * n; 
}
课程里有提问：斐波那契数列的递归实现 
public class Fibonacci {
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
    public static void main(String[] args) {
       Scanner n = new Scanner(System.in); 
       String next = n.nextLine(); 
       int num=Integer.parseInt(next);
            System.out.print(fibonacci(num)+"\n");
    }
}

字符串拼接 Ex12.1

Complete the method numXY.
It finds the number of times the string "XY" appears in the input string recursively.
You must not use any loops or regular expressions.
For example:                                                                    
TestResult
System.out.println(numXY("AAXYAA"));1
System.out.println(numXY("AXYBXYAA"));2
代替loop的作用
public class XYCounter {
    public static void main(String[] args) {
       System.out.println(numXY("AAXYAA"));
System.out.println(numXY("AXYBXYAA"));
    }
public static int numXY(String input) {
    if (input.length() < 2) {
            return 0;
        } else if (input.startsWith("XY")) {
            return 1 + numXY(input.substring(2));
        } else {
            return numXY(input.substring(1));
        }
}
}

Ex12.2

Complete the method remDup.
It reduces all adjacent same characters that appear in the input string to a single character recursively.
You must not use any loops or regular expressions.
For example:                                                                    
TestResult
System.out.println(remDup("hello"));helo
System.out.println(remDup("abbbcd"));abcd
 
public class StringManipulator {
    public static void main(String[] args) {
        // Test cases  
        System.out.println(remDup("hello"));   // Output: helo  
        System.out.println(remDup("abbbcd"));  // Output: abcd  
    }
public static String remDup(String input) {
        if (input.length() <= 1) {
            return input;
        } else if (input.charAt(0) == input.charAt(1)) {
// If the current character is the same as the next one, skip the current character  
            return remDup(input.substring(1));
        } else {
// If the current character is different from the next one, keep the current character  
            return input.charAt(0) + remDup(input.substring(1));
        }
}

Review charAt&substring

23/24期末考试问题：输入一个字符串，请你写一个递归，检验字符串是否都是大写字母。
字符串问题就一定要用到charAt&substring以及string.equals这类的判断。 charAt(0)
str.charAt(0)检索str中的第一个字符str.charAt(n)检索str中的第n-1个字符 subString常用方法一：
String a = “123456anbdc”;
String b = a.subString(1);
此时得到的为字符串a从下标为1的位置开始截取到最后的值，也就是23456anbdc； subString常用方法二：
String a = “123456anbdc”;
String b = a.subString(1，5);
此时得到的为字符串a从下标为1的位置开始截取到下标为5的位置的值（不包括下标为5的值），也就是2345；

Ex12.3

与12.2几乎完全相同
Complete the method sepStar.
It separates all identical adjacent characters that appear in the input string from each other by "*" recursively.
You must not use any loops or regular expressions.
                                                                   
TestResult
System.out.println(remDup("hello"));hel*lo
System.out.println(sepStar("uuvxxyzzz"));u*uvx*xyz*z*z
 
public class EX123 {
public static void main(String[] args) {
        // Test cases  
        System.out.println(sepStar("hello"));   // Output: hel*lo  
        System.out.println(sepStar("uuvxxyzzz"));  // Output:u*uvx*xyz*z*z   
        }
public static String sepStar(String input) {
        if (input.length() <= 1) {
            return input;
        } else if (input.charAt(0) == input.charAt(1)) {
// If the current character is the same as the next one, skip the current character  
            return input.charAt(0)+"*"+sepStar(input.substring(1));
        } else {
// If the current character is different from the next one, keep the current character  
            return input.charAt(0) + sepStar(input.substring(1));
        }
}
}

EX12.4 2019 Final Exam

Complete the helper method smallest. It finds the smallest integer in an integer array recursively. You may assume that input array has at least one element in it You must not use any loops or regular expressions. Test cases: smallest([10, 5, 7, 9]) → 5 For example:                                                
TestResult
int[] arr1 = {10, 5, 7, 9}; System.out.println(smallest(arr1));5
 
// Exercise #12.4 Recursive Smallest Integer  
public class EX124 {
public static void main(String[] args) {
       int[] arr1 = {10, 5, 7, 9};
System.out.println(smallest(arr1));
    }
// Appear in FINAL EXAM 2019    
  public static int smallest(int[] array) {
        return smallest(array, 0);
    }
    private static int smallest(int[] array, int start) {
// Base case: If there's only one element left in the array, return that element  
        if (start == array.length - 1) {
            return array[start];
        }
// Recursive step: Find the smallest element in the rest of the array  
        int smallestRest = smallest(array, start + 1);
// Compare the smallest element in the rest with the current element  
        if (array[start] < smallestRest) {
// If the current element is smaller, return it  
            return array[start];
        } else {
// If the smallest in the rest is smaller, return that  
            return smallestRest;
        }
}
}

CW12

Complete the helper method replaceOddZeroHelper. It replaces all odd numbers with zero in the input integer list recursively. You must not use any loops or regular expressions. The imported libraries are Arrays and List. For example:                                                
TestResult
List list = Arrays.asList(1, 2, 3, 4, 5); replaceOddZero(list); System.out.println(list);0, 2, 0, 4, 0
 
// CW1 12.1 Recursive Replace Odd with Zero  
public class cw12{
public static void main(String[] args) {
List list = Arrays.asList(1, 2, 3, 4, 5);
replaceOddZero(list);
System.out.println(list);
}
public static void replaceOddZero(List list) {
    replaceOddZeroHelper(list, 0);
}
private static void replaceOddZeroHelper(List list, int start) {
    // Base case  
    if (start>=list.size()){
            return;
        }
        if (list.get(start) % 2 != 0){
            list.set(start,0);
        }
        replaceOddZeroHelper(list,start+1);
    // Recursive step    
}
这里都用了一个List+一个int来处理，一个负责改变输出，一个负责记录位置。

64.Data Protection, Ethics and Professional issues

能进行一些常识判断即可
提示一下：非常识知识点
GDPR
7 princple
一般只考一题选择。
>>这里是课件<<
>>返回总目录<<