递归问题思考

Question

public  class  recursivefactorial  {  
           public  static  int  factorial(int  n){  
           int  result;  
           if  (n==0)result=1;  
           else  result=n*factorial(n-1);  
           return  result;  
}  
 
           /**  
             *  @param  args  
             */  
           public  static  void  main(String[]  args)  {  
                       //  TODO  自动生成方法存根  
                         
for  (int  index=1;index<=6;index++){  
           System.out.println(index+"!="+factorial(index));  
}  
           }  
 
}  
/*如果n=6,我的理解:
result=6*factorial(5)
而factorial(5)=5*factorial(4)
...
factorial(1)=1
由下往上代入
阶乘问题，我感觉还可以理解，但是河内塔的问题我感觉很难理解了，按照程序的顺序原则，谁给我详细解说下啊，哎~数学向来很好的，是不是智力衰退了...郁闷啊，  */ 

Answer 1

函数的递归调用与分治策略
递归方法是算法和程序设计中的一种重要技术。递归方法即通过函数或过程调用自身将问题转化为本质相同但规模较小的子问题。递归方法具有易于描述和理解、证明简单等优点，在动态规划、贪心算法、回溯法等诸多算法中都有着极为广泛的应用，是许多复杂算法的基础。递归方法中所使用的“分而治之”的策略也称分治策略。递归方法的构造
构造递归方法的关键在于建立递归关系。这里的递归关系可以是递归描述的，也可以是递推描述的。下面由一个求n的阶乘的程序为例，总结出构造递归方法的一般步骤。[例1]从键盘输入正整数N（0<=N<=20），输出N!。[分析]N!的计算是一个典型的递归问题。使用递归方法来描述程序，十分简单且易于理解。[步骤1]描述递归关系 递归关系是这样的一种关系。设{U1,U2,U3,…,Un…}是一个序列，如果从某一项k开始，Un和它之前的若干项之间存在一种只与n有关的关系，这便称为递归关系。注意到，当N>=1时，N!=N*(N-1)!（N=1时，0!=1），这就是一种递归关系。对于特定的K!，它只与K与(K-1)!有关。[步骤2]确定递归边界 在步骤1的递归关系中，对大于k的Un的求解将最终归结为对Uk的求解。这里的Uk称为递归边界（或递归出口）。在本例中，递归边界为k=0，即0!=1。对于任意给定的N!，程序将最终求解到0!。确定递归边界十分重要，如果没有确定递归边界，将导致程序无限递归而引起死循环。例如以下程序：#include <iostream.h>int f(int x){  return(f(x-1));}main(){  cout<<f(10);}它没有规定递归边界，运行时将无限循环，会导致错误。[步骤3]写出递归函数并译为代码 将步骤1和步骤2中的递归关系与边界统一起来用数学语言来表示，即       N*(N-1)! 当N>=1时n!=      1        当N=0时再将这种关系翻译为代码，即一个函数：long f(int n){ if (n==0)   return(1); else   return(n*f(n-1));}[步骤4]完善程序 主要的递归函数已经完成，将程序依题意补充完整即可。//ex1.cpp#include <iostream.h>long f(int n){ if (n==0)   return(1); else   return(n*f(n-1));}main(){ int n; cin>>n; cout<<endl<<f(n);}

Answer 2

public class c
{
public static void main(String [] args)
{
int num =4;
System.out.println(fun(num));
}

public static int fun(int x)
{

if(x==1)
{
return x;
}

return x*fun(x-1);
}
}