算法之递归思维

算法之递归思想

树的遍历的实现就是典型的递归思想。

/*
*   description:树的遍历示例，递归
*               访问顺序：
*               前序： 当前节点 - 左子树   - 右子树
*               中序： 左子树   - 当前节点 - 右子树
*               后序： 左子树   - 右子树   - 当前节点
*
*   writeby:    nick
*   date:       2012-10-22 23:56
*/
#include <iostream>

using namespace std;

struct node 
{
    int item;
    node *l, *r;
    node(int n)
    {item=n; l=0; r=0;}
};
typedef node *link;

//前序遍历
void pretraverse(link h, void visit(link))
{
    if(h==0) return;
    visit(h);
    pretraverse(h->l, visit);
    pretraverse(h->r, visit);
}

//中序遍历
void midtraverse(link h, void visit(link))
{
    if(h==0) return;
    midtraverse(h->l, visit);
    visit(h);
    midtraverse(h->r, visit);
}

//后序遍历
void posttraverse(link h, void visit(link))
{
    if(h==0) return;
    posttraverse(h->l, visit);
    posttraverse(h->r, visit);
    visit(h);
}

void visit(link p)
{
    cout << p->item << " ";
}

int main()
{
    link root = new node(4);
    root->l = new node(5);
    root->r = new node(6);
    cout << "先序遍历：";
    pretraverse(root, visit);

    cout << endl << "中序遍历：";
    midtraverse(root, visit);

    cout << endl << "后序遍历：";
    posttraverse(root, visit);
    
    return 0;
}

一：概念

递归，说白了就是直接或者间接的调用自己的一种算法。它是把求解问题转化为规模较小的子问题，然后通过多次递归一直到可以得出结果

的最小解，然后通过最小解逐层向上返回调用，最终得到整个问题的解。总之递归可以概括为一句话就是：“能进则进，不进则退”。

二：三要素

<1> 递归中每次循环都必须使问题规模有所缩小。

<2> 递归操作的每两步都是有紧密的联系，如在“递归”的“归操作时”，前一次的输出就是后一次的输入。

<3> 当子问题的规模足够小时，必须能够直接求出该规模问题的解，其实也就是必须要有结束递归的条件。

三：注意

<1> 前面也说了，递归必须要有一个递归出口。

<2> 深层次的递归会涉及到频繁进栈出栈和分配内存空间，所以运行效率比较低，当问题规模较大时，不推荐使用。

<3> 在递归过程中，每次调用中的参数，方法返回点，局部变量都是存放在堆栈中的，如果当问题规模非常大时，容易造成堆栈溢出。

四：举二个例子

<1> 相信大家在初中的时候都学过阶乘吧，比如:5!=5*4*3*2*1

思路：根据上面的阶乘特征很容易我们就可以推导出n!=n*(n-1)*(n-2)....*2*1，

那么进一步其实就是: n!=n*(n-1)! ，

(n-1)!=(n-1)*(n-2)!。

显然他是满足递归的三要素，当n的规模不大时，我们可以用递归拿下。

 1 static void Main(string[] args)
 2         {
 3             while (true)
 4             {
 5                 //阶乘问题
 6                 Console.WriteLine("\n请输入一个求阶乘的一个数：");
 7 
 8                 int num = int.Parse(Console.ReadLine());
 9 
10                 Console.WriteLine("\n阶乘的结果为：" + fact(num));
11             }
12         }
13 
14         static int fact(int n)
15         {
16             if (n == 1)
17                 return 1;
18 
19             return n * fact(n - 1);
20         }

算法之递归思维

第一次：输入5的时候能够正确求出。

第二次：输入10的时候求出来竟然362万之多，可见多恐怖，如果俺们的时间复杂度是n!，那程序也就Game Over了，

第三次：输入100，已经超过了int.MaxValue了，

第四次: 输入10w，蹦出著名了“堆栈溢出”，好家伙，我们知道“递归”在程序中使用“栈”的形式存放的，每一次“递归”中，方法的返回值

包括函数中的参数都会存放在栈中，C#中每个线程分配的栈空间为1M，所以当N的规模非常大时，就把栈玩爆了。

<2> 在大一时上计算机文化基础的时候我们就接触过”进制转换问题“，比如将”十进制“转化为”二进制“。

思路：采用除2取余法，取余数为相应二进制数的最低位，然后再用商除以2得到次低位.......直到最后一次相除商为0时得到二进制的最高位，

比如(100)₁₀=(1100100)_2，仔细分析这个问题，会发现它是满足”递归“的三要素的，

① 进制转换中，数据规模会有所缩小。

② 当商为0时，就是我们递归的出口。

所以这个问题我们就可以用递归拿下。

  static void Main(string[] args)
        {
            Console.WriteLine("请输入一个十进制数：");

            int num = int.Parse(Console.ReadLine());

            string result = string.Empty;

            Console.WriteLine("转化的二进制为：" + ConvertToBinary(ref result, num));

            Console.ReadLine();

        }

        static string ConvertToBinary(ref string str, int num)
        {
            //递的过程
            if (num == 0)
                return string.Empty;

            ConvertToBinary(ref str, num / 2);

            //归的过程
            return str += (num % 2);
        }

算法之递归思维

来自一线码农博客园

算法之递归思维

相关推荐