递归是一种直接或间接调用自身函数。

• 确定递归公式
• 确定边界条件

练习

1.递归打印1~10

#include <stdio.h>
// 打印1 ～ 10
//
void PrintN(int n,int count){
        if(n <= 10){  // 边界条件
                printf("%d ",n);
                PrintN(n+1,count);
        }
}
int main(){
        int n;
        scanf("%d",&n);
        int count;
        scanf("%d",&count);
        PrintN(n,count);
        printf("\n");
}

2.打印数组以及数组求和

#include <stdio.h>
// 递归公式
// 边界条件
#define SIZE sizeof(arr)/sizeof(arr[0])
void PrintElement(int* arr,int n,int i){
        if(i<n){
                printf("%d\n",arr[i]);
                PrintElement(arr,n,i+1);
        }
}
void PrintArr(int* arr,int n){
        PrintElement(arr,n,0);
}

// 只打印首元素
// 数组依次移动
void PrintArr2(int* arr,int n){
        if(0 == n) return;
        printf("%d\n",arr[0]);
        PrintArr2(arr+1,n-1);
}
// 带有返回值
int SumArr(int* arr,int n){
        // 递过程
        printf("SumArr(%p,%d)\n",arr,n);
        if(0 == n) return 0;
        int res = arr[0]+SumArr(arr+1,n-1);
        // 归过程
        printf("SumArr(%p,%d) = %d\n",arr,n,res);
        return res;
}

3.打印第n个斐波那契数列

#include <stdio.h>
// 1 1 2 3 5 8 13 ..
// 获取每个月的兔子总数
// f(n) = f(n-1)+f(n-1) //  n >=3
//
//递归可能比较消耗内存
int Get_rabbits(int month){
        if(0 == month) return 0;
        if(1 == month || 2 == month) return 1;
        return Get_rabbits(month-1)+Get_rabbits(month-2);
}

int main(){
        int month;
        scanf("%d",&month);
        int res = Get_rabbits(month);
        printf("%d\n",res);
}

对链表的递归操作

1.定义链表结构

typedef struct Node{
        int val;
        struct Node* next;
} Node;

2. 创建链表(首添加)

void Create_list(Node** header,int n,int i){
        if(n>0){
                Node* node = malloc(sizeof(Node));
                node->val = i;
                node->next = *header;
                *header = node;
                Create_list(header,n-1,i+1);
        }
}

3.打印链表

• 递：顺序打印链表
• 归：逆序打印链表

void Print_list(Node* header){
        if(NULL != header){
                // 顺序打印
                printf("%d\n",header->val);
                Print_list(header->next);
                // 逆序打印
                printf("%d\n",header->val);
        }
}

4.反转链表

Node* Reverse_list(Node* header){
        if(NULL == header) return header; // 空链表情况

        // 非空链表
        if(NULL == header->next) return header;
        Node* root = Reverse_list(header->next);
        Node* p = header->next;
        p->next = header;
        header->next = NULL;
        // 每次返回的都是最后一个节点,最后一个节点没有发生改变
        return root;
}

5.尾添加元素

Node* Append_list(Node* header,int val){
        // 空链表情况
        if(NULL == header){
                Node* new_node = malloc(sizeof(Node));
                new_node->val = val;
                new_node->next = NULL;
                header = new_node;
        }
        // 边界条件
        if(NULL == header->next){
                Node* new_node = malloc(sizeof(Node));
                new_node->val = val;
                new_node->next = NULL;
                header->next = new_node;
        }else{
                Append_list(header->next,val);
        }
        // 返回自身
        return header;
}

6.销毁链表

• 从第一个节点开始销毁

Node* Destory_list(Node* header){
        if(NULL == header) return NULL;
        Node* free_node = header->next;
        free(header);
        // 每次都返回空
        return Destory_list(free_node);
}

• 从最后一个节点开始销毁

Node* Destory_list2(Node* header){
        if(NULL == header) return NULL;
        Destory_list2(header->next);
        free(header);
        return NULL;
}