一、快速排序的递归实现

快速排序的思想是每次找到一个元素的位置，再在以这个元素分隔的两个子范围中分别再各自确定一个元素的位置，子子范围也是如此操作，当某个子范围只有一个元素或者没有元素时，便不再做任何操作。这是一个递归过程，递归退出的边界就是子范围中不存在元素或者只存在一个元素。

基于这个思想，很容易便得到递归处理的程序框图：

代码：

#include <cstdio>

using namespace std;

static void quickSort(int array[],int low,int high){
    int l=low,h=high,tmp;
    if (l<h){
        tmp=array[l];
        while (l<h){
            while (array[h]>=tmp){
                h--;
                if(l == h){
                    goto complete;
                }
            }
            array[l]=array[h];

            while (array[l]<tmp){
                l++;
                if(l == h){
                    goto complete;
                }
            }
            array[h]=array[l];
        }

        complete:
        array[l]=tmp;
        //递归处理左右的序列
        quickSort(array,low,l-1);
        quickSort(array,h+1,high);
    }
}

int main() {
	//测试
    int a[8]={49,38,65,97,76,13,27,49};
    quickSort(a,0,7);
    for (int i = 0; i < 8; i++) {
        printf("%d ",a[i]);
    }
    return 0;
}

二、快速排序的非递归实现

上述递归实现的局限性可能在于：当数据量特别大时，可能会导致栈溢出(栈涨的速度为${\log }_{2}n$，也可能是我多虑了，涨地其实挺慢的)。

为了解决上面可能出现的问题，我们可以将递归实现转换为非递归实现，我们知道任何递归的过程都可以转化为一个迭代的过程，而转化的关键在于如何使用迭代来模拟整个递归的处理。

观察上面的递归处理过程，我们可以看到：每一次排序函数的调用都会再次重新调用两次新的排序函数，然后系统会按照调用顺序一步一步地进行处理和返回，而调用排序函数的关键在于必须将排序的范围告诉函数。

这个过程很像一个排队处理的过程，于是我们可以使用队列进行递归的模拟，而队列中的信息存储要处理的范围即可。当队列不为空时，表示还有范围未处理；队列为空时，表示所有的范围都已经处理完毕，也即确定了所有元素的位置，完成了排序工作。

于是我们可以得到下面非递归处理的程序框图：

代码：

#include <cstdio>
#include <queue>

using namespace std;

struct Scope{
    int low,high;
};

static void quickSort2(int array[],int low,int high){
    queue<Scope> scopes;
    scopes.push({low,high});
    Scope sp;
    while (!scopes.empty()){
        sp = scopes.front();
        scopes.pop();
        int l=sp.low,h=sp.high,tmp;
        if (l<h){
            tmp=array[l];
            while (l<h){
                while (array[h]>=tmp){
                    h--;
                    if(l == h){
                        goto complete;
                    }
                }
                array[l]=array[h];

                while (array[l]<tmp){
                    l++;
                    if(l == h){
                        goto complete;
                    }
                }
                array[h]=array[l];
            }

            complete:
            array[l]=tmp;
            //将左右子序列加入待处理队列中
            scopes.push({sp.low,l-1});
            scopes.push({h+1,sp.high});
        }
    }
}

int main() {
	//测试
    int a[8]={49,38,65,97,76,13,27,49};
    quickSort2(a,0,7);
    for (int i = 0; i < 8; i++) {
        printf("%d ",a[i]);
    }
    return 0;
}

栈的作用

当前问题执行到一个状态，以现有的条件无法完全解决时，必须先记下当前状态，然后继续往下执行，等条件成熟后再返回解决。
如DFS时，当前节点1，沿着邻接点2往下遍历，后面还要回到节点1继续遍历其他邻接点。

背景

最近做题遇到过几次递归实现的算法，要求你用非递归的方式实现。这里做一个总结。其实也没技巧，再看几遍，多默写几次代码，记熟即可。
递归算法基本都涉及到函数调用栈。每次递归调用时都将函数数据入栈，所以递归调用越深，占用的栈空间越多。如果层数过深，肯定会导致栈溢出，这也是消除递归的必要性之一。

