探索递归算法的整个执行过程

缺乏、安全感 2022-12-25 01:00 64阅读 0赞

## 一 概述 ##

递归算法是计算机中通过重复将问题分解为同类的子问题而解决问题的方法。递归方式可以被用于解决很多的计算机问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身进行递归。计算机理论可以证明递归的作用可以完全取代循环，因此在很多的函数编程语言中习惯用递归实现循环。

## 二 递归算法的整个执行过程的分析 ##

**此处借助二叉树的先序遍历递归算法来分析递归算法的整个执行过程**

**如图：**

![2020112922292875.png][]

**先序遍历二叉树的整个过程为：先遍历根结点，然后遍历左子树，最后遍历右子树。**

/**
     *访问根结点
     *先序遍历左子树
     *先序遍历右子树
     */
    void PreOrder(BiTree T) {
        if(T!=NULL){
            visit(T);           //访问根结点
            PreOrder(T->lchild);//1.递归遍历左子树
            PreOrder(T->rchild);//2.递归遍历右子树
        }
    }

当先序遍历该树时，先将根结点1传入方法PreOrder(BiTree T)，此时函数中的T就代表着根结点1的树，此时就需要执行先序遍历。

对左子树进行访问。

此时应该访问的为根结点为2的左子树，此时的T为根结点为2的左子树，然后继续对其左子树进行访问，执行如下语句：

PreOrder(T->lchild);//1.递归遍历左子树

此时应该访问的为根结点为4的左子树，此时的T为根结点为4的左子树，当这是后继续对其左子树进行访问，执行如下语句：

PreOrder(T->lchild);//1.递归遍历左子树

此时继续访问左子树时，发现以4为根结点的左子树中不存在左子树，所以此时的T为NULL，所以会结束函数PreOrder的执行。

在左子树访问完后，就开始访问右子树。

PreOrder(T->rchild);//2.递归遍历右子树

由树结构可知，访问以4为根结点的右子树为NULL，所以会直接结束函数PreOrder的执行，并进行返回。

此时对以2为根结点的非空右子树进行访问，也就是以5为根结点的右子树。然后对该右子树的左子树进行访问，为NULL则返回，接着对该右子树的左子树进行访问，为NULL则返回。此时对结点5的访问已经结束了。同时对结点2的整个访问过程也结束了。

同理，其他结点也是按照先根，后左，再右的方式进行递归访问，直至结点为NULL则返回。

**最后，该树的先序遍历的顺序为：1 2 4 5 3 6**

[2020112922292875.png]: /images/20221120/e317601c9b0a40948533fa7e8ff1e301.png

发表评论取消回复

表情：

评论列表（有 0 条评论，64人围观）

还没有评论，来说两句吧...

相关阅读

相关算法-递归算法

1、定义：函数（方法）直接或间接调用自身。必须要有一个明确的结束递归的条件 > 递归的退出条件：思考临界值-`拿到参数对它的范围进行判断`

墨蓝/ 2024年04月08日 09:38/ 0 赞/ 107 阅读

相关递归——递归函数的详细过程

函数递归什么是递归？递归的两个必要条件例子斐波那契数的递归求解 n的阶乘递归求解什么是递归？程序调

港控/mmm°/ 2022年12月26日 09:26/ 0 赞/ 235 阅读

相关探索递归算法的整个执行过程

一概述递归算法是计算机中通过重复将问题分解为同类的子问题而解决问题的方法。递归方式可以被用于解决很多的计算机问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程

缺乏、安全感/ 2022年12月25日 01:00/ 0 赞/ 65 阅读

相关简述递归的执行过程

递归是计算机科学中一个非常重要的概念, 也是程序设计中一种常用的问题求解策略. 问题: 递归求解问题的基本思想是什么? 递归是程序设计中一种常用的问题求解策略, 它的基本思

电玩女神/ 2022年11月14日 15:53/ 0 赞/ 99 阅读

相关递归算法

递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归函数（或过程）来表示问题的解。一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(

深碍√TFBOYSˉ_/ 2022年07月13日 13:46/ 0 赞/ 226 阅读

相关【算法】递归

前言 Github：[https://github.com/yihonglei/road-of-arch][https_github.com_yihonglei_road

我就是我/ 2022年07月12日 04:48/ 0 赞/ 217 阅读

相关递归算法

今年上半年开展新项目, 每天都很忙但也很充实, 学到了很多东西, 比如如何处理50M以上的Excel, 批量处理10W+的数据，新的设计模式等。。。本次分享的是一个小技

àì夳堔傛蜴生んèń/ 2022年05月17日 06:34/ 0 赞/ 277 阅读

相关递归算法

定义：简单来说，递归算法就是直接或者间接调用自身的函数。把一个大型的复杂问题层层转换为一个与原问题相似的小规模的问题来求解。例子：一列数的规则如下: 1、1、2、3、5、8

绝地灬酷狼/ 2022年05月12日 12:14/ 0 赞/ 263 阅读

相关算法--递归

递归：注意两点： 1.边界条件时（有时有return，有时是别的操作）代码里用橘红色标出 2.递归时参数变化（规模变小）代码里用黄色标出递归：你

野性酷女/ 2021年10月09日 03:44/ 0 赞/ 505 阅读

相关递归的定义？何时使用递归？递归模型？递归执行过程？常见的递归思想的例题和实现？

递归递归定义：递归是指函数的定义中又调用函数自身的方法。例题求n（n为正整数）的阶乘 int fun(int n){

我会带着你远行/ 2021年07月24日 13:37/ 0 赞/ 455 阅读