4-9:
题目：写一个简短的递归程序，用于在不使用任何循环的条件下查找一个序列中的最小值和最大值。
这一题和做天的第一题很像，但是这一题要求返回两个值，最大和最小，我们不应该写两个程序来分别找最大和最小值，如果这样就与昨天重复了，也不符合程序要求。
所以我们在递归时直接返回两个值，递归的基本情况是当序列只有一个元素时，最大最小都是哪一个元素；递归情况是，max(前n-1个元素的最大值，第n个元素)、min(前n-1个元素的最小值，第n个元素)
跟据这两个定义就可以写出程序：
def max_min_in_s(s, n):
if len(s) == 0:
return None
if n ==0:
return s[0], s[0]
s_max, s_min = max_min_in_s(s, n-1)
if s_max < s[n]:
s_max = s[n]
if s_min > s[n]:
s_min = s[n]
return s_max, s_min
s = [1, 3, 4, 55, 6, 7, 8, 3, 10]
print(max_min_in_s(s, len(s)-1))
注意输入的n是s的最后一个元素的索引！
输出：
这个算法不像之前一样只返回一个值，而是返回以个元组，这样可以只用线性递归就可以的出结果。
4-10
题目：在只使用加法和整数除法的情况下，描述一个递归算法，来计算以2为底的n的对数的整数部分。
刚拿到的时候我懵了一镇，后来想想也就那样。原版答案提示是这样说的：
The integer part of the base-two logarithm of n is the number of times you can divide by two before you get a number less than 2.
这一说就太明白了，在你得到一个小于2的数之前，你能把n除以2几次，这个值便是对数的整数部分。
import time
def log_2_n(n):
if n == 1:
return 0
if n < 1:
return log_2_n(n*2) + 1
else:
return log_2_n(n//2) + 1
start_time = time.time()
t = log_2_n(2**997+11111)
print(t)
end_time = time.time()
print(start_time)
print(end_time)
print(end_time-start_time)
我多试了几组，最后试的是默认最大递归深度，但是丝毫不影响我们程序的速度。
结果：
递归，有的人恨它，有的人爱它，还有的人恨着恨着就爱上了。
我是第二种人，一直很爱。
4-11
题目：描述以个有效的递归算法，来求解序列唯一性的问题，不使用排序，算法的时间复杂度对多为O(n^2)。
这一题就比较好玩，我下午上课写的。在复制序列这一步我觉得还可以改进，因为复制字符串就已经是O(n)了，所以算上递归最后还是O(n^2).
算法的思想是：当序列只有一个元素的时候，序列元素一定是唯一的；当序列元素大于1的时候：只要最后的第n个元素不与前n-1项元素重复，且前n-1项元素是唯一的，这时候，这n个元素的序列元素具有唯一性。
def element_unique(s, n):
if len(s) == 0:
return None
if n == 0:
return True
return s[n] not in s[0:n] and element_unique(s, n-1)
s1 = [1, 2, 3, 4, 5, 6, 7, 8, 9]
s2 = [1, 2, 3, 4, 5, 6, 7, 8, 8]
print('s1序列元素唯一', element_unique(s1, len(s1)-1))
print('s2序列元素唯一', element_unique(s2, len(s2)-1))
这里要注意的就是返回的那一句return s[n] not in s[0:n] and element_unique(s, n-1),这里利用了and逻辑与的短路保护机制，当出现重复元素，也就是s[n] not in s[0:n]为假，根据逻辑与的性质，后面的递归就不用判断了，直接返回了，节省了大量时间。
结果：
哎呀，我真是越来越棒了！
我发现一个问题：在原版书的提示中，它更愿意用low和high两个变量里保存判断范围的下标值，而我只用1个，这是因为我每次考虑的都是最后一个与前n-1个，而书上考虑的是第一个和后n-1个。
