文章目录

• 函数
• • 一：函数是什么？
  • 二：C语言中函数的分类
  • • 1：库函数
    • • （1）：库函数存在的意义：
      • （2）：库函数的学习与使用
    • 2：自定义函数
    • • （1）：自定义函数的组成
      • （2）：例题
      • • 例题一：写一个函数找出两个整数的最大值
        • 例题二：写一个函数交换两个整型变量的内容
  • 三：函数中的参数
  • • 1：实际参数(实参)
    • 2：形式参数(形参)
  • 四：函数的调用
  • • 1：传值调用
    • 2：传址调用
    • 3：练习
    • • （1）：写一个函数可以判断一个数是不是素数。
      • （2）：写一个函数判断一年是不是闰年。
      • （3）：写一个函数，实现一个整形有序数组的二分查找。
      • （4）：写一个函数，每调用一次这个函数，就会将 num 的值增加1
  • 五：函数的嵌套调用和链式访问
  • • 1.嵌套调用
    • 2.链式访问
    • • （1）：链式访问的经典例题
  • 六：函数的声明和定义
  • • 1：函数的声明
    • 2：函数的定义
    • 3：程序的分块化编写
  • 七：函数的递归
  • • 1：什么是递归
    • 2：递归的两个必要条件
    • • （1）：练习1：（画图讲解）
      • • 函数的栈帧与销毁
      • （2）：练习2：（画图讲解）
    • 3：函数的递归与迭代
    • • （1）：什么是迭代
      • （2）：优缺点
      • • 求第n个斐波那契数。（不考虑溢出）
        • 求n的阶乘
    • 4：函数递归经典问题
    • • （1）：汉诺塔问题
      • • 算法分析
      • （2）：青蛙跳台阶问题
      • （3）：青蛙跳台阶问题(进阶版)
      • • 题目(1)： 从前有一只青蛙想跳台阶去等峰，若该青蛙一次可以跳上1级台阶、也可以跳上2级……（n-1）级、n级。那么该青蛙跳上第n级的台阶时总共有多少种跳法。（前提是n个台阶会有一次n阶的跳法）
        • 题目(2)：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个m级的台阶总共有多少种跳法？

函数

一：函数是什么？

维基百科中对函数的定义：子程序
在计算机科学中，子程序（英语：Subroutine, procedure, function, routine, method, subprogram, callable unit）
（1）：是一个大型程序中的某部分代码， 由一个或多个语句块组成。它负责完成某项特定任务，而且相较于其他代码，具备相对的独立性。
（2）：一般会有输入参数并有返回值，提供对过程的封装和细节的隐藏。这些代码通常被集成为软件库。

二：C语言中函数的分类

（1）库函数：C语言内部提供的函数。
（2）自定义函数：自我发挥写出的函数。

1：库函数

（1）：库函数存在的意义：

1. 我们知道在我们学习C语言编程的时候，总是在一个代码编写完成之后迫不及待的想知道结果，想把这个结果打印到我们的屏幕上看看。这个时候我们会频繁的使用一个功能：
2. 将信息按照一定的格式打印到屏幕上（printf）。
3. 在编程的过程中我们会频繁的做一些字符串的拷贝工作（strcpy）。
4. 在编程是我们也计算，总是会计算n的k次方这样的运算（pow）。**
5. 为了提高我们的工作的效率,防止bug的出现,我们就引入了库函数

（2）：库函数的学习与使用

像上面我们描述的基础功能，它们不是业务性的代码。我们在开发的过程中每个程序员都可能用的到，为了支持可移植性和提高程序的效率，所以C语言的基础库中提供了一系列类似的库函数，方便程序员进行软件开发。

库函数的使用不需要专门去记，我们可以通过查找了解它们的使用方式。

这里推荐一个网站和一个应用程序

（1）www.cplusplus.com
（2）MSDN(Microsoft Developer Network)
（3）http://en.cppreference.com（英文版）
（4）http://zh.cppreference.com（中文版）
通过这些方式，我们可以查找到它们的信息，例如：函数名、形式参数、需要的头文件和返回值等必要的信息。

这些工具的语言都是英文，在学习编程的工程中我们需要学习英文，
下面来举两个库函数的例子

strcpy

char * strcpy ( char * destination, const char * source );

上面英文简单说明了目的地是返回值
加深的理解就是：
strcpy函数会把源头source的数据拷贝到目的地空间里面以后，会把目的地空间的起始地址给返回回来。

