从C#开始的编程入门——函数

上一篇：数组

我们先从一个算法开始

停！你怎么就开始说起算法来了？？？

看见算法二字大可不必紧张。算法只是解决问题的办法，它并不一定就是非常非常复杂的一大段代码，不要看到“算”字脑海里就浮现出复杂的公式和代码（虽然有时候也有），复杂不等于高效，更不等于符合实际要求。

比如我们下面来思考一个问题。

如果给定一个数组，我们如何将所有元素升序（从小到大）排列？ 以我们前面所讲到的，已经完全可以解决。

请尝试思考解决，再看后续的讲解。

冒泡排序

冒泡排序（Bubble Sort）是一种非常简单、非常符合第一反应的排序算法。

我们使用for遍历（Traverse，就是从头到尾挨个挨个看的意思）我们的数组。

然后我们把每一个元素和旁边的相比较。我们要求是升序排列，那么当我们发现右边的元素比手上的元素小时，我们就把两者相互交换。这样在第一次遍历完毕后，最大的元素就跑到了数组的最右边。

重复这个过程。直到没有元素需要交换。由于第一次遍历之后，最大元素的位置已经确定，所以第二次我们不再需要遍历到最后一个位置。而第二次之后的第三次也是一样的道理，我们每次只需要遍历到上一次结束位置的前一个位置，从而节约一点时间。

最后所有的元素都已经排到对应的位置，我们也不需要再去遍历，至此我们的数组就排序完毕了。

实际上，我们用代码描述起来更加清楚。

由于我们需要掌握旁边元素的情况，这里我们不使用foreach，而是使用for，以便可以把控制变量加一以访问右边的元素。我们这里需要两层循环相互嵌套。外面的for记录已经排了几次了，里面的循环控制实际的遍历和交换操作。

比如第一次遍历，实际上只确定了0个元素的位置，此时i为0。那么内部循环需要查看数组的array.Length - 1 - i个元素，此时也就是要从头到尾检查。那么第一轮遍历结束，外部循环进入第二次，i加一，表示已经进行一次，那么内部循环便会减少一次遍历。

内部的for循环会比较右边的元素，也就是j+1。temp变量用于暂时保存j的值，以防把右边的元素值给j之后它的值就丢失了。（我才发现原来奶牛关的markdown是支持代码块的，以后不用图片了）

