【数据结构】43_递归的思想与应用（上）

递归是一种数学上分而自治的思想

将原问题分解为规模较小的问题进行处理

分解后的问题与原问题类型完全相同，但规模较小

通过小规模问题的求解，能够轻易求得原问题的解

问题的分解是有限的（递归不能无限进行）

当边界条件不满足时，分解问题（递归继续进行）

当边界条件满足时，直接求解（递归结束）

递归模型的一般表示法

递归在程序设计中的应用

递归函数

函数体中存在自我调用的函数

递归函数必须有递归出口（边界条件）

函数的无限递归将导致程序崩溃

递归思想的应用

求和 Sum

Sum(n) = 1 + 2 + 3 + ... + n

【数据结构】43_递归的思想与应用（上）

编程实现：递归求和

#include <iostream>

using namespace std;

unsigned int sum(unsigned int n)
{
    if (n > 1)
    {
        return n + sum(n - 1);
    }

    return 1;
}

int main()
{
    cout << sum(100) << endl;

    return 0;
}

输出：

斐波那契数列

数列自身递归定义：1,1,2,3,8,13,21,...

【数据结构】43_递归的思想与应用（上）

编程实验：斐波那契数列

#include <iostream>

using namespace std;

unsigned int fibonacci(unsigned int n)
{
    if (n > 2)
    {
        return fibonacci(n-1) + fibonacci(n-2);
    }

    return 1;
}

int main()
{
    for (unsigned int i=1; i<=10; ++i)
    {
        cout << fibonacci(i) << endl;
    }

    return 0;
}

输出：

求解字符串长度

【数据结构】43_递归的思想与应用（上）

编程实验：求解字符串长度

#include <iostream>

using namespace std;

unsigned int _strlen_(const char *s)
{
//    if (*s != '\0')
//    {
//        return 1 + _strlen_(s + 1);
//    }

//    return 0;

    return (s ? (*s ? (1+_strlen_(s+1)) : 0) : 0);
}

int main()
{
    cout << _strlen_("D.T.") << endl;

    return 0;
}

输出：