递归找到最终推荐人.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 用递归用的是堆栈\n",
    "# 有时候深度深还没出栈，就超过了限度\n",
    "# 会有溢出的风险\n",
    "# 这时候我们可以限制调用的最大深度\n",
    "# 比如超过一千层之后就不在继续往下递归了，直接报错\n",
    "# 如果非要计算出来的话\n",
    "# 自己模拟个栈，使用非递归代码实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 还有一种优化方法就是比截面重复计算\n",
    "# 因为会分解大问题，后面可能遇到重复的\n",
    "# 所以通过一个数据结构来保存已经求解过的结果\n",
    "# 后面再遇到直接调用就行"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 如何递归改写成非递归\n",
    "# 其实也就是改成循环\n",
    "# 系统是根据栈来实现递归，我们就模拟栈行为\n",
    "# 比如二叉树中序遍历\n",
    "# 模拟递归的调用，保证栈中状态出入栈的顺序和递归的顺序一致\n",
    "# 循环就是用while True，用if else把树一个个填到栈中"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 快速排序就是用分治法把一个list分成较大和较小的两个子序列，然后递归排序\n",
    "# 选个基准值，然后所有比基准值小的放一边，剩下的放另外一边\n",
    "# int Partition(int le,int ri) //划分\n",
    "# {\n",
    "#     int tmp=a[le],pos=le;\n",
    "#     while(le<ri)\n",
    "#     {\n",
    "#         while(le<ri&&a[ri]>=tmp) ri--;\n",
    "#         a[pos]=a[ri];\n",
    "#         pos=ri;\n",
    "#         while(le<ri&&a[le]<=tmp) le++;\n",
    "#         a[pos]=a[le];\n",
    "#         pos=le;\n",
    "#     }\n",
    "#     a[pos]=tmp;\n",
    "#     return pos;\n",
    "# }\n",
    "# void Qsort(int le,int ri) //递归版本\n",
    "# {\n",
    "#     if(le<ri)\n",
    "#     {\n",
    "#         int p=Partition(le,ri);\n",
    "#         Qsort(le,p-1);\n",
    "#         Qsort(p+1,ri);\n",
    "#     }\n",
    "# }\n",
    "# void QsortLoop(int n) //循环版本\n",
    "# {\n",
    "#     int i;\n",
    "#     record cur(1,n,0),now;\n",
    "#     stack<record>s;\n",
    "#     while(1)\n",
    "#     {\n",
    "#         //getchar();\n",
    "#         //printf(\"%d %d %d\\n\",cur.le,cur.ri,cur.state);\n",
    "#         if(cur.le<cur.ri)\n",
    "#         {\n",
    "#             if(cur.state==0) //划分 向下递归 保存本层下次递归状态\n",
    "#             {\n",
    "#                 int p=Partition(cur.le,cur.ri);\n",
    "#                 now.le=p+1; now.ri=cur.ri; now.state=1;\n",
    "#                 s.push(now);\n",
    "#                 cur.ri=p-1;\n",
    "#             }\n",
    "#             else if(cur.state==1) //向下递归 保存本层下次递归状态\n",
    "#             {\n",
    "#                 now=cur; now.state=2;\n",
    "#                 s.push(now);\n",
    "#                 cur.state=0;\n",
    "#             }\n",
    "#             else\n",
    "#             {\n",
    "#                 if(s.empty()) break ; //栈内没有节点退出\n",
    "#                 cur=s.top();\n",
    "#                 s.pop();\n",
    "#             }\n",
    "#         }\n",
    "#         else //递归返回\n",
    "#         {\n",
    "#             if(s.empty()) break ; //栈内没有节点退出  不加这句可以试一试2 1 2\n",
    "#             cur=s.top();\n",
    "#             s.pop();\n",
    "#         }\n",
    "#     }\n",
    "# }\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}