1143_ SiCp learning notes_ Tree recursion

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

    A typical example of tree recursion is the solution of Fibonacci sequence , The above is a simple definition rule description . This description can be easily converted into a recursive function by code , The last screenshot of the above document is lisp How to implement .

    If the replacement model is used for expansion , This is the solution process of Fibonacci sequence . It can be seen from here that , Half the work is actually repetitive . In fact, it can be analyzed from the characteristics of the code itself , Because every recursion calls the function twice .

    This is an optimization of Fibonacci sequence solution , In fact, the optimization method is mainly aimed at the iterative part in the previous formula . In previous software design , The state saving and other work of these two parts are actually completely entrusted to the parser . And the improved way , Make a transition between the two maintenance states , In fact, the saving of some temporary information is not completely handled by the parser, but put into memory . The design of software is actually very easy to understand .

    This is a test of the above software design . Equivalent functions can also be easily used python To do a writing test .

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)

    The computational effect of both languages is the same . I also compared the solution method with the first scheme , Solve in the computer fib(100) The process is very long . And the improved way , In fact, it has good execution efficiency , Whether it's lisp still python.

    Here is another classic question ： The combination of coins . The disassembly of this problem is divided into two steps , Described as the colored part above . About this description , In my own understanding, I should consider this ： All the combination methods actually have 2 Kind of , One is that the first kind of coins are not used ; The other is the case of using at least one coin of the first kind . Then the case of using at least one coin of the first kind can be considered as the total amount minus the face value of one coin of the first kind , Any combination of the remaining amounts . such , It's easy to build the following recursive program .

    such , Basically finished reading the content of tree recursion . Through the study of this chapter , I still see a useful way of thinking . however , The realization of many laws or methods is actually supported by certain data theory to a great extent . look , Mathematics is also a very important tool and method .