计算机科学中的递归： 第一部分

• 下载源代码 - 1.31 KB
• 下载编译好的程序 - 22 KB

摘要

在编程中，递归与《牛津高阶学习词典》中的“recur”（重复）相对，指的是某事发生多次。在模块化编程中，一个函数调用，或者面向对象编程中的一个方法，会多次（或无限次）地调用自身，这可能是故意的，但通常是由于算法错误而无意中发生的。然而，多年来，递归在复杂的情况（如编程和数学计算）中变得非常有用，值得对其重要性和应用进行详细解释。

注意：本文档**不会**对该主题进行广泛阐述，**只会**强调其重要性和应用。我相信人们通过这种方式（至少我）学习得更快，而不是用**大段的语法**和公式来压垮他们。如果您需要关于它的（递归）通用文本，请参阅维基百科。

本系列将向您介绍递归并展示其一些有用的应用。在第一部分，我将讨论使用递归进行文件/文件夹的迭代。我将跳过所有数学内容，直接进入编程方面。请尝试阅读到最后，并记住给文章评分，这将极大地影响下一部分。

引言

首先，如果我的文章、笑话和代码伤害了您（开发者社区），我深表歉意。我不是英国人，我的母语是约鲁巴语（尼日利亚西南部的一种语言）。我决定写这篇笔记来分享我从上帝那里获得的一些想法。我必须说，写这篇文章比编程本身还要辛苦。在我用 Symbian C API（应用程序编程接口）为我的手机开发了一个文件管理器后，我决定写这篇文章。

[文件管理器是一个类似 Windows Explorer 的应用程序。你**不能**通过私信向我索要完整源代码！]

什么是递归？ 递归是过程执行过程中，某个步骤涉及重新运行整个相同过程。大多数人将递归的概念与循环混淆。但在这里，我想让您将递归看作一个弹簧或一个“悠悠球”，拉伸到一定限度，然后在拉伸后恢复到其初始状态/大小。另一方面，循环应该被想象成一个吊扇，朝着“一个方向”旋转一段时间（或直到被某种东西打断）。然而，在编程中，这两者都是不可或缺的，其中循环的使用频率更高。

<下一章将介绍递归与循环的对比。>

更具体地说，计算机科学和数学中的递归是指一个函数被定义，并且同一个函数在同一个函数内部被应用。递归简单来说就是某事自发地或错误地（由于错误）一遍又一遍地发生；例如，LAME 作为一个递归缩略词：LAME is not An Mp3 Encoder（LAME 不是一个 MP3 编码器）。看到了吗？

递归！如果您仍然不明白；请看“递归”。

递归主要用于将大型复杂操作分解为更小、更简单的步骤，如果使用更直接、更复杂的方法，这些步骤“设计”来完成相同的任务（更像“分而治之”的方法）。要令人满意地使用递归，一个人必须首先了解它的伟大之处，而这正是本部分的设计目的。如果您想知道如何用编程解决阶乘或其他数学问题，请关注其他即将到来的部分。

注意：本文附带的示例代码清晰、注释详细且自解释。但如果您仍然觉得不清楚，请通过私信联系我：gx_306@yahoo.com 以获得更清晰的解释。:S。对于那些因文本格式糟糕而给文章低分的人，我希望您现在已经改变了主意，因为我已经重写了整个内容。

“要理解递归，首先必须理解递归！”

示例代码

本文附带的示例程序/代码使用递归过程来搜索并打印出从作为参数传递给它的根目录开始的所有文件（无论是否隐藏），直到目录路径的最后一个子目录。整个代码是用 C 编程语言编写的。让我们来看看……

流程图

流程图希望说明一切。定义了一个单一例程；从根目录开始，它使用一个循环（参见从 F1.6 到 F1.3 的循环）来遍历一个文件夹，并在过程中，当搜索过程中遇到一个目录时（参见 F1.4 - F1.8），启动该例程的一个新实例。从图表中可以看出，新启动的例程在所有事情结束后，最终返回到父例程。因此，无论我们进行多少次递归，程序都会在主程序结束时终止（如果一切顺利）。

代码

注意：整个示例代码是用纯 C 语言编写的，出于可移植性原因没有使用专有 API。对于那些发送邮件说程序创建了“Recursion_out.txt”文件但没有在其中写入任何内容的人，您可能遇到了 MSVCRT.DLL 的问题；请在此处获取一个副本，或寻找可能替换它的工作/升级版本。

