本文主要是介绍有关于递归函数的一些学习记录（Recursion）走楼梯，递归找出最两个数的大公约数，汉诺塔问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题一：说，一个人在爬一个楼梯时，一次可以走一个台阶也可以走两个台阶，问这个人走到第九个台阶有多少种走法？
这是我在2013年春参加南京大学计算机系研究生复试的时候，被问到了这样一个问题，
如果我们不能用递归的思想来解决此类问题的话，这类问题的复杂程度可想而知。若我们理清思路，可得：
当楼梯为第 n=1层时，只有1种走法；当n=2层时，会有两种走法；
所以 f(1)=1;f(2)=2;
而当一个人处于第n层时，它可由第n-1层用一 步迈上去，也可以由第n-2层，1步迈两层上去。所以 f(n)=f(n-1)+f(n-2);
这里可能会有人疑问说，当位于第n-2层时不是由两种迈步的方法吗？要明白的是，当用户在第n-2层只迈一步的时候调到第n-1层，这是f(n-1)里面的问题了，故走到第n层的走法就是走到第n-1层加上第n-2层的走法所以
f(n)=f(n-1)+f(n-2);然后用递归函数就解出来了，这里给出函数的实现。这个问题的原形页就是fibonacci的实现问题。
int step(int n)
{if(n==1||n==2) return n;elsereturn step(n-1)+step(n-2);
}两个数的最大公约数就是可以同时整除这两个数的最大的约数，一般的求法是找到这两个数（设为X,Y）的较小的一个值并赋值给一个变量temp,然后temp依此减小一，直到可以同时被Ｘ，Ｙ整除，这里通过循环很容易就可以实现。
下面来介绍怎样通过递归来实现：
根据经典的欧几里得算法也称作（辗转相除算法）两个正整数（ａ，ｂ）假如a<b，的最大公约数c也是b%a与a的最大公约数，因为b=(b/a)*a+b%a,所以若a和b%a均可整除c,则(b/a)*a也可整除c,从而b也可整除c.又c是a的最大约数，则c也是a和b的最大公约数，所以通过辗转相除可实现递归算法：
int getcd(int a ,int b)
{
return (b==0)?a:getcdd(b,a%b);
}
（1）将n-1个盘子从A->C;
void hanoi(char x,char y,char z,int n)
{
if(n==1)
cout<<"1:"<<<"->"<<"<<
这篇关于有关于递归函数的一些学习记录（Recursion）走楼梯，递归找出最两个数的大公约数，汉诺塔问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
