在C语言的学习过程中,我们时常遇到一些特殊的问题,这些问题一步一步解决,且这些步骤都是这个问题的上一步或下一步(语文不好,不太会形容,555),这时候,我们就可以使用递归。
递归其实就是函数自己调用自己链表的问题与一些树的问题常用它来解决。著名的深度优先搜索(DFS)就可以通过递归实现。
接下来给出几个简单例题帮助大家理解:
例1:非常经典的斐波那契数
#include
int fibonacci(int n)
{
if(n <= 2) {
return 1;
//第一、二个都是1。
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}//每个斐波那契数是它前两个的和,用递归来实现。
}
int main(void) {
int n;
printf("请输入你想输出第几项的斐波那契数:\n");
scanf("%d", &n);
printf("%d\n", fibonacci(n));
return 0;
}
例2:非常简单的一道二叉树题目
文章图片
/**
* Definition for a binary tree node.
* struct TreeNode {
*int val;
*struct TreeNode *left;
*struct TreeNode *right;
* };
*/
int maxDepth(struct TreeNode *root) {
if (root == NULL) return 0;
return fmax(maxDepth(root->left), maxDepth(root->right)) + 1;
}//每个结点的高度是它下面两个高度的最大值再加一,用递归实现。
例3:又是一道二叉树的题:
文章图片
文章图片
/**
* Definition for a binary tree node.
* struct TreeNode {
*int val;
*struct TreeNode *left;
*struct TreeNode *right;
* };
*/
bool hasPathSum(struct TreeNode *root, int sum) {
if (root == NULL) {
return false;
}//没有路,返回false。
if (root->left == NULL && root->right == NULL) {
return sum == root->val;
}//接下来无路可走,从头走到结束了,如果总和等于target,则返回true,找到,否则返回false。
return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}//最后递归,分别向左右两边找。
例4:全排列问题(深度优先搜索) 【基础知识|C语言递归】力扣46.全排列
给定一个 没有重复 数字的序列,返回其所有可能的全排列。
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int cnt;
void dfs(int step, int* nums, int numsSize, int** ret, int* path, bool* book) {
//step先从0开始
int i;
if (step == numsSize) {
//找到一种排列方式。
ret[cnt] = (int*)malloc(sizeof(int) * numsSize);
for(int i=0;
i
推荐阅读
- C语言|深度解析C语言之递归求解算法
- 算法|二进制,八进制,十进制,十六进制的相互转换【简单易懂】
- c语言|在ARM64下编程的常见陷阱(C语言常见陷阱)
- 树莓派|树莓派镜像制作
- C语言|(师承郝斌老师)C语言——结构体
- Linux系统网络编程|Linux系统(基础IO)
- 数据结构|【洋哥带你玩转线性表(四)——链式队列】
- 数据结构|【洋哥带你玩转线性表(三)——双向链表】
- 数据结构|数据结构——哈希查找的实现(C语言)