数据结构－杂记--递归浅谈

r囧r小猫 2022-06-07 04:24 245阅读 0赞

#### 浅谈递归 ####

*  人用迭代，神用递归，介绍一下递归的基础知识，再加上几道题，加深自己对于递归的理解；
 *  递归通常的理解就是函数里面的代码循环调用自身的代码，但是实际上还是存在间接递归这种说法的；
 *  间接递归表示的就是函数`A`调用函数`B`，函数`B`在调用函数`A`这种形式；
 *  需要使用递归的场合的情况判定:

> 如果问题本身是通过递归进行定义的，那么就应该使用递归进行解决;

*  首先看这样一个例题,这是用来计算二项式系数的，二项式稀疏的定义采用的就是递归的形式，所以应该使用二项式的方法进行求解:

> *x*=*n*!*m*!(*n*−*m*)!

#include<iostream>
    
    using namespace std;
    
    int recursion(int n)
    {
        if(n==0)
            return 1;
        if (n != 1)
            return n * recursion(n - 1);
    }
    
    int Binomial_factor(int number_of_iterm, int base_number)
    {
        if(number_of_iterm==0||base_number==0)
            return 1;
        if(number_of_iterm==base_number)
            return 1;
        if(number_of_iterm<0||base_number<0)
            return 0;
    
        int divident=recursion(base_number);
        int divider = recursion(number_of_iterm);
        divider *= recursion((base_number - number_of_iterm));
        return divident/divider;
    
    }
    
    int main()
    {
        cout << int(Binomial_factor(2,10));
    
    }

*  这实现是按照`n!`的定义来实现的；  
    
    
     *  1.首先是用函数`recursion(int n)`来处理阶乘，在使用函数`Binomial_factor`函数来处理阶乘的形式要求；
     *  2.在函数处理里面添加了异常处理模块；
 *  暂时没有实现按照递归定义完成的二项式实现；
 *  接下来尝试实现`Binary_search()`的递归实现:  
    
    
     *  1.首先需要判定递归结束条件，建立边界条件；
     *  2.依次实现递归调用，解决问题；

int Binary_search(int array[], int SearchNumber, int left, int right)
    {
        if (array == NULL || left == right)
            exit;
        int middle = 0;
        //递归截至的条件，这个是很重要的，否则递归就无法结束，类似于迭代里面的无限循环，
        //最终程序会因为栈空间溢出而终止；
        if (left <= right)
        {
            middle = (left + right) / 2;
            switch (Compare(array[middle], SearchNumber, 1))
            {
            case -1:
            //递归开始循环调用程序本身，程序本身的执行会出现很多分叉，然后需要进行状态的保存；
                return Binary_search(array,SearchNumber,middle + 1,right);
            case 0:
                return middle;
            case 1:
                return Binary_Search(array,SearchNumber,left middle－1;
            }
    
        }
        return -1;
    }

*  递归的优缺点:  
    
    
     *  1.在逻辑正确的情况下，递归调用的代码会简洁很多；
     *  2.递归函数在执行的过程中需要开辟大量的空间保存堆栈数据，并且存在大量的函数调用导致空间浪费和时间浪费；
     *  3.在进行递归调用的过程中，大量的工作室重复的，效率比较低；
     *  4.堆栈中间开辟导致溢出的风险变大；
 *  补充一个关于递归的例子:  
    
    
     *  在给定的`n>=1`个元素的集合里面，需要打印这个集合的所有置换；

#include<iostream>
    
    using namespace std;
    
    void perm(int *list, int i, int n)
    {
        int j,temp;
        if (i == n) for (j = 0; j < n; ++j){
            printf("%c ", list[j]);
        }
        else
        {
            for (j = i; j < n; j++)
            {
                swap(list[i], list[j]);
                perm(list,i+1,n);
                swap(list[i],list[j]);
            }
        }
    }
    
    int main()
    {
        int list[3]={
       'a','b','c'};
        perm(list,0,3);
    }

*  程序的输出是：  
    ![这里写图片描述][SouthEast]
 *  大致的分析一下这个程序的执行过程  
    ![这里写图片描述][SouthEast 1]  
    ![这里写图片描述][SouthEast 2]
 *  程序递归执行的过程还是很麻烦的，在分析过程中很容易出错；
 *  提供一个变量`i`和变量`j`的变换过程来方便理解；  
    ![这里写图片描述][SouthEast 3]  
    ![这里写图片描述][SouthEast 4]

[SouthEast]: /images/20220607/13d868c1f9d64edcb67f7fa2559d0002.png
[SouthEast 1]: /images/20220607/fffd21a27c11404cb1f8bd24fab4148a.png
[SouthEast 2]: /images/20220607/48676ca04ec343b3a7351b1dc9896987.png
[SouthEast 3]: /images/20220607/08955c4f9aea4a48b887282abf5471bd.png
[SouthEast 4]: /images/20220607/194e2aca4e6a44a0bac2eda4dd275def.png