var temp = 0;
var array = new int[]{9, 8, 6, 1, 5, 3, 7, 2, 4};
    for (int i = 0; i < array.Length; i++)
    {
        for (int j = 0; j < array.Length - 1 - i; j++)
        {
            if (array[j] > array[j + 1])
            {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }

最后尝试再遍历一次数组输出每个元素，看看是否是正确的算法。

冒泡排序可以说是最简单的排序算法，它的问题在于对于很多情况来说实在是太慢了。

问题

好了，现在我们写好了一个给数组排序的算法。不过也就十多行。如果说整个程序只需要进行一次排序操作就完事了，那么还挺好说的。

但是如果一个程序需要重复进行两次排序操作，你直接复制粘贴吗？或许可以。那么如果需要十次、一百次呢？显然不现实。

这个时候，我们可以把我们的排序算法写成一个函数。

函数

函数（function，又叫子程序）是大部分编程语言都支持的一种程序结构。他可以把一段代码组合在一次，然后取一个名字。这样在每次我们需要用到这段代码的时候，我们就可以直接用这个名字就行了，这样我们就做到了重用我们的代码。而不是去复制粘贴一段段重复的代码，这让我们的代码更加紧凑，避免代码重复。

如果我们要把上面的冒泡排序算法整理成一个函数，我们就可以像下面这样写：

int[] BubbleSort(int[] array)
{
    var temp = 0;
    for (int i = 0; i < array.Length; i++)
    {
        for (int j = 0; j < array.Length - 1 - i; j++)
        {
            if (array[j] > array[j + 1])
            {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
    return array;
}

你会发现，前面定义的array不见了。它的确不见了，现在只有括号里似乎是array的声明。

我们反思一下，如果我们把上面的代码照抄，那么我们始终都是在对上面那个array进行排序，如果我们想要对任意数组排序，难道我们要写一万个函数？显然没有意义。实际上，array具体是什么样的，在运行时需要括号里的array告诉代码，括号里声明的array，就叫做这个函数的参数（parameter）。

这里说的参数指的是形式参数（formal argument，常简称为形参），意思是它在我们定义的时候只相当于一个占位符，而其具体的取值，会在运行时依据传递进来的值决定。而相对应的，实际参数（actual argument，简称为实参）指的则是在我们使用函数时给形参的值。parameter和argument在中文语境下通常都翻译成参数，很多时候单独用parameter说的就是形参，而argument指的是实参。

回忆一下中小学数学。f(x) = x + 1这样一个函数的含义。x是自变量，它是不确定的，依据定义域和实际给定的值确定。x + 1是函数具体的操作，最后如果给定x=1，那么最终从函数f得到的值就是2。上面的话如果用编程语言的说法来描述就是：“定义函数f，需要一个参数x，返回x+1的值”。

如果用C#来描述：

int f(int x)
{
    return x + 1;
}

我们回到上面的排序算法的函数。且看第一行。我们称这是函数的签名（signature）。首先函数的定义从返回值类型开始。我们的函数返回类型是int[]，也就是数组。我们不需要给返回值取名字，因为我们函数只负责返回值，谁拿到这个值谁去取名就好了。紧接着是函数名，我们需要一个名字来使用我们的函数，这里是BubbleSort，就是冒泡排序的意思。然后是括号。括号里面是参数的声明。每个参数又有自己的类型，所以仍然是类型开始，然后是参数的名字，因为我们要在函数内部使用参数，所以我们要给它们取名字才行。参数是外界提供给函数的，这是函数可变的部分，我们根据参数的不同可以执行和它对应的合适的操作，以便最终得到对应正确的结果。

然后是大括号，里面是若干语句，就像之前的for和if一样。类似的，我们的参数，以及函数内部声明的变量，作用域都限定在函数内。

最后我们以return array结尾。凡是函数声明了返回值类型我们都需要在函数内部有对应的return，然后紧接着返回对应类型的值，这才算合法的函数。如果函数内有分支结构，必须保证每个分支都会返回值，因为运行时情况不确定，不能只有某个分支返回值。

提示：现在我们直接把函数写在Main内部即可。

现在写好了，我们如何使用函数呢？我们只需要写函数的名字，然后括号里传递（pass）对应的参数即可，这个操作我们称为函数调用（call，日语把call翻译成了一个更形象的词：呼び出す），而函数名称后面的括号，即是函数调用运算符。（call和invoke通常都翻译成调用，尽管有一些微妙的区别）

var sortedArray = BubbleSort(new int[]{1, 4, 5, 1, 114});

我们的函数会返回排序好的数组，因此我们可以使用另一个变量去接收这个返回值。

注意，在调用函数时，参数不仅可以是变量，实际上只要是和参数类型匹配的表达式即可。函数调用本身也是一个表达式。

返回值

不是所有函数都会返回值，比如我只想简单地输出一段话的话，我们为什么还需要返回什么值呢？函数不返回值的时候，我们也需要写出返回类型，这时候函数的返回类型是void。

void SayHello()
{
    System.Console.WriteLine("Hello");
}

由于没有返回值，我们return后面也就不需要值了，实际上，return也可以不写。不过如果有些时候需要在特定的条件下直接结束函数执行，我们也可以直接return。

参数列表

函数可以拥有多个参数，每个参数用逗号隔开。

int Sum(int a, int b, int c)
{
    return a + b + c;
}

参数默认值

参数可以拥有默认值，使用等号指定一个默认值。比如上面的函数。

int Sum(int a, int b = 1, int c = 0)

那么在我们调用时，如果不需要为有默认值的参数指定值，那么我们就可以像没有那些参数一样直接调用

Sum(2);

这是b和c依然存在，但是值是各自的默认值。

递归

递归就是一种套娃，也叫“我调用我自己”。

思考一下阶乘的概念，n的阶乘也就是1*2*3…*n。如果现在我需要你写一个函数计算n的阶乘，n为参数，最后返回阶乘的结果。

思路很简单，我们只需要挨个乘，循环到n即可，这里我就不写循环实现了。

我们思考一下上面这个算式，其实无论是程序中的乘法运算符，还是初等数学里面的乘号，至少在大部分情况下，乘号都是一个二元运算符，它只操作两个操作数。1*2*3*4实际上是((1*2)*3)*4。实际上就是乘法的不断嵌套。

现在我们用递归来描述这个算式。 这个函数很简单。

int Factorial(int n)
{
    return n > 1 ? n * Factorial(n - 1) : 1;
}

递归常常用来解决一些复杂但是可以划分成更小、更简单的子问题的问题。比如二叉搜索树相关的算法。经过上面的问题你也发现了，很多问题中，递归算法和循环算法是可以相互转换的，而有些时候递归算法还可能由于递归深度过深造成爆栈（stack overflow）的问题。因此很多时候需要慎重考虑。

从下一篇文章开始，我们进入面向对象编程的世界。

下一篇：开始面向对象