1146_ SiCp learning notes_ exponentiation

    All learning summary ： https://github.com/GreyZhang/g_SICP

    This is the solution of a power operation , The recursive method is used to realize . According to my experience over the years , In fact, for similar solutions, I may first think of an iterative algorithm . I think SICP I have been talking about recursive algorithms because recursion is more in line with the thinking of computers , Many derivation processes are actually completed by the computer itself . Iterative calculation , In fact, more often than not, it is a process of repetition .

    This is the implementation of a linear iteration , In fact, it seems that there is also a self calling process , But this is the same as before n The algorithm for the product of natural numbers is similar . Think from the perspective of process storage , It's actually an iteration . Because the process of calculation is not passed through the unsolved function , But through intermediate variables .

    This is an interesting implementation , Same implementation , I can use C Write it in language . About the following ：

#include "stdio.h"

#include "stdint.h"

uint32_t expt(uint32_t b, uint32_t n);

static void expt_iter(uint32_t b, uint32_t *p_counter, uint32_t *p_product);

uint32_t expt(uint32_t b, uint32_t n)

{

    uint32_t result = 1U;

    uint32_t n_temp = n;

    expt_iter(b, &n_temp, &result);

    return result;

}

static void expt_iter(uint32_t b, uint32_t *p_counter, uint32_t *p_product)

{

    if(*p_counter == 0U)

    {

        return;

    }

    else

    {

        *p_counter -= 1U;

        *p_product *= b;

        expt_iter(b, p_counter, p_product);

    }

}

int main(void)

{

    printf("2 ** 5 = %d\n", expt(2, 5));

    printf("2 ** 10 = %d\n", expt(2, 10));

    return 0;

}

    The test results are as follows ：

    The software design above , Pointer is used to operate external storage , This will make debugging more convenient . Of course, software can also be completely copied lisp The pattern of ：

#include "stdio.h"

#include "stdint.h"

uint32_t exp(uint32_t b, uint32_t n);

uint32_t exp_iter(uint32_t b, uint32_t counter, uint32_t product);

uint32_t exp_iter(uint32_t b, uint32_t counter, uint32_t product)

{

    if(counter == 0U)

    {

        return  product;

    }

    else

    {

        return exp_iter(b, counter - 1, b * product);

    }

}

uint32_t exp(uint32_t b, uint32_t n)

{

    exp_iter(b, n, 1);

}

int main(void)

{

    printf("%d\n", exp(2, 5));

    printf("%d\n", exp(2, 10));

    return 0;

}

    The actual value of such a function may not be very great , Especially for accurate data calculation , After all C The language has data type restrictions on computation, which may overflow . I test using operations that programmers are very familiar with , In this way, we can know whether the calculation result is correct or not at once . that , Why is such a design not recursive but iterative ？ Actually , There is a self calling process , But repeated self invocation is just a simple rule . In the process of repetition , The return result of the last function will not be used . such , The whole process is actually a process of modifying external storage according to rules . The recursive solution is cleverly transformed into an iterative process .

    Here is an optimization process , Let the complexity of calculation change from exponent to logarithm . The handling method is also very clever , Classify according to the attributes of odd and even numbers . And every time you deal with , A further simplification of computational complexity is made , It further reduces the content of recursion . Such a treatment is really worth considering , We will repeatedly consider various dichotomy when dealing with various logic 、 Calculation methods such as substitution operation . In fact, before large-scale programming , Similar ideas in basic algorithms can also be adopted . in the course of time , Our software design will definitely be a qualitative leap from thinking to quality .

    If it is not easy to use iteration to realize the recursive algorithm of transformation, the recursive design is generally selected when designing , If the algorithm is easy to transform or easy to realize through iteration at a glance, it is actually easy to realize none for perhaps while Algorithm of loop . This is actually easy to understand from another perspective , Exclusion algorithm implementation , From the perspective of programming language, the premise of software implementation is Turing completeness . And in the complete Turing expression mode , In fact, there is no necessary requirement for these two expressions .