首页 > 代码库 > 从二叉树改链表引发的递归二三想

从二叉树改链表引发的递归二三想

递归其实就是寻找通项公式,但是通项公式可以有轻微的区别。

比如二叉树改链表(只调整箭头方向)这件事情,用以下两种方法都可以实现。


方法1: 从根开始 (1)调整左子树 (2)调整右子树  (3)(如何调整)左子树的最大值连接 自身,右子树的最小值连接自身

方法2:从根开始  (1)返回左子树最大值连接自身 (2)返回右子树最小值连接自身 (3)(如何返回值)如果是来自左子树,返回最大值,如果是来自右子树,返回最小值  

(4)  递归调整左右子树 

 进而可以简化为 :

(1)调整左子树,并返回最大值连接自身  (2)调整右子树,并返回最小值连接自身 (3)(如何返回值)如果是来自左子树,返回最大值,如果是来自右子树,返回最小值


总体上,方法1和方法2差别不大,但由于想法的不同,递归函数会有轻微的差别,比如方法1不需要带返回值,方法2则需要返回值。

不过万变不离其宗,递归有一种分而治之的感觉

本来要解决一个大问题    解决(大问题),但是直接将所有实现写在函数体内部可能会比较头疼,于是,将

 解决(大问题) 转化为 => 解决 ( 小问题1), 解决 (小问题2),  解决 (小问题3)

而解决小问题又可以进一步的分解为 解决(小小问题1) 解决 (小小问题 2)  解决(小小问题3)

当然,到了这一步还只是相当于将一句大空话分成了几句小空话,没什么营养,最终还是需要的是将具体的解决方案写出来。

然而,当分解达到一定的程度,需要写出的解决方法只是针对一个很小很小的问题,这时就很容易写出了。

到了这一步,还是缺了点意思,就好像把一盒沙子泼在地上,成为一盘散沙,然后根据情况一个一个处理,依然费时费力。

如果,所有的的沙子具有一样的结构,所有的处理方法也有一样的步骤,那么这时就有意思了。

      void fix(main)
        {
            fix1(main_part1);
            fix2(main_part2);
            fix3(main_part3);
        }

        void fix1(main_part1)
        {
            fix11(main_part1_part1);
            fix12(main_part1_part2);
            fix13(main_part1_part3);
        }

        void fix2(main_part2)
        {
            fix21(main_part2_part1);
            fix22(main_part2_part2);
            fix23(main_part2_part3);
        }

        void fix3(main_part3)
        {
            fix31(main_part3_part1);
            fix32(main_part3_part2);
            fix33(main_part3_part3);
        }

当结构一致,方法一致的时候,以上的一堆函数就可以简化为

        void fix(main)
        {
            fix(main_part1);
            fix(main_part2);
            fix(main_part3);
        }

程序突然变得如此的简单。


当我们要处理的对象群具有一致的结构(因此可以实现同样的分割或者递推),而对每个对象的处理的方法又一致的时候,递归往往是不错的选择,可以很好的简化程序。当然,程序是简化了,大量的堆栈资源开销已经可能的重复运算都是在使用递归时需要考虑的问题。比如经典的斐波那契递归解法就并不高校,因为包含了大量的重复计算。这时,使用几个int和for循环来解决就是更好的做法。


最后突然想到,吃拉面的时候,师傅的双手其实就是一个递归函数。将大面团 (1)折叠 (2)拉长 往复循环,最终当面条的韧性和样子达到师傅满意的终止条件时,函数结束。

做面 (面团)

{

     做面 (面团-1);

     做面 (面团-2);//面团变为面团1和面团2通过折叠实现。各种面团具有一致的结构,因此可以通过重复的折叠方法实现分割。

     拍打拉长 ();

}


本文仅是博主无聊时的碎碎想,写得不好的地方,还请轻拍。