所谓递归是函数自己调用自己。

1.什么是递归

C语言中的递归是一种编程技术，首先要明确递归一定是发生在函数身上，简单来说就是一个函数直接或间接地调用自己。递归函数通常用于解决那些可以通过将问题分解为更小的、相似的子问题来解决的问题。递归的应用常用于处理树结构、图遍历、分治算法、动态规划等场景。

我们通过一个查找案例来理解递归的实际应用场景。

实例：查找数组中是否存在指定元素。

#include <stdio.h>
#include <stdlib.h>
#define LEN(x) sizeof(x) / sizeof(x[0])

int search(int arr[],int len,int dest){
    int iCount=0;
    for(int i=0;i<len;i++,iCount++){
       if(arr[i]==dest){
          printf("找到元素，i=%d\n",i);
          printf("循环次数：%d\n",iCount);
          return i;
       }
    }
    printf("循环次数：%d\n",iCount);
    return -1;
}

int main() {
    int arr[]={23,14,8,10,18,9,33,21,17,19,4,32};
    int dest=4;
    int pos=-1;

    if((pos =search(arr,LEN(arr),dest))!= -1){
       printf("索引为%d的位置找到元素：%d\n",pos,dest);
    }else{
       printf("未找到元素%d\n",dest);
    }
    return 0;
}

我们的算法虽然可取，但是每次搜索元素都是从前往后依次查找，如果数组元素数量过多，显然效率低下。 我们可以通过递归实现一种折半查找算法，大大提升查找效率。

折半查找的基本思想是将n个元素组成的数组先排序后分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果xa[n/2],则只要在数组a的右半部搜索x。

首先，我们使用冒泡排序算法实现对数组的排序。

#include <stdio.h>
#include <stdlib.h>
#define LEN(x) sizeof(x) / sizeof(x[0])

void popSort(int arr[],int len){

    for(int i=0;i<len-1;i++){
       for(int j=0;j<=i;j++){
          if(arr[j]>arr[j+1]){
             int temp;
             temp = arr[j];
             arr[j]=arr[j+1];
             arr[j+1]=temp;
          }
       }
    }
} 


int main() {
    int arr[]={23,14,8,10,18,9,33,21,17,19,4,32};
    popSort(arr,LEN(arr));

    printf("\n-------------排序之后-----------\n");
    for(int i=0;i<LEN(arr);i++){
       printf("%d ",arr[i]);
    }
    return 0;
}

运行结果： -------------排序之后------------ 8 9 10 14 17 18 19 21 4 23 32 33

再通过递归实现折半查找。

#include <stdio.h>
#include <stdlib.h>
#define LEN(x) sizeof(x) / sizeof(x[0])

//全局变量用来统计查找次数
int iCount = 0;

void popSort(int arr[],int len) {

    for(int i=0; i<len-1; i++) {
        for(int j=0; j<=i; j++) {
            if(arr[j]>arr[j+1]) {
                int temp;
                temp = arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }
}

int binarySearch(int arr[],int low,int high,int dest) {
    if(low>=high) {
        return 0; //表示未找到该元素；
    }
    iCount++;
    int mid = (high+low)/2;
    if(dest==arr[mid]) {
        return 1;
    }
    if(dest<arr[mid]) {
        return binarySearch(arr,low,mid-1,dest);
    }
    if(dest>arr[mid]) {
        return binarySearch(arr,mid+1,high,dest);
    }
}

int search(int arr[],int len,int dest) {
    popSort(arr,len); //首先对数组进行排序。

    return binarySearch(arr,0,len,dest);
}

int main() {
    int arr[]= {23,14,8,10,18,9,33,21,17,19,4,32};
    int dest = 9;
    int pos = search(arr,LEN(arr),dest);

    if(pos) {
        printf("找到元素：%d\n",dest);
    } else {
        printf("未找到元素：%d\n",dest);
    }
    printf("查找次数：%d",iCount);

    return 0;
}

2.递归编程练习

实例1： 求斐波那契数列的第n项。 什么是斐波那契数列？数列的前两项都是1，从第三项开始每一项是前两项之和，这样的数列称为斐波那契数列。 例如： 1,1,2,3,5,8,13…这样一个数列就是斐波那契数列。 求斐波那契数列第n项的值，就可以使用递归实现。

#include <stdio.h>
#include <stdlib.h>

long long fact(long long n,long long prev,long long next){

   if(n==2){
      return next;
   }
   return fact(n-1,next,prev+next);
}

int main() {
    long long n=100;
    printf("第%d项是：%lld\n",n,fact(n,1,1));
    return 0;
}

运行结果： 第100项是：3736710778780434371