1. 直接转换法

用循环结构代替单向递归和尾递归。

单向递归：简单的说是指递归的过程总是朝着一个方向进行。函数1调用函数2再调用函数3…一只不重复调用之前的函数。
尾递归函数是以递归调用结尾的函数，是单向递归的特例。

尾递归的递归调用语句只有一个，而且是放在过程的最后。当递归调用结束并返回时，上层函数也就结束了。无需关注函数地址、参数、局部变量等，因此可以直接采用循环写出非递归过程。

斐波那契数列的递归

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;
  else//循环实现
  	int x1= 1;
　	int x2= 0;
　	int sum;
　	for(int i = 2;i < = n; i++) {
   　	sum= x1+x2;
　　	x2= x1;
   　	x1= sum;
　　 }
  	return sum;
}

如何由递归转循环呢，我的思路是列出递归每次的值，然后找规律：

0 1 1

	int x1= 1;
　	int x2= 0;
　	int sum;
	for(int i=2;i<=n;++i)

再观测，x2等于上一次相加的x1，x1等于上一次相加的sum。则循环体内为：

	sum= x1+x2;
	x2= x1;
	x1= sum;

直接用循环替代递归不是很难，一般找清楚递归的变化规律就可以做出。

2. 间接转换法

用于需要回溯的递归；如：函数1调用函数2，函数2又要回溯到函数1；再由函数1调用函数3；（想象树的遍历）我们可以根据函数调用栈，手动建立一个栈，实现非递归实现。

int Stack[Maxsize],top=-1
visit(a);
Stack(++top)=a//将初始状态a进栈
while(top!=-1)//栈不为空
{
	a1=Stack(top);//将栈顶元素赋给a1
	//从a1中寻找满足条件的a2
	if(a2 true)//找到了
	{
		visit(a2);//访问a2;
		Stack(++top)=a2;//将a2进栈
	}
	else//未找到，a1遍历完毕
		---top;//a1退栈
}

注意一点就是：先读取栈顶元素，找到栈顶元素满足条件的下一个元素入栈。因为此时该元素没有出栈+循环的缘故，上层栈内元素出栈后，会回溯到该元素，直到该元素所有满足条件的元素都被访问，该元素出栈，就不会被回溯。这就模拟了函数的递归调用栈。
在数据结构中递归间接转换非递归应该有很多，不够我目前遇到的主要还是二叉树遍历和图的深度遍历，下面做一个记录：

二叉树先序遍历

void preorder(BTNode *p)
{
	if(p!=NULL)
	{
		visit(p);
		preorder(p->lchild);
		preorder(p->rchild);
	}
}

先序遍历
观察先序遍历的入栈过程：
根节点入栈并访问
根节点左子树各节点入栈并访问，各节点出栈
根节点右子树各节点入栈并访问，各节点出栈
根节点出栈

void preorder(BTNode *bt)
{
	if(bt!=NULL)
	{
		BTNode *STack[Maxsize];
		int top=-1;
		BTNode *p;
		Stack[++top]=bt;
		while(top!=-1)
		{
			p=Stack[top--];
			visit(p);
			if(p->rchild!=NULL)
				Stack[++top]=p->rchild;
			if(p->;child!=NULL)
				Stack[++top]=p->rchild;
		}
	}
}

模拟先序遍历：
根节点入栈
循环
-----栈顶元素出栈，访问；
-----栈顶元素右孩子入栈；左孩子入栈；
直到栈空

注意：真实递归的话是左子树先入栈，依次遍历并出栈后右子树才入栈。
我们这边模拟为了简化，是右孩子先入左孩子后入。以此实现先访问左孩子后访问右孩子。

中序：

while(top!=-1||p!=NULL)//存在节点出栈后栈空（根节点），但是p非空，右子树还可以入栈。
{
	while(p!=NULL)//一直向左入栈，直到节点没有左孩子
	{
		Stack[++top]=p;
		p=p->lchild;
	}
	if(top!==-1)//节点出栈，访问，右孩子
	{
		p=Stack[top--];
		visit[p];
		p=p->rchild;
	}
}

