1143_SICP学习笔记_树递归

    全部学习汇总：GitHub - GreyZhang/g_SICP: learn SICP and hack lisp.

    树递归的一个典型的例子是斐波那契数列的求解，上面是一个简单定义规则说明。这个描述很容易通过代码实现转换成一个递归的函数，上面文档截图最后就是lisp的实现方式。

    如果采用替换模型进行展开，这就是斐波那契数列的求解过程。从这里可以看出来，有一半的工作其实是重复的。从从代码本身的特点其实也能够多少分析出来，因为每一次递归都调用了两次函数。

    这是对斐波那契数列求解的一个优化，优化的方式其实主要针对前面公式中符合迭代的部分。之前的软件设计中，这两部分的状态保存等工作其实是完全交给了解析器。而改进的这种方式，把两个维护状态做了一个转换，这样部分临时信息的保存其实是脱离了完全由解析器来处理而是放到了内存。软件的设计其实是很好理解的。

    这是对上面的软件设计的一个测试。对等的功能也可以很容易用python的方式来做一个编写测试。

def fib(n):

    if n <= 1:

        return n

    else:

        return fib(n - 1) + fib(n - 2)

def fib_iter(a, b, n):

    if n == 0:

        return b

    else:

        return fib_iter(a + b, a, n - 1)

def new_fib(n):

    return fib_iter(1, 0, n)

    两种语言的计算效果都是一样的。我也对比了用第一种方案做的求解方式，在计算机中求解fib(100)的过程是十分漫长的。而改进后的方式，其实是有很好的执行效率的，无论是lisp还是python。

    这里给出了另一个经典的问题：钱币的组合问题。这个问题的拆解分为两步，描述为上面着色的部分。关于这个描述，用我自己的理解应该这么考虑：所有的组合方式其实是有2种，一种是一个第一种钱币都不用的情况；另一种是至少使用一个第一种钱币的情况。那么至少使用一个第一种钱币的情况其实可以认为是总额减去一个第一种钱币面额后，剩下的数额的任意组合情况。这样，很容易构建出来下面的递归程序了。

    这样，树递归的内容基本看完了。通过这一个章节的学习，还是看到了一点很有用的思维方式的。但是，很多规律或者方法的实现很多程度上其实是有一定的数据理论作为支持的。看起来，数学还是一个很重要的工具和方法。