posted at 2022.12.16 14:14 by Administrator
有些问题使用递归算法进行求解更容易理解，例如：计算阶乘、查找斐波那契数、解决棒料切割问题、在汉诺塔中移动圆盘、希尔伯特曲线绘制、八皇后及骑士巡游问题等。
遗憾的是，递归算法有一些不足之处，它虽然容易理解，但其效率却不高。例如生成斐波那契数时会使得计算机速度大大减慢。还有一些递归算法则会导致一系列递归方法的深度调用，从而耗尽调用堆栈，例如使用Warnsdorff启发式方法的骑士巡游问题，对于较大的棋盘会导致调用溢出错误。
幸运的是，我们可以采取一些方法来解决这个问题。
具体是：
一、 尾部递归的删除
该算法首先检查是否需要递归调用自己，或者是否可以简单地返回值1。
二、 动态规划（dynamic programming）
这项技术在20世纪50年代发明时可能看起来是动态的，但与其他基本上可以随时规划的神经网络、遗传算法和机器学习技术等现代技术相比，它似乎完全是静态的。该算法是在计算时记录中间结果值，这样就不需要重复进行计算。
三、 自底向上编程
即首先计算最小值，然后依次向上计算。
四、 传真（模拟程序在执行递归时所做的操作）
在进行递归调用之前，程序将当前状态的信息存储在调用堆栈中，
然后，当递归返回时，程序将从调用堆栈中弹出保存的信息，以便可以从停止的地方继续执行。
下面使用传真方法，构建非递归的希尔伯特曲线算法。
原始的希尔伯特曲线递归算法的伪代码：
Hilbert(Integer：depth, Float dx, Float dy) if (depth > 0) Then Hilbert(depth - 1, dy, dx); DrawRelative(dx, dy); if (depth > 0) Then Hilbert(depth - 1, dx, dy); DrawRelative(dy, dx); if (depth > 0) Then Hilbert(depth - 1, dx, dy); DrawRelative(-dx, -dy); if (depth > 0) Then Hilbert(depth - 1, -dy, -dx);
End Hilbert
我们将算法分成每次递归调用之前的各个节（section），并将其分别命名为1、2、3等。然后，创建一个名为section的变量，该变量指示算法下一步应该执行哪一节。最初将变量设置为1，以便算法从代码的第一节开始。
创建一个While循环，当section大于0时，重复执行。接下来，将算法的所有代码移到While循环中，并将其放入一系列If-Else语句中。使每条If语句将变量section与节编号进行比较，如果匹配，则执行相应代码。当算法进入某一节的代码时，递增变量section，以便算法知道下次循环时执行下一节代码。
当算法通常递归调用自己时，将所有参数的当前值推送到调用堆栈上。另外，将section推送到堆栈上，这样算法在从模拟递归返回时就知道要执行哪一节的代码。更新模拟递归应使用的所有参数。最后，设置section=1，从代码的第一节开始模拟递归调用。
具体C#代码：
using System;using System.Collections.Generic;using System.Drawing;using System.Windows.Forms;using System.Drawing.Drawing2D; namespace Hilbert{ Public partialclassForm1 : Form { public Form1() { InitializeComponent(); } privatevoid drawButton_Click(object sender, EventArgs e) { Bitmap bm = new Bitmap( hilbertPictureBox.ClientSize.Width, hilbertPictureBox.ClientSize.Height); using (Graphics gr = Graphics.FromImage(bm)) { gr.SmoothingMode = SmoothingMode.AntiAlias; gr.Clear(Color.White); constint margin = 10; int depth = (int)depthNumericUpDown.Value; float dx = (float)((bm.Width - 2 * margin) / (Math.Pow(2, depth + 1) - 1)); CurrentX = margin; CurrentY = margin; HilbertN(depth, gr, dx, 0); } hilbertPictureBox.Image = bm; } // The current position. privatefloat CurrentX, CurrentY; //绘制希尔伯特曲线 privatevoid HilbertN(int depth, Graphics gr, float dx, float dy) { // 创建堆栈存储递归前的信息 Stack<int> sections=new Stack<int>(); Stack<int> depths=new Stack<int>(); Stack<float> dxs=new Stack<float>(); Stack<float> dys = new Stack<float>(); //确定接下来执行哪一节的代码 int section = 1; while (section > 0) { if(section==1) { section++; if(depth > 0) { sections.Push(section); depths.Push(depth); dxs.Push(dx); dys.Push(dy); depth--; float temp = dx; dx = dy; dy = temp; section=1; } } elseif(section==2) { DrawRelative(gr,dx,dy); section++; if (depth > 0) { sections.Push(section); depths.Push(depth); dxs.Push(dx); dys.Push(dy); depth--; section = 1; } } elseif (section == 3) { DrawRelative(gr, dy, dx); section++; if (depth > 0) { sections.Push(section); depths.Push(depth); dxs.Push(dx); dys.Push(dy); depth--; section = 1; } } elseif (section == 4) { DrawRelative(gr, -dx, -dy); section++; if (depth > 0) { sections.Push(section); depths.Push(depth); dxs.Push(dx); dys.Push(dy); depth--; float temp = dx; dx = -dy; dy = -temp; section = 1; } } elseif (section == 5) { //8、9级曲线几乎填充整个计算机屏幕，不再递归//从递归返回 //如果没有任何数据弹出，则表明已到了栈顶 if (sections.Count == 0) { section = -1; } else { //弹出之前的参数 section=sections.Pop(); depth=depths.Pop(); dx=dxs.Pop(); dy=dys.Pop(); } } } } privatevoid Form1_Load(object sender, EventArgs e) { } // Draw starting at the indicated point and update x and y. privatevoid DrawRelative(Graphics gr, float dx, float dy) { gr.DrawLine(Pens.Blue, CurrentX, CurrentY, CurrentX + dx, CurrentY + dy); CurrentX += dx; CurrentY += dy; } }}namespace Hilbert{ staticclassProgram { [STAThread] staticvoid Main() { Application.EnableVisualStyles(); Application.SetCompatibleTextRenderingDefault(false); Application.Run(new Form1()); } }
}
效果图：
b0a1e705-5f1d-4c60-bf9c-656f81aa07d8|0|.0|96d5b379-7e1d-4dac-a6ba-1e50db561b04
Tags: 程序, 算法
IT技术
