递归总结

• 递归
• • 什么是递归
  • 递归的特点 结构 缺点
  • 递归的本质
  • 递归的应用
• 递归实战
• • 阶乘
  • • 阶乘递归解法
    • 阶乘普通解法
  • 斐波拉契数列
  • • 斐波拉契数列递归解法
    • 斐波拉契数列普通解法
  • 汉诺塔
  • 输出一个数字的每一位
  • • 普通解法
    • 递归解法
  • 倒序保存字符串
  • • 递归解法

递归

什么是递归

递归简而言之就是函数自己调用自己 如图所示

但是递归并不是简简单单的自己调用自己的过程 它分为 传递 和 回归，传递就是橙色箭头 回归则是黑色箭头 这就是递归
以 计算阶乘为例，假设我们输入6 计算6的阶乘为例

#define _CRT_SECURE_NO_WARNINGS
#include
int factorial(int x) //递归体函数
{if (x == 1){return 1;  }return x * (factorial(x - 1));
}
int main()
{int i = 0;scanf("%d", & i);int k = factorial(i);printf("%d", k);return 0;
}

具体实现过程如下 我们可以很清楚看到 先传递 在归一 就是递归

递归的特点 结构 缺点

递归的本质

在传递的过程将问题化简 归一的过程将化简的问题解决

递归的应用

(1). 问题的定义是按递归定义的（Fibonacci函数，阶乘，…）；

(2). 问题的解法是递归的（有些问题只能使用递归方法来解决，例如，汉诺塔问题，…）；

(3). 数据结构是递归的（链表、树等的操作，包括树的遍历，树的深度，…）

递归实战

阶乘

阶乘递归解法

#define _CRT_SECURE_NO_WARNINGS
#include
int factorial(int x)   // 递归体
{if (x == 1)// 函数出口{return 1;  }return x * (factorial(x - 1));//就x！转换成X*((x-1)!) 达到传递化简的目的
}
int main()
{int i = 0;scanf("%d", & i);int k = factorial(i);printf("%d", k);return 0;
}

阶乘普通解法

#define _CRT_SECURE_NO_WARNINGS
#include
int main()
{int k = 0;scanf("%d", &k);int i = 0;int sum = 1;for (i = 1; i < k + 1; i++){sum = sum * i;    //利用循环累乘 最后打印}printf("%d", sum);return 0;
}

斐波拉契数列

斐波拉契数列 即0、1、1、2、3、5、8、13、21、34、………这样一串数字

斐波拉契数列递归解法

递归解法通过数学函数定义可轻松得到 他的递归体
是当n>1时 fib(n-2)+fib(n-1)
递归出口就是n=0 返回0，n=1，返回1

#define _CRT_SECURE_NO_WARNINGS
#include
int fib(int x)  //第0个元素为0 第一个元素为1
{if (x == 0){return 0;}else if (x == 1)  //出口{return 1;}elsereturn fib(x - 2) + fib(x - 1); //循环体 
}int main()
{int k = 0;scanf("%d", &k);int sum = fib(k);printf("%d", sum);return 0;
}

斐波拉契数列普通解法

#define _CRT_SECURE_NO_WARNINGS
#includeint fib(int x)
{int i = 0;int j = 1;int k = 0;int m = 0;for (m = 0; m < x-1; m++){k = i + j;i = j;j = k;}return k;
}int main()
{int k = 0;scanf("%d", &k);int sum = fib(k);printf("%d", sum);return 0;
}

汉诺塔

汉诺塔简单了解

输出一个数字的每一位

如 输入 1234 输出 1 2 3 4

普通解法

这里用取对数的方法得到有多少位 依次除以位数的10次方 即可

#define _CRT_SECURE_NO_WARNINGS
#include
#include
void  elect(int x)
{printf("逆序输出");float k = 0.1;int m = 0;do{m = x % 10;k = k * 10;printf("%d是%f位",m,k);x = x / 10;if (x < 9){k = k * 10;printf("%d是%f位", m, k);break;}} while (1);printf("\n \n");
}
void  elect2(int x)
{printf("顺序输出");int digit = log10(x) ;int i = 0;int m = 0;for (i = pow(10, digit); i >0; i = i / 10){m = x / i;printf("%d  ", m);x = x % i;}}
int main()
{int k = 0;scanf("%d", &k);//elect(k);elect2(k);return 0;
}

递归解法

#define _CRT_SECURE_NO_WARNINGS
#include
void elect(int x)
{    if (x > 9){elect(x / 10);  //递归体 通过除以10 来使得问题更接近正确答案}printf("%d  ", x % 10);//出口}
int main()
{int k = 0;scanf("%d", &k);elect(k);return 0;
}

倒序保存字符串

将参数字符串中的字符反向排列，不是逆序打印

递归解法

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
void reverse_string(char arr[])
{int sz = strlen(arr);int tmp = *arr;*arr = *(arr + sz - 1);  //将最后一个和第一个互换*(arr + sz - 1) = '\0';// 将最后一个赋值为0if (strlen(arr) > 1)//如果不是最后一个则 指针后移{reverse_string(arr + 1);}*(arr + sz - 1) = tmp;
}
int main()
{char arr[] = "abcdef";reverse_string(arr);printf("%s\n", arr);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！