2.3编写函数不允许创建临时变量，求字符串的长度。
尝试一下用递归的方式解决
思路:当发现str指向的字符不是'\0'时,长度至少为1, 总长度就是1加上后面字符串的长度
my_strlen("abcdef") <--> 1+my_strlen("bcdef")
画图解释:
为了便于理解，接下来简化一下字符串， 变为"abc"
int my_strlen(char* str) { if(*str != '\0') return 1 + my_strlen(str + 1); else return 0; } int main() { char arr[10] = "abc"; int len = my_strlen(arr); printf("%d\n", len); return 0; }
再次强调递归满足的两个条件:
1 满足语句条件，进入语句递归
2 以不断+1的方式逼近跳出的条件('\0')
if(*str != '\0')
return 1 + my_strlen(str + 1);
else
return 0;
错误总结:
错误代码:
if(*str != '\0')
return 1 + my_strlen(str++);
else
return 0;
原因
++是后置的，所以是先把str的地址传入函数，再＋＋，是没用的，没有逼近跳出条件
每一个函数的str都是独立的,代码会死递归
图解:
str+1和++str写法的区别
1 my_strlen(str + 1) <--> 2 my_strlen(++str)
1 把下一个字符的地址传进去了，留下的str是不会动的,对于str是不会修改
2 留下的str动了，如果递归回来想使用这个原来的地址，那就不是原来需要的，就会出现问题
补充:
总结:
1.内存分为一个个的内存单元，一个单元大小是byte
2.每个字节都有一个地址(地址之间相差1个字节)
递归与迭代
递归：是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现象。
迭代：是重复反馈过程的活动，其目的通常是为了逼近所需目标或结果。
求n的阶乘。（不考虑溢出）
求阶乘的一种基础方法
fac(n)=n * fac(n-1)
图解:
代码呈现:
int fac(int n) { int i = 0; int ret = 1; for (i = 1; i <= n; i++) { ret = ret * i; } return ret; } int main() { int n = 0; scanf("%d",&n); int ret = fac(n); printf("%d\n", ret); return 0; }
程序运行:
求第n个斐波那契数。（不考虑溢出）
"斐波那契数列:"
1 1 2 3 5 8 13 21 34 55 .........
即当n>=2时，这个数列从第3项开始，每一项都等于前两项之和。
图解:
递归的方式实现斐波那契数列计算
//求第n个斐波那契数 int count;//统计第n个斐波那契数重复计算的次数 int Fib(int n) { if (n == 3) count++; if (n <= 2) return 1; else return Fib(n - 1) + Fib(n - 2); } int main() { int n = 0; scanf("%d", &n); int ret = Fib(n); printf("%d\n", ret); printf("count=%d\n", count); return 0; }
count作用:
是用于计算第40(n输入的40)个斐波那契数时,统计第3个斐波那契数重复出现的次数
举例:
if (n == 3)
count++;
printf("count=%d\n", count) ;
图解:
可以发现36重复出现多次,而且如果n输入50时特别耗费时间,（如果你的参数比较大）那就会报错： stack overflow（栈溢出） 这样的信息
因为:
系统分配给程序的栈空间是有限的，但是如果出现了死循环，或者（死递归），这样有可能导致一 直开辟栈空间，最终产生栈空间耗尽的情况，这样的现象我们称为栈溢出。
递归缺点:
输入50，计算第50个斐波那契数
光标在动，说明程序还在运行。
打开任务管理器
还在占用着内存，说明程序是正常运行的
总结:
递归可以解决问题，但是遇到数字大的时候解决问题的效率很低
寻求解决问题其他办法:
迭代
循环也是迭代的一种
//迭代的方式 int Fib(int n) { int a = 1; int b = 1; int c = 1; while (n >= 3) { c = a + b; a = b; b = c; n--; } return c; } int main() { int n = 0; scanf("%d", &n); int ret = Fib(n); printf("%d\n", ret); printf("count=%d\n", count); return 0; }
思路:
写代码用递归还是迭代?
递归:写代码写起来很直接, 像公式一样写出来,代码没有明显问题
迭代:若递归写出来的效率太低,存在明显缺陷（斐波那契数列的问题用递归去写）,则用迭代的方式提高效率
提示：
1. 许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。
2. 但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。
3. 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。
欢迎各位大佬补充,谢谢支持！
