C语言中递归的实际应用与经典问题

目录
  • 一、什么是递归
  • 二、递归模板
  • 三、递归的实际应用
    • 1.阶乘递归
    • 2.斐波那契数列
  • 四、递归的经典问题
    • 汉诺塔问题
    • 青蛙跳台阶
  • 总结

一、什么是递归

递归简单的来说就是在函数中调用自己

它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的两个必要条件：

存在限制条件，当满足这个限制条件的时候，递归便不再继续。

每次递归调用之后越来越接近这个限制条件。

二、递归模板

void recursion(参数0)
{
    if (终止条件)
    {
        return;
    }
    else
    {
        recursion(参数1)
    }
}

三、递归的实际应用

1.阶乘递归

int tmp(int n)
{
	if (n == 1)
	{
		return 1;
	}
	else
	{
		return n*tmp(n - 1);
	}
}

2.斐波那契数列

斐波那契数列指的是这个数列从第3项开始，每一项都等于前两项之和。

递归算法：

int fibonacci(int n)
{
	if (n<=2)
		return 1;
	else
	{
		return fibonacci(n - 1) + fibonacci(n - 2);
	}
}

非递归方法：

int fibonacci(int n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (n > 2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}

四、递归的经典问题

汉诺塔问题

汉诺塔问题来源：

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

这里我们使用的方法是从特殊到一般，这也是数学问题中常用的方法。

首先我们设计一个盘，那就直接把这个盘从自身柱子移到目标柱。

其次我们看两个盘，三根柱子两个盘，先将上面的柱子移动到中间柱，然后将最下面的柱子移动到目标柱，最后中间的柱子。

再来看多个盘

void hanno(int n, char a, char b, char c)
{
	if (n == 1)
	{
		printf("%c->%c\n", a, c);
	}
	else
	{
		hanno(n - 1, a, c, b);//递归处理,一开始的时候,先将n-1个盘子移至过渡柱z上后再将最底下的大盘子直接移至目标柱子y
		printf("%c->&c\n", a, c);
		hanno(n - 1, b, a, c);//然后重复以上步骤,递归处理放在过渡柱z上的n-1个盘子,
	}
}

青蛙跳台阶

一只青蛙可以一次跳 1 级台阶或一次跳 2 级台阶,例如:跳上第一级台阶只有一种跳法:直接跳 1 级即可。跳上两级台阶,有两种跳法: 每次跳 1 级,跳两次; 或者一次跳 2 级.问要跳上第 n 级台阶有多少种跳法?

解题思路

我们设台阶数位N;

当N=1时，当然只有1种跳法；

当N=2时，青蛙可以跳2次1层和跳1次2层；

当N=3时，当有3层台阶时，青蛙可以选择先跳1层，剩下2层台阶，所以此时就是有2层台阶时的跳法，有2种；当青蛙选择第一次跳2层台阶时，剩下1层台阶，此时有1层台阶时的跳法，所以3层台阶时的方法是：2层台阶的方法 + 1层台阶的方法。

#include<stdio.h>
int frog(int n)
{
   if(n == 1)
   {
      return 1;
   }
   if(n == 2)
   {
      return 2;
   }
   return frog(n-1) + frog(n-2);
}
int main()
{
   int n;
   scanf("%d",&n);
   int ways = frog(n);
   printf("%d\n",ways);
   return 0;
}

总结

到此这篇关于C语言中递归的实际应用与经典问题的文章就介绍到这了,更多相关C语言中递归应用内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • 纯C语言:递归二进制转十进制源码分享

    复制代码 代码如下: #include<stdio.h>#include<math.h>int change(int n,int *sum,int *m)//n为第n位,m总位数{    char c;    if(c!='#')    {        *m=*m+1;        change(n+1,sum,m);    }    if(c=='#')    {        return *sum=int(*sum+pow(2,*m-n));    }}void main

  • C语言函数的递归和调用实例分析

    一.基本内容: C语言中的函数可以递归调用,即:可以直接(简单递归)或间接(间接递归)地自己调自己. 要点: 1.C语言函数可以递归调用. 2.可以通过直接或间接两种方式调用.目前只讨论直接递归调用. 二.递归条件 采用递归方法来解决问题,必须符合以下三个条件: 1.可以把要解决的问题转化为一个新问题,而这个新的问题的解决方法仍与原来的解决方法相同,只是所处理的对象有规律地递增或递减. 说明:解决问题的方法相同,调用函数的参数每次不同(有规律的递增或递减),如果没有规律也就不能适用递归调用. 2

  • C语言之整数划分问题（递归法）实例代码

    C语言之整数划分问题(递归法)实例代码 整数划分问题是算法中的一个经典命题之一,有关这个问题的讲述在讲解到递归时基本都将涉及.所谓整数划分,是指把一个正整数n写成如下形式: n=m1+m2+...+mi; (其中mi为正整数,并且1 <= mi <= n),则{m1,m2,...,mi}为n的一个划分. 如果{m1,m2,...,mi}中的最大值不超过m,即max(m1,m2,...,mi)<=m,则称它属于n的一个m划分.这里我们记n的m划分的个数为f(n,m); 例如但n=4时,他有

  • c语言版本二叉树基本操作示例(先序 递归 非递归)

    c语言版本二叉树基本操作示例(先序 递归 非递归)

    复制代码 代码如下: 请按先序遍历输入二叉树元素(每个结点一个字符,空结点为'='):ABD==E==CF==G== 先序递归遍历:A B D E C F G中序递归遍历:D B E A F C G后序递归遍历:D E B F G C A层序递归遍历:ABCDEFG先序非递归遍历:A B D E C F G中序非递归遍历:D B E A F C G后序非递归遍历:D E B F G C A深度:请按任意键继续. . . 复制代码 代码如下: #include<stdio.h>#include&

  • 对C语言中递归算法的深入解析

    对C语言中递归算法的深入解析

    许多教科书都把计算机阶乘和菲波那契数列用来说明递归,非常不幸我们可爱的著名的老潭老师的<C语言程序设计>一书中就是从阶乘的计算开始的函数递归.导致读过这本经书的同学们,看到阶乘计算第一个想法就是递归.但是在阶乘的计算里,递归并没有提供任何优越之处.在菲波那契数列中,它的效率更是低的非常恐怖. 这里有一个简单的程序,可用于说明递归.程序的目的是把一个整数从二进制形式转换为可打印的字符形式.例如:给出一个值4267,我们需要依次产生字符'4','2','6',和'7'.就如在printf函数中使用

  • C语言程序中递归算法的使用实例教程

    C语言程序中递归算法的使用实例教程

    1.问题:计算n! 数学上的计算公式为: n!=n×(n-1)×(n-2)--2×1 使用递归的方式,可以定义为: 以递归的方式计算4! F(4)=4×F(3) 递归阶段 F(3)=3×F(2) F(2)=2×F(1) F(1)=1 终止条件 F(2)=(2)×(1) 回归阶段 F(3)=(3)×(2) F(4)=(4)×(6) 24 递归完成 以递归方式实现阶乘函数的实现: int fact(int n) { if(n < 0) return 0; else if (n == 0 || n =

  • C语言递归操作用法总结

    本文实例总结了C语言递归操作用法.分享给大家供大家参考,具体如下: 用归纳法来理解递归 步进表达式:问题蜕变成子问题的表达式 结束条件:什么时候可以不再是用步进表达式 直接求解表达式:在结束条件下能够直接计算返回值的表达式 逻辑归纳项:适用于一切非适用于结束条件的子问题的处理,当然上面的步进表达式其实就是包含在这里面了. 递归算法的一般形式: void func( mode) { if(endCondition) { constExpression //基本项 } else { accumrat

  • C语言的递归思想实例分析

    本文实例分析C语言的递归思想,分享给大家供大家参考之用.具体方法如下: 通俗点来说,递归就是自己调用自己. 递归的难点一是理解递归的执行调用过程,二是设置一个合理的递归结束条件. 下面来看一段摘自书中的简单程序: #include <STDIO.H> long fact(int n); long rfact(int n); int main(void) { int num; printf("This program calculates factorials.\n"); p

  • C语言使用普通循环方法和递归求斐波那契序列示例代码

    复制代码 代码如下: #include <stdio.h> int fac(int x); int main(void){    int n;    scanf("%d", &n);    if (n == 1 || n == 2)        printf("1\n");    else if (n == 3)        printf("2\n");    else    {        int last = 1; 

  • C语言中递归的实际应用与经典问题

    C语言中递归的实际应用与经典问题

    目录 一.什么是递归 二.递归模板 三.递归的实际应用 1.阶乘递归 2.斐波那契数列 四.递归的经典问题 汉诺塔问题 青蛙跳台阶 总结 一.什么是递归 递归简单的来说就是在函数中调用自己 它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量. 递归的两个必要条件: 存在限制条件,当满足这个限制条件的时候,递归便不再继续. 每次递归调用之后越来越接近这个限制条件. 二.递归模板 void

  • C语言中递归和排列组合详解

    目录 排列组合三大问题: 1.打印n个数的全排列 2.打印n个数中任意m个数的全排列 3.打印n个数中任意m个数的组合 完整代码如下: 总结 排列组合三大问题: 1.打印n个数的全排列2.打印n个数中任意m个数的全排列3.打印n个数中任意m个数的组合 1.打印n个数的全排列 这个题实际上是可以直接用STL中的next_permutation()函数,代码如下: #include<bits/stdc++.h> using namespace std; int main(){ int data[4

  • C语言中的递归，你真的懂了吗？

    什么是递归? 要说到递归如果不说栈的话,我觉得有点不合适,递归特点就是不断的调用同一个函数,如果这个函数没有一个递归界限,那么就是死循环了,所以讨论递归,就必须要讨论递归的界限,就是限定这个递归调用多少次. 我们看一个例子 #include "stdio.h" int digui(unsigned long count ) { if(count > 0){ count --; printf("%d \n",count); digui(count); } ret

  • C语言中斐波那契数列的三种实现方式(递归、循环、矩阵)

    C语言中斐波那契数列的三种实现方式(递归、循环、矩阵)

    目录 一.递归 二.循环 三.矩阵 <剑指offer>里讲到了一种斐波那契数列的 O(logN) 时间复杂度的实现,觉得挺有意思的,三种方法都记录一下. 一.递归 一般来说递归实现的代码都要比循环要简洁,但是效率不高,比如递归计算斐波那契数列第n个元素. long long Fibonacci_Solution1(unsigned int n) { // printf("%d ", n); if (n <= 0) return 0; if (n == 1) retur

  • C语言非递归后序遍历二叉树

    C语言非递归后序遍历二叉树

    本文实例为大家分享了C语言非递归后序遍历二叉树的具体代码,供大家参考,具体内容如下 法一:实现思路:一个栈 先按 根->右子树->左子树的顺序访问二叉树.访问时不输出.另一个栈存入前一个栈只进栈的结点. 最后输出后一个栈的结点数据. #include<stdio.h> #include<stdlib.h> typedef struct TreeNode{ char element; struct TreeNode *left,*right; }Tree,*BTree;

  • 浅谈c语言中一种典型的排列组合算法

    浅谈c语言中一种典型的排列组合算法

    c语言中的全排列算法和组合数算法在实际问题中应用非常之广,但算法有许许多多,而我个人认为方法不必记太多,最好只记熟一种即可,一招鲜亦可吃遍天 全排列: #include<stdio.h> void swap(int *p1,int *p2) { int t=*p1; *p1=*p2; *p2=t; } void permutation(int a[],int index,int size) { if(index==size) { for(int i=0;i<size;i++) print

  • C语言中计算二叉树的宽度的两种方式

    C语言中计算二叉树的宽度的两种方式 二叉树作为一种很特殊的数据结构,功能上有很大的作用!今天就来看看怎么计算一个二叉树的最大的宽度吧. 采用递归方式 下面是代码内容: int GetMaxWidth(BinaryTree pointer){ int width[10];//加入这棵树的最大高度不超过10 int maxWidth=0; int floor=1; if(pointer){ if(floor==1){//如果访问的是根节点的话,第一层节点++; width[floor]++; flo

  • C语言数据结构递归之斐波那契数列

    C语言数据结构递归之斐波那契数列 因为自己对递归还是不太熟练,于是做POJ1753的时候就很吃力,就是翻棋子直到棋盘上所有棋子的颜色一样为止,求最少翻多少次,方法是枚举递归.然后就打算先做另一道递归的题(从数组中取出n个元素的组合),但是同样在递归的问题上不太理解.好吧,于是复习CPP,在第229页的时候,看到了斐波那契数列,回想起之前做过的一道题目,发现可以用递归的方法来做.于是决定优化一下之前的代码. 以下这段摘自<C primer plus> 斐波那契数列的定义如下:第一个和第二个数字都

  • 在Go语言中使用JSON的方法

    Encode 将一个对象编码成JSON数据,接受一个interface{}对象,返回[]byte和error: func Marshal(v interface{}) ([]byte, error) Marshal函数将会递归遍历整个对象,依次按成员类型对这个对象进行编码,类型转换规则如下: bool类型 转换为JSON的Boolean 整数,浮点数等数值类型 转换为JSON的Number string 转换为JSON的字符串(带""引号) struct 转换为JSON的Object,

随机推荐