【数据结构】递归和分治思想之递归

斐波那契数列的实现

斐波那契问题介绍

如果一对兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。假设所有兔子都不死，那么一年后可以繁殖多少对兔子？

分析

所经过的月数	1	2	3	4	5	6	7	8	9	10	11	12
兔子对数	1	1	2	3	5	8	13	21	34	55	89	144

表中的数字1，1，2，3，5，8，13...构成了一个序列，这个序列的特点是：前面两个相邻项之和 = 后一项.

用常规的迭代来实现

int main(int argc, const char * argv[]) {    
    int i;
    int a[12];
    a[0] = 0;
    a[1] = 1;
    printf("%d ",a[0]);
    printf("%d ",a[1]);
    
    for (i = 2; i<13; i++) {
        a[i] = a[i-1]+a[i-2];
        printf("%d ",a[i]);
    }
    printf("\n");
    return 0;
}

输出结果

用递归来实现

#include <stdio.h>

/**
 * 斐波那契递归函数
 */
int Fib(int i){
    
    if (i < 2)
        return i == 0 ? 0 : 1;
    return Fib(i - 1) + Fib(i - 2); // 这里Fib就是函数自己，它在自己调用自己
}

int main(int argc, const char * argv[]) {
    
    for (int i = 0; i < 40; i++) {
        printf("%d ", Fib(i));
    }
    printf("\n");
    return 0;
}

同样的问题用递归来实现，代码很简洁。不过对于递归的理解有点费脑！
递归就是在函数中调用该函数本身的函数。
对于递归可以这样理解：不用把一个递归函数中调用自己的函数看作是在调用自己，而就当它是在调用另个一函数，只不过这个函数和自己长的一样。

递归

递归定义

一个直接调用自己或者通过一些列的语句间接调用自己的函数叫做递归函数。

递归注意点

• 每个递归定义必须至少有一个条件，满足时递归不再进行，即不再引用自身而是返回值退出。
• 递归使用的是选择结构，迭代使用的是循环结构。（这是迭代和递归的区别）
• 虽然递归是结构更清晰简洁，但是大量的递归调用会建立函数副本，会消耗大量的时间和内存。

递归的使用举例

1.求n的阶乘

int factorial(int n){
    if (n == 0)
        return 1;
    else
        return n * factorial(n - 1);
}

2.将输入的任意长度的字符串反向输出。以#作为输入结束标志。例如输入字符串ABC，反向输出字符串CBA。

void printC(){
    char a;
    scanf("%c", &a);
    
    if (a != '#') printC(); // 递归调用
    if (a != '#') printf("%c", a); // 回退输出
}