函数和递归（二）

一个函数调用自身就是递归。
通常可以把大型复杂问题转换成与原文题相似但规模较小的问题求解。

最简单的递归程序：

#include <stdio.h>
int main() {
    printf("递归\n");
    main();
    return 0;
}

递归常见的错误：栈溢出

---

练习1：接受一个整型值（无符号），按照顺序打印它的每一位。例如：输入：1234，输出1 2 3 4

#include <stdio.h>
void print(int n)
{
    if (n>9) {
        print(n/10);
    }
    printf("%d ",n%10);
}
 
int main()
{
    unsigned int num = 0;
    scanf("%d",&num);
    //递归
    print(num);
    return 0;
}

递归在书写时一定要写条件，不要让递归无限循环下去！

递归的两个必要条件

• 存在限制条件，x当满足这个限制条件的时候，递归便不再继续。
• 每次递归调用之后越来越接近这个限制条件

---

练习二：编写函数，不允许创建临时变量，求字符串长度
使用临时变量的方法：

int my_strlen(char* str)
{
    int count = 0;
    while (*str !='\0') {
        count++;
        str++;
    }
    return count;
}
 
int main()
{
    char arr[] = "bit";
    //模拟实现了一个strlen函数
    int len = my_strlen(arr);
    printf("%d\n",len);
}

不创建临时变量：

int my_strlen(**char*** str)
{
    if(*str != '\0')
 
        return 1+my_strlen(str+1);
    else
        return 0;
}
 
int main()
{
    char arr[] = "bit";
    //模拟实现了一个strlen函数
    int len = my_strlen(arr);
    printf("%d\n",len);
}

---

递归与迭代

练习3:求n的阶乘
不使用递归

int Fac1(int n)
{
    int i = 0;
    int ret = 1;
    for (i = 1; i <= n; i++) {
        ret = ret * i;
    }
    return ret;
}
 
int main()
{
    int n = 0;
    int ret = 0;
    scanf("%d",&n);
    ret = Fac1(n);//用循环的方式实现
    printf("%d\n",ret);
    return 0;
}

使用递归的方式

int Fac2(int n)
{
    if (n<=1) {
        return 1;
    }else
        return n*Fac2(n-1);
}
 
int main()
{
    int n = 0;
    int ret = 0;
    scanf("%d",&n);
    ret = Fac2(n);//用循环的方式实现
    printf("%d\n",ret);
    return 0;
}

---

练习4:斐波那契数列
前两个数之和等于第三个数字

int Fib(int n)
{
    if (n <= 2) {
        return 1;
    }else{
        return Fib(n-1)+Fib(n-2);
    }
}
 
int main()
{
    int n = 0;
    int ret = 0;
    scanf("%d",&n);
    ret = Fib(n);
    printf("%d\n",ret);
    return 0;
}

上面代码的优化：

int Fib(int n)
{
    int a = 1;
    int b = 1;
    int c = 1;
    while (n>2) {
        c = a + b;
        a = b;
        b = c;
        n--;
    }
    return c;
}
 
int main()
{
    int n = 0;
    int ret = 0;
    scanf("%d",&n);
    ret = Fib(n);
    printf("%d\n",ret);
    return 0;
}

函数递归的经典问题：

• 汉诺塔问题
• 青蛙跳台阶问题