C++：函数与递归 Function and Recursion

1. 函数调用堆栈、作用域、形参与实参 The stack of function call, function scope, formal parameter and actual parameter

    所谓“堆栈”，实际上就是个栈，和“堆”没有任何关系，只是都这么说而已。它的执行原理是：当函数A被调用时，它作为堆栈顶部的函数调用。A调用函数B时，B的函数调用加入栈成为新的顶部。B调用完时，退栈，控制权又回到了A。最底层的调用是main函数。

    如果变量在一个函数调用中被创建，则这个函数调用就是它的作用域—— 一旦函数调用被退栈，它也会被随之销毁。

    The working principle of function is: When a function A is called, it is added to the top of the stack. When A calls B, function B is added and become the new top element. Function B moves out of the stack when it is finished, and the control right returns to A. The bottom of the stack is main function.

    If a variable is created in a function call, then the call becomes its scope - once the function call is removed, it will be subsequently destroyed.

    最后要说的是形参与实参，看如下代码：

    Last but not least, I want to say something about function‘s parameters.

void f(int x) {
    x++;
    cout << x << endl;
}
int main() {
    int x = 1;
    f(x);
    cout << x << endl;
    return 0;
}

    主函数的x是实参，传入到函数f内的x是形参，只在f的调用内被分配内存。

    The variable x in main function is an actual parameter. However the x which is passed to function f is a formal parameter, only in f‘s call it will be allocated the memory.

2. 无参函数、内联函数、引用参数与默认实参 No-argument function, inline function, reference argument and default argument

    无参函数：不接受任何参数且不返回任何值，如void print()。

    内联函数：用来减少函数调用的开销——特别是小函数。它把函数代码的多份副本插入到程序中，而不是每次调用都把控制权给它。编译器通常忽略inline限定符，并且对除了小函数之外的函数，通常都这么做。

    引用参数：上面那个小例子就不是传递引用，而是实值传递，它为参数创建一个副本。而f(int &x)这样的传递引用，函数可以访问它的内存。当参数很大时，传递引用显然性能更好。大的不可修改的参数怎么办？通过常量的引用传递变为f(const int &x)，只是x就不能在f里改变了。

    默认实参：对形参指定默认实参，可以试试下面的例子：

    No-argument function: It does not accept any argument and not return any value, like "void print()".

    Inline function: It is used to reduce the cost of a function call - especially small functions. It inserts multiple copies of the function code into the program rather than give the control right to it in each call. Compilers often ignore inline qualifier, and for other functions it usually does the same thing as small ones.

    Reference argument: The example above is not pass-by-reference, but pass-by-value. It creates a copy of the argument. However, a reference passing like f (int & x), the function can access to its memory. When the argument is large, passing references clearly has a better performance. But how to do when a large parameter not allowed to be modified? Just pass a const reference like f (const int &x), and in this case you can not change the value of x in f.

    Default argument: Assign a default value to formal parameter. Here I offer a example.

int f(int x=2, int y=3, int z=5) {
    return x*y*z;
}
int main() {
    cout << f() << endl;
    cout << f(7) << endl;
    cout << f(7,11) << endl;
    cout << f(7,11,13) << endl;
    return 0;
}

3. 函数重载和函数模版 Function overloading and function template

    重载的例子：

    Here is the example of overloading.

int f(int x) {
    return x*x;
}
double f(double x) {
    return x*x;
}
int main() {
    cout << f(2) << endl;
    cout << f(2.5) << endl;
    return 0;
}

    而模版是更高效的重载，例子：

    How does compiler distinguish them? By the function signature, which is composed by function name and its types of formal parameters.

    What‘s more, function template is a more effective method of overloading.

template <class T>
T maximum(T a, T b, T c) {
  if (a<b) swap(a,b);
  if (a<c) swap(a,c);
  return a;
}
int main() {
    cout << maximum(2,5,3) << endl;
    cout << maximum(2.5, 8.0, 9.1) << endl;
    cout << maximum(‘S‘, ‘A‘, ‘B‘) << endl;
    while (1);
    return 0;
}

4. 递归与迭代 Recursion and iteration

    自调用的函数就是递归，当然也可以几个函数循环调用，其中终止条件是必需的。有许多相关的经典问题，就不赘述了。

    递归能实现的，迭代也可以实现。显然递归的花费要比迭代大，那为什么要用递归呢？因为迭代方法有时实现起来比较晦涩，难以反应问题，毕竟100个人里，也不会用一个人写汉诺塔用迭代（我是这样想的）。

    A recursion is a function can call itself or can be called cyclically among several functions, and the terminate condition is necessary. There are many classic problems associated with the topic, so here I do not go into details.

    The work that recursion could do is the same as iterations‘. Obviously recursion costs more than iteration, so why using recursion? Because sometimes iterative method  is too obscure. After all, in 100 people, no one writes Hanoi in iteration (I think so).