GUCS 样章

https://www.yinwang.org/blog-cn/2021/05/11/gucs-sample

作者为王垠，https://www.yinwang.org/

递归 Recursive

例如：

function length(ls)
{
    //...
}

如何写出递归函数（例1:length）

1. 写出递归调用的结构 write the recursive call

function length(ls)
{
    if (...)
    {
        // base case
    }
    else
    {
        return length(second(ls));
    }
}

2. 构建递归结果 construct the recursive case result from the recursive call

function length(ls)
{
    if (...)
    {
        // base case
    }
    else
    {
        return 1 + length(second(ls));
    }
}

3. 推导出基础用例 derive the base case from the recursive call

function length(ls)
{
    if (ls == null)
    {
        return 0;
    }
    else
    {
        return 1 + length(second(ls));
    }
}

至此，我们已经完成了计算一个列表长度的函数。一般我们使用head和tail来替代first、second，进一步优化可以写为：

var head = first;
var tail = second;

function length(ls)
{
    if (tail == null)
    {
        return 0;
    }   
    else
    {
        return 1 + length(tail(ls));
    }
}

我们在初中数学就学习了最基本的 演绎法 和 归纳法， 其实递归就是归纳法的一个应用。

上述步骤是王垠给出的推荐方法，就是先写出一般规律，再写特殊情况——特殊情况，也往往是递归的退出条件。 就像解数学题一样，如果我们对于一般规律还无法轻松看出，那么可以通过代入简单的用例，来推导。

例2：append

仍然是用上文所展示的方法：

1. append 函数，即两个list相拼接

我们的期望是：将 ls2 接在 ls1 的尾部

function append(ls1,ls2)
{
    //TODO
}

2. 构造一般规律

function append(ls1,ls2)
{
    if (...)
    {
        // TODO
    }
    else
    {
        return  pair(head(ls1),append(tail(ls1),ls2));
    }
}

3. 补全特殊情况

function append(ls1,ls2)
{
    if (ls1 == null)
    {
         return ls2;
    }
    else
    {
        return  pair(head(ls1),append(tail(ls1),ls2));
    }
}

例3: nth

nth(ls,n) 是指从 ls 中取出第 n 个数

function nth(ls,n)
{   
    if(ls == null)  // 这个 if 要写在前面
    {
        throw "Index out of bound";
    }
    else if (n == 0)    // 因为是从 0 开始数的。并非从 1 开始
    {
        return head(ls);
    }      
    else
    {
        return nth(tail(ls),n-1);
    }
}

练习

两数之和