通用技术 [原创] 算法之递归 (1)

卡农Lucas · 2015年02月05日 · 最后由 securitytest 回复于 2017年09月26日 · 1474 次阅读

算法之递归（1）

最近事情太多了，很少有时间可以完全静下来认真研究一些东西；每当专注的写代码的时候，总是被其他事情打断。还好，礼拜天来了，总算可以抽出一些时间了 J

《代码之美》第一章有一个关于模式匹配的问题，即根据正则表达式在相应的文本中找到匹配的值，找到返回 1，没找到返回 0。撇开具体的实现，里面优美的递归调用倒是深深地吸引了我。于是，我开始重新思考递归，毕竟有些细节之前的思考还不够到位。

什么是递归

我的印象中的递归是函数调用自身来完成预先定义的操作。当然，实际涉及的内容更多，比如退出递归的条件，代码逻辑，参数等等。

可以将递归理解为栈，即调用序列是以顺序结构的形式并遵循后进先出的顺序存放在栈中的。举个例子来说，加入存在这样的调用 A()->B()->C()->D()，那么其在栈中的顺序如下，

A() : int

B() : int

C() : int

D() : int

通过这个例子不难看出，将 B，C，D 的名字全部换成 A，就是递归调用 A 的全部过程。

我们来看一个具体的例子，如何计算 1 到 N 个自然整数的和。

{1， 2， 3， 5， …， n}

解法一

定义一个全局变量，用来做存储当前的和。

具体实现如下

int sum = 0;

private void GetSum(int n)
{
    if (n == 0) return;
    if (n < 0)
        throw new ArgumentException("Invalid input.");
    sum += n;
    GetSum(n - 1);
}

这个递归逻辑上没有问题，但是多定义了一个变量，作为最终的用户，需要在其上面再封装一层可以使用。当然，也可以在写一个函数重新封装，然后 expose 这个 wrap 后的版本。

那么有没有更好的解决方案？

解法二

定义一个有返回值的函数。

开篇的时候，我介绍递归类似于堆栈，所以递归调用也遵循后调用现出的原则。如果加上返回值，那么就只需要计算当前的 n 值于 n 之前所有值的和即，便可以得到 n 个数的和。比如有 10 个数，当前 n 是 5，那么这层递归是 5 的和。

我们先来看一下代码，然后再做具体的分析。

private int GetSumWithReturn(int n)
{
    if (n < 0)
    {
        throw new ArgumentException("Invalid input.");
    }

    if (n == 0)
        return 0;

    return n + GetSumWithReturn(n - 1);
}