1142_ SiCp learning notes_ Functions and processes created by functions_ Linear recursion and iteration

    All learning summary ：GitHub - GreyZhang/g_SICP: learn SICP and hack lisp.

    The first said , The title is named after the translation and adjustment of text information . If combined C language , It is more suitable to call it subfunction or function function combined by subfunction .

    This is the opening word of this chapter , But there are some interesting things to think about . such as , As a professional programmer, you need to have a more vivid and specific thinking ability . In the process of becoming a professional , Must learn how to deal with different scenes to deal with the image 、 Specific thinking . We need to describe the whole function in the way of this sub function 、 Global information and behavior . natural , Many sub functions will have their own state information to be maintained .

    This is a recursive factorial function implementation , The following figure is a specific description of each step using the replacement method .

    And this , It is an iterative implementation and deployment description . Judge the difference between recursion and iteration , The main difference is whether the intermediate state of the program is automatically processed by the parser rather than whether the function is called by itself . This point , I didn't think deeply when dealing with other designs before .

    According to this idea , In fact, you can design one according to the gourd and the gourd C Language version of “ Recursive iteration ”：

#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;

}

    test ：

    In the test above , Added one python Comparison of . among ,python Is a completely recursive implementation ：

def fac(n):

    if n == 1:

        return 1

    else:

        return n * fac(n - 1)

print(fac(5))

print(fac(10))

print(fac(12))

    Judging from the test results , Within a certain parameter range , This C The version calculation of is still correct .

    As the level of recursion increases , The information that the parser needs to track increases linearly . This process is called linear recursion . As the depth of recursion increases , More and more information needs to be managed and maintained . therefore , The above two processing ideas ： Recursion and iteration should not only focus on the processing depth in the replacement model when comparing the resource consumption of their algorithms , We should also pay attention to the horizontal expansion width . Vertical represents mainly time consumption , The horizontal actually involves the consumption of time and storage resources .

    But recursion does not necessarily meet such conditions , This is why the recursion discussed here is specifically proposed as linear recursion . And through the expansion of the end part , In fact, there is also a recursive method with basically constant resource consumption , For example, tail recursion . For me, , This is indeed another new concept .