黑马程序员技术交流社区

标题: 递归算法 [打印本页]

---

作者: 赵刘滨    时间: 2012-8-10 15:32
标题: 递归算法
什么是递归算法？（麻烦用代码说明下）

---

作者: 柏森仁    时间: 2012-8-10 15:34
c#题目如下:
要求输出:1,2,3,5,8,13,21,34,55,89
写法一:
public class MyClass
{
        public static void Main()
        {
                int[] cSum = new int[10];
        string sSum="";
        for (int i = 0; i < cSum.Length; i++)
        {
                        if(i==0)
                        {
                                cSum[i]=1;
                                sSum=""+cSum[i];
                        }
                        else if(i==1)
                        {
                                cSum[i]=cSum[i-1]+cSum[i-1];
                                sSum=sSum+','+cSum[i];
                        }
                        else
                        {
                                cSum[i]=cSum[i-1]+cSum[i-2];
                                sSum=sSum+','+cSum[i];
                        }
                }
                //输出结果1,2,3,5,8,13,21,34,55,89,普通写法
                Console.WriteLine(sSum);
                Console.ReadKey();
        }
}
Snippet Compliler调试通过
这样写虽然能实现，但是感觉不大好，重构，用递归写法
写法二:
public class MyClass
{
        public static void Main()
        {
                int[] cSum= new int[10];
                string sSum="";
                for(int j=0;j<cSum.Length;j++)
                {
                        cSum[j]= process(j);
                        if(sSum!="")
                        {
                                sSum=sSum+',';
                        }
                        sSum+=cSum[j];
                }
                //输出结果1,2,3,5,8,13,21,34,55,89,递归写法
                Console.WriteLine(sSum);
                  Console.ReadKey();   
        }
       
        public static int process(int i)
        {
                int s;
                if(i==0||i==1)
                {
                        s=i+1;
                }
                else
                {
                        s=process(i-1)+process(i-2);
                }
                return s;
        }
}
通过递归算法重构了写法一
下面留个题目，要求输出:1,1,2,3,5,8,13,21,34,55
写法三:
public class MyClass
{
        public static void Main()
        {
                         int[] cSum = new int[10];
            string sSum="";
            for (int i = 0; i < cSum.Length; i++)
            {
                                if(i==0||i==1)
                                {
                                        cSum[i]=1+cSum[i];
                                        if(sSum!="")
                                        {
                                                sSum+=",";
                                        }
                                        sSum+=cSum[i];
                                }
                                else
                                {
                                        cSum[i]=cSum[i-1]+cSum[i-2];
                                        sSum=sSum+','+cSum[i];
                                }
                        }
                        //输出结果1,1,2,3,5,8,13,21,34,55
                        Console.WriteLine(sSum);
                        Console.ReadKey();
        }
}

---

作者: 郑小杰    时间: 2012-8-10 17:07
递归是一种编程手法，简单的说就是函数自身调用自身，下边给你来一个求1+2+3+.....和的代码，很容易理解的

1. public static void main(String[] args) {
   
2.                 // TODO Auto-generated method stub
   
3.         int sum = getSum(100);
   
4.         System.out.println("sum="+sum);
   
5.         }
   
6.        
   
7.         public static int getSum(int n)
   
8.         {
   
9.                 if(n==1)
   
10.                         return 1;
    
11.                 return n+getSum(n-1);
    
12.         }
    
13. }

复制代码

---

作者: 王龙喜    时间: 2012-8-10 17:10
我感觉递归较接近思维的方式,用于解一些光用循环解起来较复杂的问题
例1.阶乘(算比较有特点的了)
计算x!
一般循环就是
int multi = 1;
if (x <=1) return (1);
for(int i=1;i<=x;i++)
  multi = multi*i;
return(multi);

递归把x！看作x*(x-1)!
int multi(int x)
{
if(x==0||x==1) return 1;
else return x*multi(x-1);
}
这样就能把x！算出来

例2 最著名的就是汉诺塔了
你可以网上找点资料看看

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2