//strcpy的用法#include#includeint main(){char arr1[20] = { "xxxxxxxxxxxxxxx" };char arr2[]   = { "hello bit" };strcpy(arr1, arr2);//arr1为目的地,arr2为源头,为了将arr2数组里面的内容拷贝到arr1里面printf("%s\n", arr1);return 0;//arr1与t对齐的后面的x,也就是数组下标为9的x,被改成\0拷贝了过来//实际上打印的结果为hello bit(\0不显示但存在)}

memset(内存设置函数)

void * memset ( void * ptr, int value, size_t num );

补充:该值指的是num的字节数

//memset的用法#include#includeint main(){char arr[] = { "hello bit" };memset(arr, 'x', 5);printf("%s\n", arr);return 0;}//memset中间一定是unsigned char类型,5则表示arr数组里面前五个东西被x所取代

注：
但是库函数必须知道的一个秘密就是：使用库函数，必须包含 #include 对应的头文件。
这里对照文档来学习上面几个库函数，目的是掌握库函数的使用方法。

2：自定义函数

（1）：自定义函数的组成

自定义函数由程序员自主设计，和普通的函数一样有函数名、返回类型、形式参数等。

基本结构如下：

ret_type fun_name(para1, * ){    statement;//语句项}//ret_type 返回类型//fun_name 函数名//para1    函数参数

（2）：例题

例题一：写一个函数找出两个整数的最大值

//写一个函数找出两个整数的最大值#includeint get_max(int x, int y){    if (x > y)    {        return x;    }    else    {        return y;    }    //简便的代码,一行代替上面函数体里面的代码    //return(x > y " />
 假设他在VS环境下工作,点击 头文件，添加现有项，将上面两个代码文件添加过来
 这个游戏引擎恰好是李四想把它买过来的一个项目
 张三心想：我可以让你用，但我不想让你看到具体怎么实现的
 于是他点击
 
 
点击应用
 使用完后add.c里面的代码运行不起来
 

 这个add.lib文件就是张三写的游戏引擎的静态库
 李四买下来后打开来看add.lib文件,是一堆乱码,
 张三于是给他了一个使用说明书
 首先把lib文件放到这里来
 
 test.c的代码最终应该这样显示
 
#include "add.h"//引用头文件#pragma comment(lib, "add.lib")//加载引用静态库int main(){int a = 0;int b = 0;scanf("%d %d", &a. & b);int c = Add(a, b);printf("%d\n", c);return 0;}
七：函数的递归
1：什么是递归
程序调用自身的编程技巧称为递归(recursion).(递归也就是程序自己调用自己)
 递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接
 调用自身的
 一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，
 递归策略
 只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
递归的主要思考方式在于：把大事化小
下面介绍一个最简单的递归
#includeint main(){printf("hehe\n");main();return 0;}//死递归hehe,到最后程序因为栈溢出而自动跳出(挂掉了)
那什么时候会发生栈溢出(Stack overflow)呢？
 每一次函数的调用都会在栈区申请内存空间，而上面代码递归无限次申请，最终导致栈溢出.
2：递归的两个必要条件
存在限制条件，当满足这个限制条件的时候，递归便不再继续。
每次递归调用之后越来越接近这个限制条件。
（1）：练习1：（画图讲解）
接受一个整型值（无符号），按照顺序打印它的每一位
例如：输入：1234，输出 ：1 2 3 4
#includevoid print(unsigned int n){if (n > 9)//如果n是两位数的话{print(n / 10);//满足递归的两个必要条件}printf("%d", n % 10);}int main(){unsigned int num = 0;//无符号整型用%uscanf("%u", &num);//1234print(num);//按照顺序打印num的每一位return 0;}
下面我们来分析递归的过程
//递归的思考方式：大事化小////print(1234)//print(123) 4   //print(12) 3 4//print(1) 2 3 4//1 2 3 4//print(1234);//这个函数从上到下，先递进后回归//1234大于9，进入if语句,第一层print(1234){    if (n > 9)//n=1234,满足条件，进入if    {        print(123);    }    printf("%d ", n % 10);//第一层，n%10=4}//print(123)展开，n=123满足条件，继续进入下一层,接着递归print(123){    if (n > 9)//n/10=123,满足条件，进入if    {        print(12);    }    printf("%d ", n % 10);//第二层，n%10=3}//print(12)展开，n/10=1此时不满足条件，不会继续进入下一层的if语句print(12){    if (n > 9)//n=12,不满足条件，不进入if    {        print(1);    }    printf("%d ", n % 10);//第三层，n%10=2}print(1){    if (n > 9)//n=1,不满足条件，不进入if    {        print(0);    }    printf("%d ", n % 10);//第三层，n%10=1}//递归的“递”此时已经完成，我们将这个代码整理一下，查看它时如何“归”的print(1234){    {        {            {                printf("%d ", n % 10);//第四层，n%10=1            }            printf("%d ", n % 10);//第三层，n%10=2        }        printf("%d ", n % 10);//第二层，n%10=3    }    printf("%d ", n % 10);//第一层，n%10=4}//代码从第四层开始向外执行，故可以实现数字的按位打印//输出：1 2 3 4

 下面补充一点函数栈帧的知识点(修炼内功)(博主摸鱼王胖嘟嘟的文章写的详细且易懂，可以收藏一下)
函数的栈帧与销毁
这里我就简单讲一下
 之前提过寄存器的种类，我们现在再来回忆一下
eax：通用寄存器，保存临时数据，常用于返回值
ebx: 通用寄存器，保留临时数据
ebp：栈底寄存器
edp：栈顶寄存器
eip：指令寄存器，保存当前指令的下一条指令的地址
ebp与edp是用来维护函数栈帧的

 那函数具体怎么调用的呢？首先我们在VS里面按下F10，再点击反汇编，这个时候我们就能看到汇编代码。我们取消“显示符号名”，因为我们要观察内存地址的具体布局

 提示：
 1.dword是四个字节
 2.每一次初始化4个字节，总共初始化ecx次，最终初始化成eax,0CCCCCCCCh的内容
 3.push：压栈：给栈顶放一个元素
 pop：出栈：从栈顶删除一个元素

 从中我们可以发现，实际上我们根本没有定义形参
 我们通过mov,push指令进行传参（把b、c进行形参压栈压到[ebp+8],[ebp+0Ch(12)]中来）
 Add(a,b)是先传右边再传左边的。
 a’与b’（x与y）实际上就是a,b实参的临时拷贝
return z之后函数便开始销毁，下面我们可以看一下反汇编的代码
00C213F1 5F   pop   edi00C213F2 5E   pop   esi00C213F2 5B   pop   ebx//pop三次 相当于之前连续push三次的逆过程,连续在栈顶弹出值分别存放到edi,esi,ebx中//pop完后,这些空间没必要存在了,应该被销毁00C213F4 8B E5 mov  esp,ebp//mov将ebp赋给了esp,这个时候esp与ebp在同一个位置上00C213F6 5Dpop   ebp//把ebp pop出来之后ebp回到main函数的栈底,esp回到main函数的栈顶

 如图所示esp返回到main函数的栈顶了
00C213F7 C3 ret//ret指令的执行,跳到栈顶弹出的值就是call指令的下一条指令的地址//此时esp+4(pop了一下),栈顶的地址也弹出去了,esp指向了00C21450(call)的底部
调用完Add函数，回到main函数的时候，继续往下执行
00C21450 83 C4 08addesp,8//回到call指令的下一条地址,esp直接+8,把x,y形参的空间释放,esp这个时候指向edi的顶端00C21453 89 45 E0movdword ptr [ebp-20h],eax//把eax中的值,存放到[ebp-20h(也就是c)]里面去//函数的返回值是由eax寄存器带回来的
解读完后我们就可以解答以下几个问题
局部变量是怎么创建的？
 答：首先为函数分配好栈帧空间，空间里面初始化好一部分，然后给局部变量的栈帧空间里面分配一点空间。
为什么局部变量的值不初始化的时候是随机值？
 答：不初始化的话由于局部变量来自于main函数的栈帧，这里面的值是随机放进去的，初始化后就可以覆盖随机值了。
函数是怎么传参的？传参的顺序是怎么样的？
形参和实参的关系是什么样的？
 答：形参是实参的一份临时拷贝。
函数的调用时怎么做的？
 （3、5）答：当要去调用函数的时候，没调用之前就已经push，把(a,b)这两个参数从右向左开始压栈。当我们进入形参函数的时候，其实在Add函数的栈帧里面，通过指针的偏移量，找回了函数的形参。
函数调用结束后是怎么返回的？
 答：在调用之前我们就把call指令的下一条指令的地址给存放进去了，把ebp调用这个函数的上一个函数栈帧的ebp给存进去了，当函数调用完需要返回的时候，弹出ebp，就能找到上一个函数调用的ebp，指针往下(高地址)走的时候，就能走到esp的顶部，从而能够回到main函数的栈帧空间，之后，我们记住了call指令的下一条指令的地址，当我们返回的时候，我们就可以跳转到call指令的下一条指令的地址，让函数调用后可以返回，返回值通过eax寄存器方式带回来。
（2）：练习2：（画图讲解）
求字符串长度，下面介绍三种方法：
 方法一：
//方法一#include#includeint main(){char arr[] = { "abc" };int len = strlen(arr);printf("%d", arr);return 0;}
方法二：利用函数与循环
//方法二#includeint my_strlen(char* str){int count = 0;while (*str != '\0'){count++;str++;}return count;}int main(){char arr[] = { "abc" };int len = my_strlen(arr);printf("%d", len);return 0;}
方法三：递归(简便，不需要创建临时变量)
//strlen("abc");//1+strlen("bc");//1+1+strlen("c");//1+1+1+strlen("");//1+1+1+0=3#includeint my_strlen(char* str){if (*str != '\0'){//如果第一个字符不是"\0",则字符串至少包含一个字符//可以剥出来个1,str+1是下一个字符所指向的地址//空字符第一个是"\0"return 1 + my_strlen(str + 1);//注意:这里str++并不能代替str+1的作用//我们把str+1之后的地址传下去了,而留下来str还是原来的str.//因为str++是先使用再++,//那么根据原理传进去的str还是原来的str(原来是a的地址,传进去还是a的地址)//所以按照原理:++str能代替str+1的作用,但并不推荐这样做,//因为如果递归回来之后使用str的话,留下来的str不是原来的str了.}elsereturn 0;}int main(){char arr[] = { "abc" };int len = my_strlen(arr);printf("%d", len);return 0;}
方法三看上去代码很少，但实际上程序内部重复了大量的计算.
3：函数的递归与迭代
（1）：什么是迭代
迭代实际上就是重复，循环是一种特殊的迭代。
（2）：优缺点
函数递归中我们一层一层调用函数，它的优点是所需代码量少，简洁。但缺点主要有两个，一方面，大量重复的计算拖慢了程序的运行速度；另一方面，函数每一次被调用的时候都需要在栈区开辟相应的空间，当递归过深时可能会出现栈溢出。（栈区的空间已经被用完了，程序无法继续进行了）
当我们使用迭代时，循环不需要大量调用函数，重复的计算会少很多，这个程序的运行速度会加快不少，只是这个程序的代码量会大很多。
求第n个斐波那契数。（不考虑溢出）
//斐波那契数列//1 1 2 3 5 8 13 21 34 55 ....//方法一:递归法// n<=2 1//Fib1(n) // n>2 Fib1(n-1)+Fib1(n-2);//第三个数加第二个数#includeint Fib1(int n){//如果想知道某个斐波那契数究竟计算了多少次,可以设置一个全局变量count//if (n == k)//算第k个斐波那契数被计算了多少次//count++;if (n <= 2)return 1;elsereturn Fib1(n - 1) + Fib1(n - 2);}//int count = 0;int main(){int n = 0;scanf("%d", &n);int ret1 = Fib1(n);//定义一个ret来接受上面函数的返回值printf("%d", ret1);//printf("count=%d\n", count);return 0;}
求n的阶乘
//求n的阶乘//方法一:递归法//1*2*3=Fac(3)//1*2*3*4=Fac(3)*4// // n<=1  1//Fac(n)// n>1 n*Fac(n-1);#includeint Fac1(int n){if (n <= 1)return 1;elsereturn n * Fac1(n - 1);}int main(){int n = 0;scanf("%d", &n);int ret1 = Fac1(n);//定义一个ret来接受上面函数的返回值printf("%d", ret1);return 0;}
上面两个代码看似很简便，但实际运行的时候却发现了大问题：
在使用 Fib1 这个函数的时候如果我们要计算第50个斐波那契数字的时候特别耗费时间。
使用 Fac1函数求10000的阶乘（不考虑结果的正确性），程序会崩溃
为什么呢？
 在使用Fib函数的时候，当n=50的时候，光n=46就被计算(出现)了3次，这样会使得程序运行速度非常慢。
 在使用Fac1函数的时候，当求10000的阶乘的时候，会出现 stack overflow（栈溢出）的信息，系统分配给程序的栈空间是有限的，但是如果出现了死循环,或者(死递归),这样有可能导致一直开辟栈空间，最终产生栈空间耗尽的情况，这样的现象我们称为栈溢出。
那么我们怎么纠正这个问题呢？
 把递归改成非递归
 改正后的代码如下
//斐波那契数列//1 1 2 3 5 8 13 21 34 55 ....//方法二:迭代  #includeint Fib2(int n){int a = 1;//int b = 1;//前两个数都是1int c = 1;//对斐波那契数列中前两个数之和的第三个数初始化//不能令c=0,如果输入的n小于2,那直接return 0了,很显然不行while (n > 2)//第三个斐波那契数的时候开始循环{//1 1 2 3 5 8 13 21 34 55 ....////  //      a b c.....(斐波那契数前两个数之加赋给第三个数,以此类推...)//  a b c....//a b c....  c = a + b; //斐波那契数前两个数之加赋给第三个数a = b;b = c;n--;}return c;}int main(){int n = 0;scanf("%d", &n);int ret2 = Fac2(n);//定义一个ret来接受上面函数的返回值printf("%d", ret2);return 0;}
//求n的阶乘//方法二:迭代法int Fac2(int n){int i = 0;int ret2 = 1;//阶乘初始化必然为1for (i = 1; i <= n; i++){ret2 = ret2 * i;}return ret2;}int main(){int n = 0;scanf("%d", &n);int ret2 = Fac2(n);//定义一个ret来接受上面函数的返回值printf("%d", ret2);return 0;}
提示：
许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。
但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。
当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。
4：函数递归经典问题
（1）：汉诺塔问题
一．起源：
 　　汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
二．抽象为数学问题：
 　　如下图所示，从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数
（1）n == 1
第1次 1号盘 A---->C sum = 1 次
(2) n == 2
第1次 1号盘 A---->B
 第2次 2号盘 A---->C
 第3次 1号盘 B---->C sum = 3 次
（3）n == 3
第1次 1号盘 A---->C
 第2次 2号盘 A---->B
 第3次 1号盘 C---->B
 第4次 3号盘 A---->C
 第5次 1号盘 B---->A
 第6次 2号盘 B---->C
 第7次 1号盘 A---->C sum = 7 次
不难发现规律：1个圆盘的次数 2的1次方减1
2个圆盘的次数 2的2次方减1
 3个圆盘的次数 2的3次方减1
 。 。 。 。 。
 n个圆盘的次数 2的n次方减1
故：移动次数为：2^n - 1
算法分析
（步骤1）　　如果是一个盘子
直接将a柱子上的盘子从a移动到c
否则
（步骤2）　　　　 先将a柱子上的n-1个盘子借助c移动到b（图1），
肯定没有c柱子是不能移动的，已知函数形参是hanoi(int n,char a,char b,char c)。
代表将a柱子上的盘子借助c柱子移动到b柱子，这里调用函数的时候是将a柱子上的n-1个
盘子借助c柱子，移动到b柱子。所以这里需要将位置调换一下hanoi(n-1,a,c,b)。
（步骤3）　　　　此时移动完如图1，但是还没有移动结束，首先要将a柱子上的最后一个盘子（第n个）盘子直接移动到c（图2）
 
 （步骤4）　　　　最后将b柱子上的n-1个盘子借助a移动到c（图3）
// 汉诺塔#includevoid hanoi(int n, char a, char b, char c)//这里代表将a柱子上的盘子借助b柱子移动到c柱子{if (1 == n)//如果是一个盘子直接将a柱子上的盘子移动到c{printf("%c-->%c\n", a, c);}else{hanoi(n - 1, a, c, b);//将a柱子上n-1个盘子借助c柱子，移动到b柱子printf("%c-->%c\n", a, c);//再直接将a柱子上的最后一个盘子移动到chanoi(n - 1, b, a, c);//然后将b柱子上的n-1个盘子借助a移动到c}}int main(){int n = 0;printf("请输入需要移动的圆盘个数:");scanf("%d", &n);hanoi(n, 'A', 'B', 'C');//移动A上的所有圆盘到C上return 0;}
（2）：青蛙跳台阶问题
（1）问题描述
 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
任务：青蛙跳上一个 n 级的台阶总共有多少种跳法。
规定：青蛙一次可以跳一个或两个台阶。
（2）问题分析
 当n = 1时， 有1种跳法；
 当n = 2时，青蛙跳一级再跳一级；青蛙直接跳上两级。有2种跳法；
 当n = 3时，青蛙跳一级三次；青蛙跳一级再跳两级；青蛙跳两级再跳一级，有3种跳法；
 当n = 4时，有5种跳法；
 当n = 5时，有8种跳法；…
规律类似于Fibonacci数列
 
 （3）递归结束的判断
比如说，青蛙需要跳上五级台阶。
为了找到五级台阶的种数，我们需要找到四级台阶和三级台阶的数值。
为了找到四级台阶的种数，我们需要找到三级台阶和二级台阶的数值，此时其中一个数值不需要递归了。
为了找到三级台阶的种数，我们需要找到二级台阶和一级台阶的数值，此时另一个数值也不需要递归了。
此时，我们的递归此时就可以中断了，所以我们得到递归终止的判断依据：柱1上的圆盘数小于等于一时，跳出递归。
//青蛙跳台问题#include//或者运用void函数,但之前要定义一个全局变量count//int count = 0;//创建全局变量来统计个跳法个数//void frog_jump(int n)//{//if (n == 0)//当台阶数为0是跳法个数加1//count++;//else if (n < 0);//else//{//frog(n - 1);//frog(n - 2);//}int frog_jump(int n){//int sum = 0;if (1 == n)//等于1时，sum=1{return 1; //sum += 1}else if (2 == n)//等于2时，sum=2{return 2;//sum += 2;}else//大于3时，开始递归{return frog_jump(n - 1) + frog_jump(n - 2);//sum = frog_jump(m - 1) + frog_jump(m - 2);}//return sum;}int main(){int n = 0;printf("请输入台阶的个数:");scanf("%d", &n);int ret = frog_jump(n);printf("一共有%d种跳法\n", ret);return 0;}
（3）：青蛙跳台阶问题(进阶版)
题目(1)： 从前有一只青蛙想跳台阶去等峰，若该青蛙一次可以跳上1级台阶、也可以跳上2级……（n-1）级、n级。那么该青蛙跳上第n级的台阶时总共有多少种跳法。（前提是n个台阶会有一次n阶的跳法）
（1）解题思路：
若n为1级台阶：f(1) = 1 (只可能有一种跳法)
 若n为2级台阶：f(2) = f(2 - 1) + f(2 - 2)（会有两个跳台阶的方法，一次1阶或者一次2阶）
 若n为3级台阶：f(3) = f(3 - 1) + f(3 - 2) + f(3 - 3)（会有三种跳台阶的方法，一次1阶、2阶、3阶）
 ……
 ……
 若n为(n - 1)级台阶：
f(n-1) = f((n-1)-1) + f((n-1)-2) + … + f((n-1)-(n-2)) + f((n-1)-(n-1))
 f(n-1) = f(0) + f(1)+f(2)+f(3) + … + f((n-1)-1)
 f(n-1) = f(0) + f(1) + f(2) + f(3) + … + f(n-2)
若n为n级台阶：
f(n) = f(n-1) + f(n-2) + f(n-3) + … + f(n-(n-1)) + f(n-n)
 f(n) = f(0) + f(1) + f(2) + f(3) + … + f(n-2) + f(n-1)
结合f(n-1)和f(n)的情况你会发现f(n) = f(n-1) + f(n-1)，所以可得： f(n) = 2*f(n-1)。
#includeint frog_jump_step(int n){if (n <= 1){return 1;}elsereturn 2 * frog_jump_step(n - 1);}int main(){int n = 0;printf("请输入青蛙应该跳的台阶个数:");scanf("%d", &n);int sum = frog_jump_step(n);printf("一共有种%d种跳法\n", sum);return 0;}
题目(2)：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个m级的台阶总共有多少种跳法？
（1）解题思路
 与上面不太一样的情况就是最后青蛙跳的台阶不是n级，所以可能会出现跳过了的现象。
 先列多项式：
 f(n) = f(n-1) + f(n-2) + f(n-3) + … + f(n-m)
 f(n-1) = f(n-2) + f(n-3) + … + f(n-m) + f(n-m-1)
 化简得：f(n) = 2f(n-1) - f(n-m-1)
#includeint frog_jump_step(int n,int m){if (n > m){return 2 * frog_jump_step(n - 1, m) - frog_jump_step(n - 1 - m, m);}else{if (n <= 1){return 1;}elsereturn 2 * frog_jump_step(n - 1);}}int main(){int n = 0;int m = 0;printf("请输入青蛙应该跳的台阶个数:");scanf("%d", &n);int sum = frog_jump_step(n, m);printf("一共有种%d种跳法\n", sum);return 0;}