请问如下unknown递归算法实现了什么功能？附代码及测试用例

这个递归算法的作用是返回数组a中从下标t到下标n范围内，值最小的元素的下标，当区间内存在多个值相等的最小值时，会返回最靠右的最小值下标。

算法前置约束：t ≤ n

algorithm unknown(a[t...n])
    if t = n 
        return n
    sol ← unknown(a[t + 1...n])
    if a[t] < a[sol]
        return t
    else
        return sol

测试用例调用unknown([2, 3, 7, 2, 8])，默认数组下标从0开始，初始入参t=0、n=4，递归过程如下：

1. 调用unknown(a[0...4])，需先求解子区间a[1...4]的最小值下标
2. 调用unknown(a[1...4])，需先求解子区间a[2...4]的最小值下标
3. 调用unknown(a[2...4])，需先求解子区间a[3...4]的最小值下标
4. 调用unknown(a[3...4])，需先求解子区间a[4...4]的最小值下标
5. 调用unknown(a[4...4])，触发终止条件t=n，返回下标4
6. 回到unknown(a[3...4])：a[3]=2 < a[4]=8，返回下标3
7. 回到unknown(a[2...4])：a[2]=7 > a[3]=2，返回下标3
8. 回到unknown(a[1...4])：a[1]=3 > a[3]=2，返回下标3
9. 回到unknown(a[0...4])：a[0]=2 不小于 a[3]=2，返回下标3

最终测试用例输出结果为3，对应数组中第4个元素（下标从0计数）的值2。

• 算法采用自顶向下的递归思路，每轮将问题规模缩小1，时间复杂度为O(n)，空间复杂度为O(n)（递归栈开销）
• 判定条件仅在a[t]严格小于子区间最小值时才替换返回下标，因此相同最小值情况下会优先返回更靠右的下标，如果要改为优先返回最左的最小值下标，只需将判定条件改为a[t] <= a[sol]即可。

内容的提问来源于stack exchange，提问作者Knol