尽管代码非常简短（递归的精髓），但它是使用 Pelles C IDE for Microsoft Windows ver: 4.50 (下载此处) 编译的。但在其他 IDE（MSVCPP、GCC 和 DEVC++ 等）上尝试代码可能也会得到相同的结果。一位朋友在 DEV C++ 上编译它，没有错误，没有警告，但我不用它，所以我不能确定。:D 最后，我使用了“<”来防止某些 HTTP 错误（如果不这样做，代码将跳过一些步骤）。

尽管示例代码注释非常详细，但有些人仍然更喜欢直接的解释。好吧，这里是：从定义的 sBuildList() 函数开始，该函数接收三个参数

1. 搜索路径：开始搜索的路径（例如，C 盘的 C:\\ 或“C:\\root folder\”，以及“root folder”）。只需输入一个带引号的路径字符串。
2. 输出文件句柄：请参见 C _fopen() 文档。
3. 标志：用于选择所需的输出（屏幕/文件）。

int sBuildList(_TCHAR* path,FILE *file,unsigned int  flag){ 
    struct _finddata_t fs;//files search structure    
    long int  handle; //Search handle
    int counter=0;//?, see below

    //Here we created two (Hopefully) larg enough  buffers
    _TCHAR* buff = (_TCHAR*)malloc(MAX_PATH);
    _TCHAR* buff2 = (_TCHAR*)malloc(MAX_PATH);

    memset(buff,0,MAX_PATH);//Reset buffers to Zero
    memset(buff2,0,MAX_PATH);

    //Below, I Performed some string operations
    // to copy input string into the buffers FAST!
    for(int i=0;i"<"strlen(path);i++)
    //note i used coates around < to prevent some http errors
        buff2[i]=buff[i]=path[i];
    strcat(buff,_T("*.*"));

    //Searches starts
    if((handle = _findfirst(buff,&fs))==-1) //-1means error
        return 0;

    do{ 
        //Note: I GOT A PM SAYING memset is SLOW!, is that through?
        memset(buff,0,MAX_PATH);//Reset buffers to Zero
        memset(buff2,0,MAX_PATH);
    
        //I used the following line to copy text into the working buffers
        //I believe this method is faster in instead of using (l)strcpy,memcpy x2.
        for(int i=0;i"<"strlen(path);i++)
        //Copy data to the buffers
            buff2[i]=buff[i]=path[i];       
    
        /* I used "counter" to skip the two first directories (i.e . and ..).*/
        if(counter>=2){
            //below i rebuild "buff" to containe the new path or filename.
            strcat(buff,fs.name);
            strcat(buff,_T("\\"));
            //if it is a directory?,search it!
            if((fs.attrib & _A_SUBDIR)!=0)
            //Check for DIRECTORY
                //Take note as i recall the "sBuildList" here
                sBuildList(buff,file,flag);
                //DE SPOT! the recursion takes place here
    
            //if is a file...
            if((fs.attrib & _A_SUBDIR)==0){ //Check for FILE (ANY FILE!)
                strcat(buff,_T("\\"));
                strcat(buff2,fs.name); 
                strcat(buff2,_T("\n")); 
                if((flag & 1)==1){//standard output
                    printf(buff2);
                }else{
                    fputs(buff2,file);//output to file
                }
            }
        }
        counter++;
    }while((_findnext(handle,&fs))==0);

    _findclose(handle);
    free((void*) buff);
    free((void*) buff2);
    return 1;
};

代码非常自解释且简短。它真正证明了递归的“分而治之”的别名（自己试试代码吧！）。这里没什么可解释的，除了我使用了上面简单的字符串操作方法将输入路径字符串同时直接复制到缓冲区中，这比使用 strcpy / memcpy (x2) 要好得多。其余代码在 do while 循环中使用 _findfirst 和 _findnext C 运行时函数来搜索文件和目录（对于 MS Windows 用户来说是文件夹）。最后，我关闭了搜索句柄和分配的缓冲区。搞定！

结论

我们已经完成了本系列第一部分的内容。后续部分将向您介绍更高级和更具数学性的递归主题，以及在软件编程中的应用。请记住给这篇文章评分，这将影响更多文章的发布。别忘了，欢迎对这项工作提出问候、报告和更正，并将不胜感激。请关注下一期。谢谢。