【算法笔记4.3小节-递归】概念，递归求全排列

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了【算法笔记4.3小节-递归】概念，递归求全排列，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1697字，纯文字阅读大概需要3分钟。

内容图文

分治（divide and conquer）

全称“分而治之”, 分治法作为一种算法思想，既可以使用递归的手段去实现，也可以通过非递归的手段去实现。

递归

递归边界和递归式构成。

//求n的阶乘
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int f(int n)
{
    if(n==0) return 1;          //当到达递归边界f(0)时，返回f(0)==1
    else return f(n-1) * n;
}
int main()
{
    int n;
    scanf("%d",&n);
    printf("%d\n",f(n));

    return 0;
}

//递归实现斐波那契数列
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int f(int n)
{
    if(n==0 || n==1) return 1;    //递归边界
    else return f(n-1) + f(n-2);       //递归式
}
int main()
{
    int n;
    scanf("%d",&n);
    printf("%d\n",f(n));

    return 0;
}

 1. 递归求全排列，之前一直纠结程序是如何执行的，堆栈是怎么变化的。今天借助debug手写模拟一遍，差不多弄懂了这个全排列计算机是如何执行的。附上手写执行过程。

//递归实现求1~n的全排列
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn = 11;
int n ;              //n为全局变量
int p[maxn];         //p为当前排列，
int hashTable[maxn] = {false};      //hashTable记录整数x是否已经在p中

//当前处理排列的第index号位
void generateP(int index){
     if(index == n + 1){     //递归边界,已经处理完排列的1~n位
        for(int i=1; i<=n; i++){
            printf("%d", p[i]);     //输出当前排列
        }
        printf("\n");
        return;
    }

    for(int x=1; x<=n; x++){    //枚举1~n,试图将x填入p[index]
        if(hashTable[x] == false){  //如果x不在p[0]~p[index-1]中
            p[index] = x;           //把x加入当前排列
            hashTable[x] = true;    //记x已在p中
            generateP(index+1);     //处理排列的第index+1号位
            hashTable[x] = false;   //已处理完p[index]为x的子问题，还原状态
        }
    }
}


int main()
{
    n = 3;  //欲输出1~3的全排列
    generateP(1);   //从P[1]开始填

    return 0;
}

递归执行调用过程图：

 

内容总结

以上是互联网集市为您收集整理的【算法笔记4.3小节-递归】概念，递归求全排列全部内容，希望文章能够帮你解决【算法笔记4.3小节-递归】概念，递归求全排列所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---