1142_SICP学习笔记_函数以及由函数创建的进程_线性递归以及迭代

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

    首先说，这个标题的命名来自于文本信息的翻译和调整。如果结合C语言来说，更加合适的叫法或者是子函数以及由子函数组合出来的功能函数。

    这算是这个章节的开篇词了，不过里面有几个比较有意思的东西值得思考。比如，作为一个专业的程序员其实得有一个比较形象具体的思考能力。在迈向专业的过程中，必须学会如何应对不同的场景进行相应处理的形象、具体化的思维。我们需要通过这种子功能的方式来描述一个功能的整体、全局信息以及行为。自然，很多子函数里面会有自己需要维护的状态信息。

    这是一个递归阶乘的函数实现，下面的图是使用替换法针对每一个步骤进行展开的具体描述。

    而这个，是一个迭代的实现以及展开描述。判断递归以及迭代的差异，主要的差一点其实是在于程序运行的中间状态是否利用了解析器来自动处理而不是看函数是否被自己调用。这一点，之前我在处理其他设计的时候其实是没有做一个深刻思考的。

    按照这样的理念，其实可以依葫芦画瓢设计一个C语言版本的“递归迭代”：

#include

#include

void fac(uint32_t n, uint32_t *p_counter, uint32_t *p_result)

{

    if(*p_counter > n)

    {

        /* result is stored to the memory @ p_result */

        return;

    }

    else

    {

        *p_result *= *p_counter;

        *p_counter += 1U;

        fac(n, p_counter, p_result);

    }

}

int main(void)

{

    uint32_t n = 5;

    uint32_t c = 1U;

    uint32_t r = 1U;

    fac(n, &c, &r);

    printf("result is %d\n", r);

    n = 10;

    c = 1U;

    r = 1U;

    fac(n, &c, &r);

    printf("result is %d\n", r);

    n = 12;

    c = 1U;

    r = 1U;

    fac(n, &c, &r);

    printf("result is %d\n", r);

    return 0;

}

    测试：

    上面的测试中，增加了一个python的对比。其中，python是一个完全递归的实现：

def fac(n):

    if n == 1:

        return 1

    else:

        return n * fac(n - 1)

print(fac(5))

print(fac(10))

print(fac(12))

    从测试的结果看，在一定的参数范围内，这个C的版本计算还是正确的。

    随着递归的层级增加，解析器需要追踪的信息线性膨胀增加。这种处理的过程叫做线性递归。随着递归的深度增加，越来越多的信息需要去管理维护。因此，上面两种处理思路：递归以及迭代在对比其算法的资源消耗的时候不应该仅仅关注替换模型中的处理深度，还得关注横向的扩展宽度。纵向代表的主要是时间消耗，而横向其实涉及到时间消耗的同时还多了一个存储资源的消耗。

    但是递归也不一定一定符合这样的条件，这也是为什么这里探讨的递归专门提出来是线性递归。而通过结束部分的拓展部分，其实也有资源消耗基本不变的递归方式，比如说尾递归。对我来说，这的确又是一个新的概念。