引入

递归学习过编程的基本上都应该大体知道，但是递归的效率并不高，我们通常使用迭代循环，但我在探索未知的情况下，递归可能会更好。我们通过斐波那契数列来了解一下递归。

斐波那契数列

因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34…
即开始有一对儿兔子，然后3个月后兔子长大了，这对兔子会生一对儿兔子，之后的每个月这对儿兔子又生一对儿，假设兔子不会死亡，那么 N 个月后有多少对儿兔子。

理解

数列：1、1、2、3、5、8、13、21、34…
找到数列的规律之后，我们发现，3号数是1号+2号，6号数是4号+5号，即该数前两个数的和。

迭代循环解题

#include <stdio.h>
int main(){
    int f1=1,f2=1,f3;
    //将第1、2个月的数先赋值，作为计算基底
    printf("%12d\t%12d\t",f1,f2);
    //由于已经赋值了，所以就先输出
    for(int i=3;i<41;i++){
        f3=f1+f2;
        printf("%12d\t",f3);
        //利用循环输出第三个月的数，也就是前两个月的和
        if(i%4==0){
            printf("\n");
        }
        //判断换行
        f1=f2;
        f2=f3;
        //将用于相加的两个数向前推移
    }
}

运行结果

递归解题

#include <stdio.h>
int fibo(int i){
if(i<2){
return i==0?0:1;
}
return fibo(i-1)+fibo(i-2);
}

int main(){
printf("%d\n",fibo(12));
}

运行结果
144

也就是第12月的兔子数是144

递归

引入了上面的斐波那契数列，我们就大概了解了递归

  • 函数调用自己和调用其它函数并没有本质不同
  • 我们把一个直接调用或者通过一系列的调用语句间接调用自己的函数
  • 称之为递归！

递归最需要注意的

递归最需要注意的就是死循环！ 所以：

  • 每个递归定义必须至少有一个条件
  • 满足条件时就不再继续递归
#include <stdio.h>
int fibo(int i){
if(i<2){
return i==0?0:1;
}
return fibo(i-1)+fibo(i-2);
}

在这个递归中，我们的结束条件就是 i<2 , 当 i<2 时，就有返回值了

递归特点

对比了刚才 Fibonacci 数列之后，我们发现

  • 递归能使代码更清晰易懂
  • 大量的递归调用会建立函数的副本，会消耗大量的时间和内存。
  • 递归分为调用和回退两个阶段。
  • 递归的回退顺序就是它的调用顺序的逆序。

计算阶乘

我们举个例子，计算一下阶乘 ，例如5的阶乘
$5!=5 \times 4 \times 3 \times 2 \times 1$

分段函数
$n!=\left{\begin{matrix}1&n=0& \n\times(n-1)&n>0& \end{matrix}\right.$

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

int main(){
    printf("%d\n",factorial(5));
}

其实有了分段函数转换为递归非常简单。

反向输出文字

我们再根据上面的这种分段函数思路，设计一个函数

  • 输入 Bliner
  • 输出 renilB
  • 即将输入的内容反向输出

代码

#include <stdio.h>
void transfer(){
    char a;
    scanf("%c",&a);
    if(a!='#'){
        transfer();
    }
    if(a!='#'){
        printf("%c",a);
    }
}

int main(){
    printf("请输入要转换的字符：\n");
    transfer();
    printf("\n");
}

思路

  • 首先要想，判断结束的条件是什么
  • 因为要不限制字符长度，所以要遇到某个特殊字符就停止
  • 然后就是如何反向输出的问题
  • 我们知道，递归有调用和回退两个结点
  • 调用的时候就接收字符
  • 回退的时候就输出最后一层接收到的字符

二分法的递归实现

二分法就是不断的缩小一半的搜索范围，来快速找到目的的查找法。

  • 判断结束的条件，就是找到这个数值
  • 如果没有找到，再次调用函数找下一层
  • 然后 low、high 重新分配，直到找到为止
#include <stdio.h>
int search(int target , int low , int high , int num[]){
    if(high>=low){
        int m=(low+high)/2;
        if(target>num[m]){
            return search(target , m+1, high , num);
        }else if(target<num[m]){
            return search(target , low , m-1 , num);
        }else{
            return m;
        }
    }
    return -1;
}
int main(){
    int num[]={1,2,3,4,5,6,7,8,9,10};
    printf("9在第%d位！\n",search(9,0,9,num)+1);
}

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。