节点入栈时，节点左孩子入栈；
直到节点左孩子不存在，节点出栈，节点右孩子入栈；
直到栈空

后序：

while(top!=-1)//按根右左入栈1
{
	p=Stack1[top1--];
	Stack2[++top2]=p;//每次栈顶元素出栈都入栈2
	if(p->lchild!=NULL)
		Stack1[++top1]=p->lchild;
	if(p->rchild!=NULL)
		Stack1[++top1]=p->rchild;
}
whild(top2!=-1)//栈2就是根右左的逆序————>左右根
{
	p=Stack2[top2--];
	visit(p);
}

栈1中根右左顺序入栈2
栈2中即可实现逆序，左右根

深度遍历

DFS(G,V){
	......
	visit(v)
	visited[v]=1;
	for(w=g->adjlist[v1].firstarc;w!=NULL;w=w->nextarc)
	{
		if(visited[w]!=1)
		{
			DFS(g,w->adjvex);
		}
	}
}

访问v0；v0此时已在函数栈中
找v0的第一个为未访问的边；
找到就递归调用边指向的邻接点v1

访问邻接点v1；邻接点v1此时已在函数栈中
找v1的第一个为未访问的边；
找到就递归调用边指向的邻接点v2
没有找到就结束递归，v2出栈

回溯访问v0；v0此时还在函数栈中
找v0的第一个为未访问的边；（此时指向v1的边已经访问了）
找到就递归调用边指向的邻接点v3

int Stack[Maxsize],top=-1
visit(v);//访问第一个结点
visited[v]=1;
Stack(++top)=v//将初始结点进栈
while(top!=-1)//栈不为空
{
	v1=Stack(top);//将栈顶元素赋给v1
	p=g->adjlist[v1].firstarc;//该结点的第一条边
	while(p!=NULL&&visited[p->adjvwx]=1)//遍历该结点的adjlist,找到第一个未访问的邻接点
		p=p->nextarc;
	if(p==NULL)//遍历结束，该结点的所有邻接点都访问了
		---top;//该结点退栈
	else//找到邻接点
	{
		visit(p->adjvex);//访问邻接点
		visited[p->adjvex]=1;
		Stack(++top)=p->adjvex;//将邻接点入栈
	}
}

访问v0并入栈；
提取栈顶v0；找v0的第一个未访问的边；
找到了；访问边指向的邻接点v1并入栈
没找到；V0出栈

参考

[1] https://blog.csdn.net/fbz123456/article/details/50959412.
新开通了本人的公众号，欢迎关注：燕南路GISer ，专注GIS干货分享，不定期更新。
主要兴趣：GIS、时空数据挖掘、python、机器学习深度学习
提问、求资源等都可在公众号后台留言
CSDN的部分内容会重写再搬迁到公众号，欢迎关注！

1.递归函数：在函数内部自身调用自身的函数。

2.

 // 方法：

       1：找临界值：无须计算，即可得出的值：---退出递归的条件

       2：这一次和上一次运算的关系   fn和fn-1的关系  

       3：假设当前递归函数可以运行，根据上一次调用自身的结果，写出这次运算的结果。f(n)=f(n-1)+n=>f(10)=f(9)+10=f(8)+10+9

下面用递归 做几道题帮助理解

<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>

</body>

