CS2L10——递归函数

递归

所谓递归，就是让函数自己调用自己

注意，错误的递归函数（或者说没有终止条件的递归）会无限递归导致爆栈！

1
2
3
4
5
6
7
8
9
static void Fun()
{
    Fun();
}

static void Main(string[] args)
{
    Fun();
}

报错：

​image​

1
2
3
4
5
6
Stack overflow.
Repeat 24088 times:
--------------------------------
   at lesson11递归函数.Program.Fun()
--------------------------------
   at lesson11递归函数.Program.Main(System.String[])

一个正确的递归函数，必须要有结束调用的条件！
用于条件判断的 这个条件 必须改变 能够达到停止的目的

例如，用递归函数打印出 0 到 10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
static void Fun(int a)
{
    Console.WriteLine(a);
    ++a;
    if (a > 10)
    {
        return;
    }
    Fun(a);
}

static void Main(string[] args)
{
    Fun(0);
}

输出：

1
2
3
4
5
6
7
8
9
10
11
0
1
2
3
4
5
6
7
8
9
10

关于递归和循环

要注意，递归不是循环！循环是反复执行一段代码，执行结束回到开头，而递归是在函数执行途中调用自己，执行期间回到开头

只是有些递归可以优化为循环，例如尾递归，尾递归指的是函数在尾位置调用自身，
上例就是尾递归，这样的递归常可以优化为循环，优秀的编译器会在编译时自动优化。

而某些递归则不容易优化为循环，或者改为循环反而降低性能或者徒增代码量，例如，遍历文件树

假设有这样的数组，数组内部有字符串，或者字符串数组，字符串数组还可能嵌套数组，遍历这个数组中的所有字符串并输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
static void TraverseString(object[] array)
{
    for (int i = 0; i < array.Length; ++i)
    {
        //如果遍历到的元素是数组，就将这个数组元素传入到自己，递归调用
        if (array[i] is object[])
        {
            TraverseString((object[])array[i]);
        }
        else
        {
            Console.WriteLine(array[i]);
        }
    }
}

static void Main(string[] args)
{
    object[] tree =
    {
        "aaaa",
        "bbbb",
        new object[]
        {
            "ccccaaaa",
            "ccccbbbb"
        },
        "dddd",
        "eeee",
        new object[]
        {
            "ffffaaaa",
            "ffffbbbb",
            new object []
            {
                "ffffccccaaaa",
                "ffffccccbbbb"
            }
        },
        "gggg",
    };

    TraverseString(tree);
}

输出：

1
2
3
4
5
6
7
8
9
10
11
aaaa
bbbb
ccccaaaa
ccccbbbb
dddd
eeee
ffffaaaa
ffffbbbb
ffffccccaaaa
ffffccccbbbb
gggg

上例中的数据集合就很适合使用递归去遍历整个数组的字符串，尤其是嵌套层数不确定的时候，使用递归会简化很多代码量