精华内容
下载资源
问答
  • 3.7 是否可以安全地认为,一旦&&和||左边表达式已经决定了整个表达式结果,则右边表达式不会被值? 3.8 为什么表达式printf("%d%d",f1(),f2());先调用了f2?我觉得逗号表达式应该确保从左到右的求值顺序。...
  • 考虑递归执行效率低,可以尝试将递归过程转换为非递归过程。本文就是来探讨怎么转换。将递归算法转换为非递归算法有两种方法,一种是直接值(迭代/循环),不需要回溯;另一种是不能直接值,需要回溯。...

    (给算法爱好者加星标,修炼编程内功)

    来源:Veaxen

    递归算法实际上是一种分而治之的方法,它把复杂问题分解为简单问题来求解。递归的特点包括:递归过程简洁、易编、易懂;递归过程效率低、重复计算多。

    考虑递归的执行效率低,可以尝试将递归过程转换为非递归过程。本文就是来探讨怎么转换的。

    将递归算法转换为非递归算法有两种方法,一种是直接求值(迭代/循环),不需要回溯;另一种是不能直接求值,需要回溯。前者使用一些变量保存中间结果,称为直接转换法;后者使用栈保存中间结果,称为间接转换法,下面分别讨论这两种方法。

    一、直接转换法

    直接转换法通常用来消除尾递归和单向递归,将递归结构用循环结构来替代。

    1.单向递归

    简单的说是指递归的过程总是朝着一个方向进行,如果函数1调用了函数2,而函数2又调用了函数1,则这种情况不属于单向递归。斐波那契数列(单向递归)的递归求解可转用一个迭代法实现。

    斐波那契数列的递归求解:

    int Fib(int n) {
    if(n <= 1) return n;
    else return Fib(n - 1) + Fib(n - 2);
    }

    转换为迭代求解过程

    int Fib(int n) {
    if(n <= 1) return n;
    int twoBack = 0;
    int oneBack = 1;
    int cur;
    for(int i = 2;i < = n; i++) {
    cur = twoBack + oneBack;
    twoBack = oneBack;
    oneBack = cur;
    }
    return cur;
    }

    2.尾递归

    是以递归调用结尾的函数,是单向递归的特例。它的递归调用语句只有一个,而且是放在过程的最后。当递归调用返回时,返回到上一层递归调用语句的下一语句,而这个位置正好是程序的结尾,因此递归工作栈中可以不保存返回地址;除了返回值和引用值外,其他参数和局部变量都不再需要,因此可以不用栈,直接采用循环写出非递归过程。

    阶乘函数就不是一个尾递归。因为在它收到递归调用的结果后,必须在返回调用前再做一次乘法运算。但是阶乘函数可以转化成一个尾递归函数,例:

    阶乘的递归求解:

    int factorial(int n)
    {
    if(n == 0)
    return 1;
    else{
    int val = factorial(n - 1);
    return n * val;
    }
    }

    转换为尾递归:

    int factorial(int acc, int x)
    { 
    //acc传的值为1。
    if(x <= 1)
    return acc;
    else
    return factorial(x * acc, x - 1);
    }

    尾递归的重要性在于当进行尾递归调用时,调用者的返回位置不需要被存在调用栈里。当递归调用返回时,它直接分支到先前已保存的返回地址。因此,在支持尾递归优化的编译器上,尾递归在时间和空间上都比较划算。迭代算法需要一个临时变量,这无疑导致了程序的可读性降低,迭代函数不像递归函数那样需要考虑函数调用的支出,而且对一个线程来说可用的栈空间通常比可用的堆空间要少得多,而递归算法则相对迭代算法需要更多的栈空间!

    二、间接转换法

    该方法使用栈保存中间结果,一般需根据递归函数在执行过程中栈的变化得到。其一般过程如下:

    将初始状态s0进栈
    while (栈不为空){
    退栈,将栈顶元素赋给s;
    ……
    ……
    if(不满足递归结束条件){
    寻找到s的相关状态s1;
    将s1进栈
      }
    }

    间接转换法在数据结构中有较多实例,如二叉树遍历算法的非递归实现、图的深度优先遍历算法的非递归实现等等,下面我们以二叉树来说明,不过大多数情况下二叉树已经够用,而且理解了二叉树的遍历,其它的树遍历方式就不难了。

    1)前序遍历

    a)递归方式:
    void preorder_recursive(Bitree T)            /* 先序遍历二叉树的递归算法 */
    {
    if (T) {
    visit(T); /* 访问当前结点 */
    preorder_recursive(T->leftChild); /* 访问左子树 */
    preorder_recursive(T->rightChild); /* 访问右子树 */
    }
    }
    b)非递归方式
    void preorder_nonrecursive(Bitree T)              /* 先序遍历二叉树的非递归算法 */
    {
    initstack(S); //初始化栈

    push(S,T); /* 根指针进栈 */
    while(!stackempty(S)) {
    while(gettop(S,p)&&p) { /* 次循环是向左走到尽头,其中gettop()获得栈顶*/
    visit(p); /* 每向前走一步都访问当前结点 */
    push(S,p->leftChild);
    }
    pop(S,p);
    if(!stackempty(S)) { /* 向右走一步 */
    pop(S,p); /* 空指针退栈 */
    push(S,p->rightChild);
    }
    }
    }

    2)中序遍历

    a)递归方式
    void inorder_recursive(Bitree T)        /* 中序遍历二叉树的递归算法 */
    {
    if (T) {
    inorder_recursive(T->leftChild); /* 访问左子树 */
    visit(T); /* 访问当前结点 */
    inorder_recursive(T->rigthChild); /* 访问右子树 */
    }
    }
    b)非递归方式
    void  inorder_nonrecursive(Bitree T)
    {
    initstack(S); /* 初始化栈 */

    push(S, T); /* 根指针入栈 */
    while (!stackempty(S)) {
    while (gettop(S, p) && p) /* 向左走到尽头 */
    push(S, p->leftChild);
    pop(S, p); /*向左走到尽头时,最后一个叶节点的leftChild是NULL,空指针退栈*/
    if (!stackempty(S)) {
    pop(S, p);
    visit(p); /* 访问当前结点 */
    push(S, p->rightChild); /* 向右走一步 */
    }
    }
    }

    3)后序遍历

    a)递归方式
    void postorder_recursive(Bitree T)           /* 中序遍历二叉树的递归算法 */
    {
    if (T) {
    postorder_recursive(T->leftChild); /* 访问左子树 */
    postorder_recursive(T->rightChild); /* 访问右子树 */
    visit(T); /* 访问当前结点 */
    }
    }

    b)非递归方式

    typedef struct {
    BTNode* ptr;
    enum {0,1,2} mark;
    } PMType; /* 有mark域的结点指针类型 */

    void postorder_nonrecursive(BiTree T) /* 后续遍历二叉树的非递归算法*/
    {
    PMType a;
    initstack(S); /* S的元素为PMType类型 */

    push (S,{T,0}); /* 根结点入栈 */
    while(!stackempty(S)) {
    pop(S,a);
    switch(a.mark){
    case 0:
    push(S,{a.ptr,1}); /* 修改mark域 */
    if(a.ptr->leftChild)
    push(S,{a.ptr->leftChild,0}); /* 访问左子树 */
    break;
    case 1:
    push(S,{a.ptr,2}); /* 修改mark域 */
    if(a.ptr->rightChild)
    push(S,{a.ptr->rightChild,0}); /* 访问右子树 */
    break;
    case 2:
    visit(a.ptr); /* 访问结点 */
    }
    }
    }

    - EOF -

    推荐阅读  点击标题可跳转

    1、递归算法转换为非递归算法的技巧

    2、程序员必备的基本算法:递归详解

    3、递归思想:用锅铲给烧饼排序

    觉得本文有帮助?请分享给更多人

    关注「算法爱好者」加星标,修炼编程内功

    0d523413dc2e5f4c46bb14216ebb0058.png

    点赞和在看就是最大的支持❤️

    展开全文
  • 考虑递归执行效率低,可以尝试将递归过程转换为非递归过程。本文就是来探讨怎么转换。将递归算法转换为非递归算法有两种方法,一种是直接值(迭代/循环),不需要回溯;另一种是不能直接值,需要回溯。...

    (给算法爱好者加星标,修炼编程内功)

    来源:Veaxen

    递归算法实际上是一种分而治之的方法,它把复杂问题分解为简单问题来求解。递归的特点包括:递归过程简洁、易编、易懂;递归过程效率低、重复计算多。

    考虑递归的执行效率低,可以尝试将递归过程转换为非递归过程。本文就是来探讨怎么转换的。

    将递归算法转换为非递归算法有两种方法,一种是直接求值(迭代/循环),不需要回溯;另一种是不能直接求值,需要回溯。前者使用一些变量保存中间结果,称为直接转换法;后者使用栈保存中间结果,称为间接转换法,下面分别讨论这两种方法。

    一、直接转换法

    直接转换法通常用来消除尾递归和单向递归,将递归结构用循环结构来替代。

    1.单向递归

    简单的说是指递归的过程总是朝着一个方向进行,如果函数1调用了函数2,而函数2又调用了函数1,则这种情况不属于单向递归。斐波那契数列(单向递归)的递归求解可转用一个迭代法实现。

    斐波那契数列的递归求解:

    int Fib(int n) {
    if(n <= 1) return n;
    else return Fib(n - 1) + Fib(n - 2);
    }

    转换为迭代求解过程

    int Fib(int n) {
    if(n <= 1) return n;
    int twoBack = 0;
    int oneBack = 1;
    int cur;
    for(int i = 2;i < = n; i++) {
    cur = twoBack + oneBack;
    twoBack = oneBack;
    oneBack = cur;
    }
    return cur;
    }

    2.尾递归

    是以递归调用结尾的函数,是单向递归的特例。它的递归调用语句只有一个,而且是放在过程的最后。当递归调用返回时,返回到上一层递归调用语句的下一语句,而这个位置正好是程序的结尾,因此递归工作栈中可以不保存返回地址;除了返回值和引用值外,其他参数和局部变量都不再需要,因此可以不用栈,直接采用循环写出非递归过程。

    阶乘函数就不是一个尾递归。因为在它收到递归调用的结果后,必须在返回调用前再做一次乘法运算。但是阶乘函数可以转化成一个尾递归函数,例:

    阶乘的递归求解:

    int factorial(int n)
    {
    if(n == 0)
    return 1;
    else{
    int val = factorial(n - 1);
    return n * val;
    }
    }

    转换为尾递归:

    int factorial(int acc, int x)
    { 
    //acc传的值为1。
    if(x <= 1)
    return acc;
    else
    return factorial(x * acc, x - 1);
    }

    尾递归的重要性在于当进行尾递归调用时,调用者的返回位置不需要被存在调用栈里。当递归调用返回时,它直接分支到先前已保存的返回地址。因此,在支持尾递归优化的编译器上,尾递归在时间和空间上都比较划算。迭代算法需要一个临时变量,这无疑导致了程序的可读性降低,迭代函数不像递归函数那样需要考虑函数调用的支出,而且对一个线程来说可用的栈空间通常比可用的堆空间要少得多,而递归算法则相对迭代算法需要更多的栈空间!

    二、间接转换法

    该方法使用栈保存中间结果,一般需根据递归函数在执行过程中栈的变化得到。其一般过程如下:

    将初始状态s0进栈
    while (栈不为空){
    退栈,将栈顶元素赋给s;
    ……
    ……
    if(不满足递归结束条件){
    寻找到s的相关状态s1;
    将s1进栈
      }
    }

    间接转换法在数据结构中有较多实例,如二叉树遍历算法的非递归实现、图的深度优先遍历算法的非递归实现等等,下面我们以二叉树来说明,不过大多数情况下二叉树已经够用,而且理解了二叉树的遍历,其它的树遍历方式就不难了。

    1)前序遍历

    a)递归方式:
    void preorder_recursive(Bitree T)            /* 先序遍历二叉树的递归算法 */
    {
    if (T) {
    visit(T); /* 访问当前结点 */
    preorder_recursive(T->leftChild); /* 访问左子树 */
    preorder_recursive(T->rightChild); /* 访问右子树 */
    }
    }
    b)非递归方式
    void preorder_nonrecursive(Bitree T)              /* 先序遍历二叉树的非递归算法 */
    {
    initstack(S); //初始化栈

    push(S,T); /* 根指针进栈 */
    while(!stackempty(S)) {
    while(gettop(S,p)&&p) { /* 次循环是向左走到尽头,其中gettop()获得栈顶*/
    visit(p); /* 每向前走一步都访问当前结点 */
    push(S,p->leftChild);
    }
    pop(S,p);
    if(!stackempty(S)) { /* 向右走一步 */
    pop(S,p); /* 空指针退栈 */
    push(S,p->rightChild);
    }
    }
    }

    2)中序遍历

    a)递归方式
    void inorder_recursive(Bitree T)        /* 中序遍历二叉树的递归算法 */
    {
    if (T) {
    inorder_recursive(T->leftChild); /* 访问左子树 */
    visit(T); /* 访问当前结点 */
    inorder_recursive(T->rigthChild); /* 访问右子树 */
    }
    }
    b)非递归方式
    void  inorder_nonrecursive(Bitree T)
    {
    initstack(S); /* 初始化栈 */

    push(S, T); /* 根指针入栈 */
    while (!stackempty(S)) {
    while (gettop(S, p) && p) /* 向左走到尽头 */
    push(S, p->leftChild);
    pop(S, p); /*向左走到尽头时,最后一个叶节点的leftChild是NULL,空指针退栈*/
    if (!stackempty(S)) {
    pop(S, p);
    visit(p); /* 访问当前结点 */
    push(S, p->rightChild); /* 向右走一步 */
    }
    }
    }

    3)后序遍历

    a)递归方式
    void postorder_recursive(Bitree T)           /* 中序遍历二叉树的递归算法 */
    {
    if (T) {
    postorder_recursive(T->leftChild); /* 访问左子树 */
    postorder_recursive(T->rightChild); /* 访问右子树 */
    visit(T); /* 访问当前结点 */
    }
    }

    b)非递归方式

    typedef struct {
    BTNode* ptr;
    enum {0,1,2} mark;
    } PMType; /* 有mark域的结点指针类型 */

    void postorder_nonrecursive(BiTree T) /* 后续遍历二叉树的非递归算法*/
    {
    PMType a;
    initstack(S); /* S的元素为PMType类型 */

    push (S,{T,0}); /* 根结点入栈 */
    while(!stackempty(S)) {
    pop(S,a);
    switch(a.mark){
    case 0:
    push(S,{a.ptr,1}); /* 修改mark域 */
    if(a.ptr->leftChild)
    push(S,{a.ptr->leftChild,0}); /* 访问左子树 */
    break;
    case 1:
    push(S,{a.ptr,2}); /* 修改mark域 */
    if(a.ptr->rightChild)
    push(S,{a.ptr->rightChild,0}); /* 访问右子树 */
    break;
    case 2:
    visit(a.ptr); /* 访问结点 */
    }
    }
    }

    - EOF -

    推荐阅读  点击标题可跳转

    1、递归算法转换为非递归算法的技巧

    2、程序员必备的基本算法:递归详解

    3、递归思想:用锅铲给烧饼排序

    觉得本文有帮助?请分享给更多人

    关注「算法爱好者」加星标,修炼编程内功

    c8316d3553e74f0c45cca002573aeb61.png

    点赞和在看就是最大的支持❤️

    展开全文
  • 考虑递归执行效率低,可以尝试将递归过程转换为非递归过程。本文就是来探讨怎么转换。 将递归算法转换为非递归算法有两种方法,一种是直接值(迭代/循环),不需要回溯;另一种是不能直接值,需要回溯。前者...

    递归算法实际上是一种分而治之的方法,它把复杂问题分解为简单问题来求解。递归的特点包括:递归过程简洁、易编、易懂;递归过程效率低、重复计算多。

    考虑递归的执行效率低,可以尝试将递归过程转换为非递归过程。本文就是来探讨怎么转换的。

    将递归算法转换为非递归算法有两种方法,一种是直接求值(迭代/循环),不需要回溯;另一种是不能直接求值,需要回溯。前者使用一些变量保存中间结果,称为直接转换法;后者使用栈保存中间结果,称为间接转换法,下面分别讨论这两种方法。

    一、直接转换法

    直接转换法通常用来消除尾递归和单向递归,将递归结构用循环结构来替代。

    1.单向递归

    简单的说是指递归的过程总是朝着一个方向进行,如果函数1调用了函数2,而函数2又调用了函数1,则这种情况不属于单向递归。斐波那契数列(单向递归)的递归求解可转用一个迭代法实现。

    斐波那契数列的递归求解:

    int Fib(int n) {
      if(n <= 1) return n;
      else return Fib(n - 1) + Fib(n - 2);
    }

    转换为迭代求解过程:

    int Fib(int n) {
       if(n <= 1) return n;
      int twoBack = 0;
       int oneBack = 1;
       int cur;
      for(int i = 2;i < = n; i++) {
          cur = twoBack + oneBack;
        twoBack = oneBack;
          oneBack = cur;
       }
       return cur;
    }

    2.尾递归

    是以递归调用结尾的函数,是单向递归的特例。它的递归调用语句只有一个,而且是放在过程的最后。当递归调用返回时,返回到上一层递归调用语句的下一语句,而这个位置正好是程序的结尾,因此递归工作栈中可以不保存返回地址;除了返回值和引用值外,其他参数和局部变量都不再需要,因此可以不用栈,直接采用循环写出非递归过程。

    阶乘函数就不是一个尾递归。因为在它收到递归调用的结果后,必须在返回调用前再做一次乘法运算。但是阶乘函数可以转化成一个尾递归函数,例:

    阶乘的递归求解:

    int factorial(int n)
    {
       if(n == 0) return 1;
       else{
        int val = factorial(n - 1);
        return n * val;
       }
    }

    转换为尾递归:

    int factorial(int acc, int x)
    
     { //acc传的值为1。
      if(x <= 1) return acc;
      else
    
         return factorial(x * acc, x - 1);
    }

    尾递归的重要性在于当进行尾递归调用时,调用者的返回位置不需要被存在调用栈里。当递归调用返回时,它直接分支到先前已保存的返回地址。因此,在支持尾递归优化的编译器上,尾递归在时间和空间上都比较划算。迭代算法需要一个临时变量,这无疑导致了程序的可读性降低,迭代函数不像递归函数那样需要考虑函数调用的支出,而且对一个线程来说可用的栈空间通常比可用的堆空间要少得多,而递归算法则相对迭代算法需要更多的栈空间!

    二、间接转换法

    该方法使用栈保存中间结果,一般需根据递归函数在执行过程中栈的变化得到。其一般过程如下:

    将初始状态s0进栈
    while (栈不为空){
        退栈,将栈顶元素赋给s;
        ……
        ……
        if(不满足递归结束条件){
            寻找到s的相关状态s1;
            将s1进栈
      }
    }

    间接转换法在数据结构中有较多实例,如二叉树遍历算法的非递归实现、图的深度优先遍历算法的非递归实现等等,下面我们以二叉树来说明,不过大多数情况下二叉树已经够用,而且理解了二叉树的遍历,其它的树遍历方式就不难了。

    1)前序遍历

    a)递归方式:
    void preorder_recursive(Bitree T)            /* 先序遍历二叉树的递归算法 */
    {
        if (T) {
            visit(T);                /* 访问当前结点 */
            preorder_recursive(T->leftChild);  /* 访问左子树 */
            preorder_recursive(T->rightChild);  /* 访问右子树 */
        }
    }
    b)非递归方式
    void preorder_nonrecursive(Bitree T)              /* 先序遍历二叉树的非递归算法 */
    {
        initstack(S); //初始化栈
    
        push(S,T);                         /* 根指针进栈 */
        while(!stackempty(S)) {
            while(gettop(S,p)&&p) {           /* 次循环是向左走到尽头,其中gettop()获得栈顶*/
                visit(p);          /* 每向前走一步都访问当前结点 */
                push(S,p->leftChild);
            }
            pop(S,p);
            if(!stackempty(S)) {            /* 向右走一步 */
                pop(S,p);          /* 空指针退栈 */
                push(S,p->rightChild);
            }
        }
    }

    2)中序遍历

    a)递归方式
    void inorder_recursive(Bitree T)        /* 中序遍历二叉树的递归算法 */
    {
        if (T) {
            inorder_recursive(T->leftChild);     /* 访问左子树 */
            visit(T);                /* 访问当前结点 */
            inorder_recursive(T->rigthChild);    /* 访问右子树 */
        }
    }
    b)非递归方式
    void  inorder_nonrecursive(Bitree T)
    {
    initstack(S);                        /* 初始化栈 */
    
        push(S, T);                         /* 根指针入栈 */
        while (!stackempty(S)) {
            while (gettop(S, p) && p) /* 向左走到尽头 */
                push(S, p->leftChild);
            pop(S, p);                   /*向左走到尽头时,最后一个叶节点的leftChild是NULL,空指针退栈*/
            if (!stackempty(S)) {
                pop(S, p);
                visit(p);          /* 访问当前结点 */
                push(S, p->rightChild);     /* 向右走一步 */
            }
        }
    }

    3)后序遍历

    a)递归方式
    void postorder_recursive(Bitree T)           /* 中序遍历二叉树的递归算法 */
    {
        if (T) {
            postorder_recursive(T->leftChild);  /* 访问左子树 */
            postorder_recursive(T->rightChild); /* 访问右子树 */
            visit(T);                        /* 访问当前结点 */
        }
    }

    b)非递归方式

    typedef struct {
        BTNode* ptr;
        enum {0,1,2} mark;
    } PMType;                               /* 有mark域的结点指针类型 */
    
    void postorder_nonrecursive(BiTree T)    /* 后续遍历二叉树的非递归算法*/
    {
        PMType a;
        initstack(S);                       /* S的元素为PMType类型 */
    
        push (S,{T,0});                  /* 根结点入栈 */
        while(!stackempty(S)) {
            pop(S,a);
            switch(a.mark){
                case 0:
                    push(S,{a.ptr,1});       /* 修改mark域 */
                    if(a.ptr->leftChild)
                        push(S,{a.ptr->leftChild,0}); /* 访问左子树 */
                    break;
                case 1:
                    push(S,{a.ptr,2});       /* 修改mark域 */
                    if(a.ptr->rightChild)
                        push(S,{a.ptr->rightChild,0}); /* 访问右子树 */
                    break;
                case 2:
                    visit(a.ptr);           /* 访问结点 */
            }
        }
    }

    参考:
    http://www.cnblogs.com/TECHNOLOGYer/p/4776496.html
    http://blog.csdn.net/shunrei/article/details/5680579

    转载于:https://www.cnblogs.com/veaxen/p/9185581.html

    展开全文
  • (点击上方快速关注并设置为星标,一起学Python)来源:Veaxen递归算法实际上是一种分而治之方法,它把复杂问题...将递归算法转换为非递归算法有两种方法,一种是直接值(迭代/循环),不需要回溯;另一种是不能直接...

    (点击上方快速关注并设置为星标,一起学Python)

    来源:Veaxen

    递归算法实际上是一种分而治之的方法,它把复杂问题分解为简单问题来求解。递归的特点包括:递归过程简洁、易编、易懂;递归过程效率低、重复计算多。

    考虑递归的执行效率低,可以尝试将递归过程转换为非递归过程。本文就是来探讨怎么转换的。

    将递归算法转换为非递归算法有两种方法,一种是直接求值(迭代/循环),不需要回溯;另一种是不能直接求值,需要回溯。前者使用一些变量保存中间结果,称为直接转换法;后者使用栈保存中间结果,称为间接转换法,下面分别讨论这两种方法。

    一、直接转换法

    直接转换法通常用来消除尾递归和单向递归,将递归结构用循环结构来替代。

    1.单向递归

    简单的说是指递归的过程总是朝着一个方向进行,如果函数1调用了函数2,而函数2又调用了函数1,则这种情况不属于单向递归。斐波那契数列(单向递归)的递归求解可转用一个迭代法实现。

    斐波那契数列的递归求解:

    int Fib(int n) {
    if(n <= 1) return n;
    else return Fib(n - 1) + Fib(n - 2);
    }

    转换为迭代求解过程

    int Fib(int n) {
    if(n <= 1) return n;
    int twoBack = 0;
    int oneBack = 1;
    int cur;
    for(int i = 2;i < = n; i++) {
    cur = twoBack + oneBack;
    twoBack = oneBack;
    oneBack = cur;
    }
    return cur;
    }

    2.尾递归

    是以递归调用结尾的函数,是单向递归的特例。它的递归调用语句只有一个,而且是放在过程的最后。当递归调用返回时,返回到上一层递归调用语句的下一语句,而这个位置正好是程序的结尾,因此递归工作栈中可以不保存返回地址;除了返回值和引用值外,其他参数和局部变量都不再需要,因此可以不用栈,直接采用循环写出非递归过程。

    阶乘函数就不是一个尾递归。因为在它收到递归调用的结果后,必须在返回调用前再做一次乘法运算。但是阶乘函数可以转化成一个尾递归函数,例:

    阶乘的递归求解:

    int factorial(int n)
    {
    if(n == 0)
    return 1;
    else{
    int val = factorial(n - 1);
    return n * val;
    }
    }

    转换为尾递归:

    int factorial(int acc, int x)
    { 
    //acc传的值为1。
    if(x <= 1)
    return acc;
    else
    return factorial(x * acc, x - 1);
    }

    尾递归的重要性在于当进行尾递归调用时,调用者的返回位置不需要被存在调用栈里。当递归调用返回时,它直接分支到先前已保存的返回地址。因此,在支持尾递归优化的编译器上,尾递归在时间和空间上都比较划算。迭代算法需要一个临时变量,这无疑导致了程序的可读性降低,迭代函数不像递归函数那样需要考虑函数调用的支出,而且对一个线程来说可用的栈空间通常比可用的堆空间要少得多,而递归算法则相对迭代算法需要更多的栈空间!

    二、间接转换法

    该方法使用栈保存中间结果,一般需根据递归函数在执行过程中栈的变化得到。其一般过程如下:

    将初始状态s0进栈
    while (栈不为空){
    退栈,将栈顶元素赋给s;
    ……
    ……
    if(不满足递归结束条件){
    寻找到s的相关状态s1;
    将s1进栈
      }
    }

    间接转换法在数据结构中有较多实例,如二叉树遍历算法的非递归实现、图的深度优先遍历算法的非递归实现等等,下面我们以二叉树来说明,不过大多数情况下二叉树已经够用,而且理解了二叉树的遍历,其它的树遍历方式就不难了。

    1)前序遍历

    a)递归方式:
    void preorder_recursive(Bitree T)            /* 先序遍历二叉树的递归算法 */
    {
    if (T) {
    visit(T); /* 访问当前结点 */
    preorder_recursive(T->leftChild); /* 访问左子树 */
    preorder_recursive(T->rightChild); /* 访问右子树 */
    }
    }
    b)非递归方式
    void preorder_nonrecursive(Bitree T)              /* 先序遍历二叉树的非递归算法 */
    {
    initstack(S); //初始化栈

    push(S,T); /* 根指针进栈 */
    while(!stackempty(S)) {
    while(gettop(S,p)&&p) { /* 次循环是向左走到尽头,其中gettop()获得栈顶*/
    visit(p); /* 每向前走一步都访问当前结点 */
    push(S,p->leftChild);
    }
    pop(S,p);
    if(!stackempty(S)) { /* 向右走一步 */
    pop(S,p); /* 空指针退栈 */
    push(S,p->rightChild);
    }
    }
    }

    2)中序遍历

    a)递归方式
    void inorder_recursive(Bitree T)        /* 中序遍历二叉树的递归算法 */
    {
    if (T) {
    inorder_recursive(T->leftChild); /* 访问左子树 */
    visit(T); /* 访问当前结点 */
    inorder_recursive(T->rigthChild); /* 访问右子树 */
    }
    }
    b)非递归方式
    void  inorder_nonrecursive(Bitree T)
    {
    initstack(S); /* 初始化栈 */

    push(S, T); /* 根指针入栈 */
    while (!stackempty(S)) {
    while (gettop(S, p) && p) /* 向左走到尽头 */
    push(S, p->leftChild);
    pop(S, p); /*向左走到尽头时,最后一个叶节点的leftChild是NULL,空指针退栈*/
    if (!stackempty(S)) {
    pop(S, p);
    visit(p); /* 访问当前结点 */
    push(S, p->rightChild); /* 向右走一步 */
    }
    }
    }

    3)后序遍历

    a)递归方式
    void postorder_recursive(Bitree T)           /* 中序遍历二叉树的递归算法 */
    {
    if (T) {
    postorder_recursive(T->leftChild); /* 访问左子树 */
    postorder_recursive(T->rightChild); /* 访问右子树 */
    visit(T); /* 访问当前结点 */
    }
    }

    b)非递归方式

    typedef struct {
    BTNode* ptr;
    enum {0,1,2} mark;
    } PMType; /* 有mark域的结点指针类型 */

    void postorder_nonrecursive(BiTree T) /* 后续遍历二叉树的非递归算法*/
    {
    PMType a;
    initstack(S); /* S的元素为PMType类型 */

    push (S,{T,0}); /* 根结点入栈 */
    while(!stackempty(S)) {
    pop(S,a);
    switch(a.mark){
    case 0:
    push(S,{a.ptr,1}); /* 修改mark域 */
    if(a.ptr->leftChild)
    push(S,{a.ptr->leftChild,0}); /* 访问左子树 */
    break;
    case 1:
    push(S,{a.ptr,2}); /* 修改mark域 */
    if(a.ptr->rightChild)
    push(S,{a.ptr->rightChild,0}); /* 访问右子树 */
    break;
    case 2:
    visit(a.ptr); /* 访问结点 */
    }
    }
    }

    (完)

    看完本文有收获?请转发分享给更多人

    关注「Python那些事」,做全栈开发工程师

    c3e99f0128edf946d35ccaa514026398.png

    dad1e0417b1f43157c846a01a1f99a29.png

    点「在看」的人都变好看了哦
    展开全文
  • 3.7 是否可以安全地认为,一旦&&和||左边表达式已经决定了整个表达式结果,则右边表达式不会被值? 36  3.8 为什么表达式printf(%d %d, f1(), f2()); 先调用了f2?我觉得逗号表达式应该确保从左到右的求...
  • 《你必须知道495个C语言问题》

    热门讨论 2010-03-20 16:41:18
    《你必须知道495个C语言问题》以问答形式组织内容,讨论了学习或使用C语言的过程中经常遇到一些问题。书中列出了C用户经常问400多个经典问题,涵盖了初始化、数组、指针、字符串、内存分配、库函数、C预...
  • c语言编写单片机技巧

    2009-04-19 12:15:17
    答:大学过程是一个理论过程,实践机会比较少,往往会造成理论与实践相脱节,这是国内大学教育系统通病,不过对于学生来说切不可好高骛远。一般从大三会开始接触到一些专业课程,电子相关专业会开设相关...
  • 100个人高考成绩平均分与全省所有考生成绩平均分在占用时间和内存存储上有非常大差异,我们自然追求高效率和低存储算法来解决问题。 2.6.1正确性 22 2.6.2可读性 23 2.6.3健壮性 23 2.6.4时间效率高和...
  • 100个人高考成绩平均分与全省所有考生成绩平均分在占用时间和内存存储上有非常大差异,我们自然追求高效率和低存储算法来解决问题。 2.6.1正确性 22 2.6.2可读性 23 2.6.3健壮性 23 2.6.4时间效率高和...
  • ASP.NET精品课程+源代码

    千次下载 热门讨论 2009-01-05 20:15:51
    当学生对一些小案例完成后教师组织学生开展自评互评及教师评定与归纳总结,从而进一步提高学生学习效率与应用能力。 (4)效果评价 通过对案例教学筹划实施上述过程。为了更好运用案例教学方法,提高教学质量,...
  • 大话数据结构

    2019-01-10 16:35:22
    100个人高考成绩平均分与全省所有考生成绩平均分在占用时间和内存存储上有非常大差异,我们自然追求高效率和低存储算法来解决问题。 2.6.1正确性 22 2.6.2可读性 23 2.6.3健壮性 23 2.6.4时间效率高和...
  • 大话数据结构 程杰

    2018-09-01 10:06:43
    100个人高考成绩平均分与全省所有考生成绩平均分在占用时间和内存存储上有非常大差异,我们自然追求高效率和低存储算法来解决问题。 2.6.1正确性 22 2.6.2可读性 23 2.6.3健壮性 23 2.6.4时间效率高和...
  • 21 2.5.2 有穷性 21 2.5.3 确定性 21 2.5.4 可行性 21 2.6 算法设计要求 22 100个人高考成绩平均分与全省所有考生成绩平均分在占用时间和内存存储上有非常大差异,我们自然追求高效率和低存储算法来...
  • 大话数据结构-程杰

    2014-07-13 23:45:52
    100个人高考成绩平均分与全省所有考生成绩平均分在占用时间和内存存储上有非常大差异,我们自然追求高效率和低存储算法来解决问题。 2.6.1 正确性 22 2.6.2 可读性 23 2.6.3 健壮性 23 2.6.4 时间...
  • 2.3 过程式程序设计 20 2.3.1 变量和算术 21 2.3.2 检测和循环 22 2.3.3 指针和数组 23 2.4 模块程序设计 23 2.4.1 分别编译 24 2.4.2 异常处理 25 2.5 数据抽象 26 2.5.1 定义类型模块 27 2.5.2 用户...
  • 2.3 过程式程序设计 20 2.3.1 变量和算术 21 2.3.2 检测和循环 22 2.3.3 指针和数组 23 2.4 模块程序设计 23 2.4.1 分别编译 24 2.4.2 异常处理 25 2.5 数据抽象 26 2.5.1 定义类型模块 27 2.5.2 用户...
  • C++程序设计语言(特别版)--源代码

    热门讨论 2012-04-23 07:33:51
    2.3 过程式程序设计 20 2.3.1 变量和算术 21 2.3.2 检测和循环 22 2.3.3 指针和数组 23 2.4 模块程序设计 23 2.4.1 分别编译 24 2.4.2 异常处理 25 2.5 数据抽象 26 2.5.1 定义类型模块 27 2.5.2 用户...
  • 经过跟踪变量值发现循环变量i阀值pSysHead->dbf_count数值为0xFFFFFFFF,该值是从被破坏内存数据库中获取,正常情况下该值小于127。而pDBFat是数据库起始地址,如果pSysHead->dbf_count值异常过大,将...
  • 11、嵌入式系统中经常要用到无限循环,你怎么样用C编写死循环呢? 答: 这个问题用几个解决方案。我首选方案是: while(1) { } 一些程序员更喜欢如下方案: for(;;) { } 13、关于内存对齐问题以及sizof()...
  • java 面试题 总结

    2009-09-16 08:45:34
    round方法返回与参数最接近长整数,参数加1/2后其floor. 27、String s = new String("xyz");创建了几个String Object? 两个 28、设计4个线程,其中两个线程每次对j增加1,另外两个线程对j每次减少1。写出程序...

空空如也

空空如也

1 2
收藏数 23
精华内容 9
关键字:

循环过程的效率怎么求