<script>
    // 递归函数：在函数内部自身调用自身的函数。
    // 	循环能做的所有事情  递归都能做
    // 	循环做不了的事情    递归也能做

    // 方法：
    // 	1：找临界值：无须计算，即可得出的值：---退出递归的条件
    // 	2：这一次和上一次运算的关系   fn和fn-1的关系  
    // 	3：假设当前递归函数可以运行，根据上一次调用自身的结果，写出这次运算的结果。f(n)=f(n-1)+n=>f(10)=f(9)+10=f(8)+10+9

    // 列：
    // 传入一个n，打印n个hello world   递归
    // f(n)=f(n-1)+console.log("hello world")
    // function printHello(n){
    // 	if (n==1) {
    // 		console.log("hello world")
    // 		return ;
    // 	}
    // 	console.log("hello world")
    // 	return printHello(n-1);
    // }

    // printHello(5)


    // 兔子繁殖问题：设有一对新生兔子，从第四个月开始他们每个月月初都生一对兔子,新生的兔子从第四个月月初开始又每个月生一对兔子
    // 	按此规律，并假定兔子没有死亡,n(n <= 20)个月月末共有多少对兔子？
    // 规律:  月份   	1 	2 	3 	4	5	6	7	8 	9 	10 ...
    // 	   	  兔子  		1	1   1   2   3   4	6	9	13	19
    // 规律:   f(n) = f(n-1)+f(n-3)
    // function rabbits(n) {
    //     if (n <= 3) {
    //         return 1;
    //     }
    //     return rabbits(n - 1) + rabbits(n - 3);
    // }

    // console.log(rabbits(20))
    // console.log(rabbits(10))


    // 	猴子吃桃问题：猴子第一天摘下若干个桃子，当即吃了一半，还不过瘾，又多吃了一个，第二天早上又将剩下的桃子吃掉一半，又多吃了一个。以后每天早上都吃前一天剩下的一半零一个。
	// 到第10天早上想再吃时，见只剩下一个桃子了。求第一天共摘多少个桃子？
	// 10   9   8    7   6   5    4    3    2    1  
	// 1    4	10	 22  46  94  190  382  766  1534

	// var sum = 1;
	// for (var i = 1; i < 10; i++) {
	// 	sum =(sum+1)*2;
	// }

	// console.log(sum)
	// 规律:  f(n) = (f(n+1)+1)*2

	// function getTotal(n) {
	// 	if (n == 10) {
	// 		return 1;
	// 	}
	// 	return (getTotal(n + 1) + 1) * 2;
	// }

	// console.log(getTotal(1))


</script>

</html>

3.递归实现深拷贝

深拷贝请看 个人另一篇文章 有详细解说

function deepClone(obj = {}) {
    if (typeof obj !== 'object' || obj == null) {
        // obj 是 null ，或者不是对象和数组，直接返回
        return obj
    }
 
    // 初始化返回结果
    let result
    if (obj instanceof Array) {
        result = []
    } else {
        result = {}
    }
 
    for (let key in obj) {
        // 保证 key 不是原型的属性
        if (obj.hasOwnProperty(key)) {
            // 递归调用！！！
            result[key] = deepClone(obj[key])
        }
    }
 
    // 返回结果
    return result
}

4.递归实现数组扁平化

<!DOCTYPE html>
<html>

<head>
  <meta charset="utf-8">
  <title>数组扁平化</title>
</head>

<body>

</body>
<script type="text/javascript">
  // 数组扁平化概念:数组扁平化是指将一个多维数组变为一维数组 
  // [1, [2, 3, [4, 5]]]  ------>    [1, 2, 3, 4, 5]

  // 5种方式实现数组扁平化  
  var arr = [1, [2, 3, [4, 5, [6, 7, 8, [9, 10]]]]]
  // flat 扁平化    Infinity  number  无穷大
  // console.log(arr.flat(Infinity))

  //  注意：flat和flatMap方法为ES2019(ES10)方法，目前还未在所有浏览器完全兼容。

  // function flatten1(arr){
  //   return  arr.flat(Infinity)
  // }

  // console.log(flatten1(arr))

  // 1.递归实现数组扁平化  递归的遍历每一项，若为数组则继续遍历，否则concat   重点
  // function flatten(arr) {
  //   var result = [];
  //   arr.map(item => {
  //     if (Array.isArray(item)) {
  //       result = result.concat(flatten(item))
  //     }
  //     // 不是数组
  //     else {
  //       result.push(item)
  //     }
  //   })
  //   return result
  // }

  // console.log(flatten(arr))







    // 2. reduce:遍历数组每一项，若值为数组则递归遍历，否则concat。


  //   function flatten4(arr) {  
  //     return arr.reduce((result, item)=> {
  //         return result.concat(Array.isArray(item) ? flatten4(item) : item);
  //     }, []);
  //  }

   // console.log(flatten4(arr))




    // 总结：遍历数组arr，若arr[i]为数组则递归遍历，直至arr[i]不为数组然后与之前的结果concat。 

</script>

</html>