{"id":159,"date":"2022-02-03T14:52:26","date_gmt":"2022-02-03T14:52:26","guid":{"rendered":"https:\/\/liangqi.org\/?p=159"},"modified":"2022-02-03T14:52:26","modified_gmt":"2022-02-03T14:52:26","slug":"recursive%e9%80%92%e5%bd%92%e7%9a%84%e6%97%b6%e9%97%b4%e7%a9%ba%e9%97%b4%e5%a4%8d%e6%9d%82%e5%ba%a6%e8%ae%a1%e7%ae%97","status":"publish","type":"post","link":"https:\/\/liangqi.org\/?p=159","title":{"rendered":"Recursive\u9012\u5f52\u7684\u65f6\u95f4\u7a7a\u95f4\u590d\u6742\u5ea6\u8ba1\u7b97"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\" id=\"\u57fa\u672c\u6982\u5ff5\">\u57fa\u672c\u6982\u5ff5<\/h2>\n\n\n\n<p>\u9012\u5f52\u53ef\u4ee5\u5c42\u6b21\u53ef\u4ee5\u901a\u8fc7tree\u7684\u5f62\u5f0f\u5c55\u73b0\u3002<\/p>\n\n\n\n<p>\u6bd4\u5982\u4e0b\u9762\u7684\u9012\u5f52\uff1a<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>int f(int n) {\n  if (n &lt;= 1) {\n    return 1;\n  }\n  return f(n - 1) + f(n - 1);\n} <\/code><\/pre>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"490\" height=\"474\" src=\"https:\/\/liangqi.org\/wp-content\/uploads\/2022\/02\/image.png\" alt=\"\" class=\"wp-image-160\" srcset=\"https:\/\/liangqi.org\/wp-content\/uploads\/2022\/02\/image.png 490w, https:\/\/liangqi.org\/wp-content\/uploads\/2022\/02\/image-300x290.png 300w\" sizes=\"auto, (max-width: 490px) 100vw, 490px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"536\" src=\"https:\/\/liangqi.org\/wp-content\/uploads\/2022\/02\/image-1-1024x536.png\" alt=\"\" class=\"wp-image-161\" srcset=\"https:\/\/liangqi.org\/wp-content\/uploads\/2022\/02\/image-1-1024x536.png 1024w, https:\/\/liangqi.org\/wp-content\/uploads\/2022\/02\/image-1-300x157.png 300w, https:\/\/liangqi.org\/wp-content\/uploads\/2022\/02\/image-1-768x402.png 768w, https:\/\/liangqi.org\/wp-content\/uploads\/2022\/02\/image-1-1140x597.png 1140w, https:\/\/liangqi.org\/wp-content\/uploads\/2022\/02\/image-1.png 1302w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>\u65f6\u95f4\u590d\u6742\u5ea6:<br>\u5c31\u662f\u603b\u7684\u6811\u7684\u8282\u70b9s\u6570\u3002\u5982\u679c\u6bcf\u4e00\u6b21\u5c42\u5d4c\u5957\u90fd\u5305\u6db52\u5c42\u5e73\u884c\u7684call\uff0c\u90a3\u65f6\u95f4\u590d\u6742\u5ea6\u5c31\u662fO(2^N).\u5982\u679c\u6709\u56db\u5c42\uff0c\u90a3\u4e48\u5c31\u662fO\uff084^N).<\/p>\n\n\n\n<p>\u7a7a\u95f4\u590d\u6742\u5ea6:<br>\u5c31\u662f\u603b\u7684\u6811\u7684\u6df1\u5ea6\u3002\u5728\u8fd9\u91cc\u5c31\u662fN<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"\u6df1\u5ea6\u4f18\u5148\u7b97\u6cd5-dfs-depth-first-search\">\u6df1\u5ea6\u4f18\u5148\u7b97\u6cd5(DFS: Depth  First Search)<\/h2>\n\n\n\n<p>\u6df1\u5ea6\u4f18\u5148\u7b97\u6cd5\u662f\u4e00\u4e2a\u9012\u5f52\u8c03\u7528\u3002\u5bf9\u4e8e\u56fe\u7684\u6df1\u5ea6\u4f18\u5148\uff0c\u6211\u4eec\u6709Vertices\u548cEdge\u7684\u6570\u91cf\uff0c\u5206\u522b\u7528V\u548cE\u6765\u8868\u793a\u3002<\/p>\n\n\n\n<p>\u65f6\u95f4\u590d\u6742\u5ea6\uff1a<br>\u56e0\u4e3a\u662f\u56fe\uff0c\u6240\u4ee5\u5728\u9012\u5f52\u7684\u65f6\u5019\u6bcf\u4e00\u6b21\u5c42\u6709\u591a\u5c11\u8282\u70b9\u662f\u4e0d\u77e5\u9053\u7684\uff0c\u6240\u4ee5\u6ca1\u529e\u6cd5\u6309\u71672^n\u7684\u666e\u904d\u7b97\u6cd5\u6765\u7b97\u3002\u4f46\u662f\u6362\u4e00\u4e2a\u601d\u8def\u5c31\u662f\u65e0\u8bba\u5982\u4f55\u6bcf\u6761\u8fb9\u90fd\u81f3\u5c11\u9700\u8981\u8d70\u4e00\u904d\u3002<br>\u65f6\u95f4\u590d\u6742\u5ea6\u5c31\u662f\u603b\u7684\u8fb9\u7684\u6570\u91cf\uff0c\u6bcf\u6761\u8fb9\u4f1a\u88ab\u8bbf\u95ee\u4e24\u6b21\uff0c\u4e00\u6b21\u662f\u904d\u5386\uff0c\u4e00\u6b21\u662f\u4f1a\u9000\u3002O(E).<\/p>\n\n\n\n<p>\u7a7a\u95f4\u590d\u6742: <br>\u5982\u679c\u6240\u6709\u7684Vertices\u90fd\u662f\u76f8\u8fde\u7684\uff0c\u90a3\u4e48\u5c31\u4f1a\u6709V\u5c42\u6df1\u5ea6\u7684\u4e66\u3002\u90a3\u7a7a\u95f4\u590d\u6742\u5ea6\u5c31\u662fO(V)<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"\u5e7f\u5ea6\u4f18\u5148\u7b97\u6cd5-bfs-breadth-first-search\">\u5e7f\u5ea6\u4f18\u5148\u7b97\u6cd5(BFS: Breadth First Search)<\/h2>\n\n\n\n<p><em>todo<\/em><\/p>\n\n\n\n<p>\u65f6\u95f4\u590d\u6742\u5ea6:<\/p>\n\n\n\n<p>O(V+E). \u8fd9\u91cc\u4e0d\u662f\u8bf4O(E)\u6bd4O\uff08V+E\uff09\u597d\u3002\u5176\u5b9eO(E)\u662fO(2E).\u56e0\u4e3a\u590d\u6742\u5ea6\u8ba1\u7b97\u5ffd\u7565\u5e38\u91cf\uff0c\u8fd9\u91cc\u5bb9\u6613\u5f15\u8d77\u8bef\u89e3\u3002<\/p>\n\n\n\n<p>\u7a7a\u95f4\u590d\u6742: <\/p>\n\n\n\n<p>O(V)<\/p>\n\n\n\n<p>Reference: <\/p>\n\n\n\n<p><a href=\"https:\/\/stackoverflow.com\/questions\/43298938\/space-complexity-of-recursive-function\" target=\"_blank\" rel=\"noreferrer noopener\">https:\/\/stackoverflow.com\/questions\/43298938\/space-complexity-of-recursive-function<\/a><br><a href=\"https:\/\/zhuanlan.zhihu.com\/p\/95081559#:~:text=%E5%9C%A8%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95,%E5%BA%A6%E4%B8%BAO(V)%E3%80%82\" target=\"_blank\" rel=\"noreferrer noopener\">https:\/\/zhuanlan.zhihu.com\/p\/95081559#:~:text=%E5%9C%A8%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95,%E5%BA%A6%E4%B8%BAO(V)%E3%80%82<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u57fa\u672c\u6982\u5ff5 \u9012\u5f52\u53ef\u4ee5\u5c42\u6b21\u53ef\u4ee5\u901a\u8fc7tree\u7684\u5f62\u5f0f\u5c55\u73b0\u3002 \u6bd4\u5982\u4e0b\u9762\u7684\u9012\u5f52\uff1a \u65f6\u95f4\u590d\u6742\u5ea6:\u5c31\u662f\u603b\u7684\u6811\u7684\u8282\u70b9s\u6570\u3002\u5982\u679c\u6bcf\u4e00\u6b21\u5c42\u5d4c\u5957\u90fd\u5305\u6db52\u5c42\u5e73\u884c\u7684call\uff0c\u90a3\u65f6\u95f4\u590d\u6742\u5ea6\u5c31\u662fO(2^N).\u5982\u679c\u6709\u56db\u5c42\uff0c\u90a3\u4e48\u5c31\u662fO\uff084^N). \u7a7a\u95f4\u590d\u6742\u5ea6:\u5c31\u662f\u603b\u7684\u6811\u7684\u6df1\u5ea6\u3002\u5728\u8fd9\u91cc\u5c31\u662fN \u6df1\u5ea6\u4f18\u5148\u7b97\u6cd5(DFS: Depth First Search) \u6df1\u5ea6\u4f18\u5148\u7b97\u6cd5\u662f\u4e00\u4e2a\u9012\u5f52\u8c03\u7528\u3002\u5bf9\u4e8e\u56fe\u7684\u6df1\u5ea6\u4f18\u5148\uff0c\u6211\u4eec\u6709Vertices\u548cEdge\u7684\u6570\u91cf\uff0c\u5206\u522b\u7528V\u548cE\u6765\u8868\u793a\u3002 \u65f6\u95f4\u590d\u6742\u5ea6\uff1a\u56e0\u4e3a\u662f\u56fe\uff0c\u6240\u4ee5\u5728\u9012\u5f52\u7684\u65f6\u5019\u6bcf\u4e00\u6b21\u5c42\u6709\u591a\u5c11\u8282\u70b9\u662f\u4e0d\u77e5\u9053\u7684\uff0c\u6240\u4ee5\u6ca1\u529e\u6cd5\u6309\u71672^n\u7684\u666e\u904d\u7b97\u6cd5\u6765\u7b97\u3002\u4f46\u662f\u6362\u4e00\u4e2a\u601d\u8def\u5c31\u662f\u65e0\u8bba\u5982\u4f55\u6bcf\u6761\u8fb9\u90fd\u81f3\u5c11\u9700\u8981\u8d70\u4e00\u904d\u3002\u65f6\u95f4\u590d\u6742\u5ea6\u5c31\u662f\u603b\u7684\u8fb9\u7684\u6570\u91cf\uff0c\u6bcf\u6761\u8fb9\u4f1a\u88ab\u8bbf\u95ee\u4e24\u6b21\uff0c\u4e00\u6b21\u662f\u904d\u5386\uff0c\u4e00\u6b21\u662f\u4f1a\u9000\u3002O(E). \u7a7a\u95f4\u590d\u6742: \u5982\u679c\u6240\u6709\u7684Vertices\u90fd\u662f\u76f8\u8fde\u7684\uff0c\u90a3\u4e48\u5c31\u4f1a\u6709V\u5c42\u6df1\u5ea6\u7684\u4e66\u3002\u90a3\u7a7a\u95f4\u590d\u6742\u5ea6\u5c31\u662fO(V) \u5e7f\u5ea6\u4f18\u5148\u7b97\u6cd5(BFS: Breadth First Search) todo \u65f6\u95f4\u590d\u6742\u5ea6: O(V+E). \u8fd9\u91cc\u4e0d\u662f\u8bf4O(E)\u6bd4O\uff08V+E\uff09\u597d\u3002\u5176\u5b9eO(E)\u662fO(2E).\u56e0\u4e3a\u590d\u6742\u5ea6\u8ba1\u7b97\u5ffd\u7565\u5e38\u91cf\uff0c\u8fd9\u91cc\u5bb9\u6613\u5f15\u8d77\u8bef\u89e3\u3002 \u7a7a\u95f4\u590d\u6742: O(V) Reference: https:\/\/stackoverflow.com\/questions\/43298938\/space-complexity-of-recursive-functionhttps:\/\/zhuanlan.zhihu.com\/p\/95081559#:~:text=%E5%9C%A8%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95,%E5%BA%A6%E4%B8%BAO(V)%E3%80%82<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[16,17],"tags":[],"class_list":["post-159","post","type-post","status-publish","format-standard","hentry","category-16","category-17"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v21.7 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Recursive\u9012\u5f52\u7684\u65f6\u95f4\u7a7a\u95f4\u590d\u6742\u5ea6\u8ba1\u7b97 - Liangqi\u2018s Technical Journey<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/liangqi.org\/?p=159\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Recursive\u9012\u5f52\u7684\u65f6\u95f4\u7a7a\u95f4\u590d\u6742\u5ea6\u8ba1\u7b97 - Liangqi\u2018s Technical Journey\" \/>\n<meta property=\"og:description\" content=\"\u57fa\u672c\u6982\u5ff5 \u9012\u5f52\u53ef\u4ee5\u5c42\u6b21\u53ef\u4ee5\u901a\u8fc7tree\u7684\u5f62\u5f0f\u5c55\u73b0\u3002 \u6bd4\u5982\u4e0b\u9762\u7684\u9012\u5f52\uff1a \u65f6\u95f4\u590d\u6742\u5ea6:\u5c31\u662f\u603b\u7684\u6811\u7684\u8282\u70b9s\u6570\u3002\u5982\u679c\u6bcf\u4e00\u6b21\u5c42\u5d4c\u5957\u90fd\u5305\u6db52\u5c42\u5e73\u884c\u7684call\uff0c\u90a3\u65f6\u95f4\u590d\u6742\u5ea6\u5c31\u662fO(2^N).\u5982\u679c\u6709\u56db\u5c42\uff0c\u90a3\u4e48\u5c31\u662fO\uff084^N). \u7a7a\u95f4\u590d\u6742\u5ea6:\u5c31\u662f\u603b\u7684\u6811\u7684\u6df1\u5ea6\u3002\u5728\u8fd9\u91cc\u5c31\u662fN \u6df1\u5ea6\u4f18\u5148\u7b97\u6cd5(DFS: Depth First Search) \u6df1\u5ea6\u4f18\u5148\u7b97\u6cd5\u662f\u4e00\u4e2a\u9012\u5f52\u8c03\u7528\u3002\u5bf9\u4e8e\u56fe\u7684\u6df1\u5ea6\u4f18\u5148\uff0c\u6211\u4eec\u6709Vertices\u548cEdge\u7684\u6570\u91cf\uff0c\u5206\u522b\u7528V\u548cE\u6765\u8868\u793a\u3002 \u65f6\u95f4\u590d\u6742\u5ea6\uff1a\u56e0\u4e3a\u662f\u56fe\uff0c\u6240\u4ee5\u5728\u9012\u5f52\u7684\u65f6\u5019\u6bcf\u4e00\u6b21\u5c42\u6709\u591a\u5c11\u8282\u70b9\u662f\u4e0d\u77e5\u9053\u7684\uff0c\u6240\u4ee5\u6ca1\u529e\u6cd5\u6309\u71672^n\u7684\u666e\u904d\u7b97\u6cd5\u6765\u7b97\u3002\u4f46\u662f\u6362\u4e00\u4e2a\u601d\u8def\u5c31\u662f\u65e0\u8bba\u5982\u4f55\u6bcf\u6761\u8fb9\u90fd\u81f3\u5c11\u9700\u8981\u8d70\u4e00\u904d\u3002\u65f6\u95f4\u590d\u6742\u5ea6\u5c31\u662f\u603b\u7684\u8fb9\u7684\u6570\u91cf\uff0c\u6bcf\u6761\u8fb9\u4f1a\u88ab\u8bbf\u95ee\u4e24\u6b21\uff0c\u4e00\u6b21\u662f\u904d\u5386\uff0c\u4e00\u6b21\u662f\u4f1a\u9000\u3002O(E). \u7a7a\u95f4\u590d\u6742: \u5982\u679c\u6240\u6709\u7684Vertices\u90fd\u662f\u76f8\u8fde\u7684\uff0c\u90a3\u4e48\u5c31\u4f1a\u6709V\u5c42\u6df1\u5ea6\u7684\u4e66\u3002\u90a3\u7a7a\u95f4\u590d\u6742\u5ea6\u5c31\u662fO(V) \u5e7f\u5ea6\u4f18\u5148\u7b97\u6cd5(BFS: Breadth First Search) todo \u65f6\u95f4\u590d\u6742\u5ea6: O(V+E). \u8fd9\u91cc\u4e0d\u662f\u8bf4O(E)\u6bd4O\uff08V+E\uff09\u597d\u3002\u5176\u5b9eO(E)\u662fO(2E).\u56e0\u4e3a\u590d\u6742\u5ea6\u8ba1\u7b97\u5ffd\u7565\u5e38\u91cf\uff0c\u8fd9\u91cc\u5bb9\u6613\u5f15\u8d77\u8bef\u89e3\u3002 \u7a7a\u95f4\u590d\u6742: O(V) Reference: https:\/\/stackoverflow.com\/questions\/43298938\/space-complexity-of-recursive-functionhttps:\/\/zhuanlan.zhihu.com\/p\/95081559#:~:text=%E5%9C%A8%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95,%E5%BA%A6%E4%B8%BAO(V)%E3%80%82\" \/>\n<meta property=\"og:url\" content=\"https:\/\/liangqi.org\/?p=159\" \/>\n<meta property=\"og:site_name\" content=\"Liangqi\u2018s Technical Journey\" \/>\n<meta property=\"article:published_time\" content=\"2022-02-03T14:52:26+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/liangqi.org\/wp-content\/uploads\/2022\/02\/image.png\" \/>\n<meta name=\"author\" content=\"liangqi\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"liangqi\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"1 minute\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/liangqi.org\/?p=159#article\",\"isPartOf\":{\"@id\":\"https:\/\/liangqi.org\/?p=159\"},\"author\":{\"name\":\"liangqi\",\"@id\":\"https:\/\/liangqi.org\/#\/schema\/person\/105c89d9b783fda67b62e3ce113d6cd3\"},\"headline\":\"Recursive\u9012\u5f52\u7684\u65f6\u95f4\u7a7a\u95f4\u590d\u6742\u5ea6\u8ba1\u7b97\",\"datePublished\":\"2022-02-03T14:52:26+00:00\",\"dateModified\":\"2022-02-03T14:52:26+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/liangqi.org\/?p=159\"},\"wordCount\":84,\"commentCount\":0,\"publisher\":{\"@id\":\"https:\/\/liangqi.org\/#\/schema\/person\/105c89d9b783fda67b62e3ce113d6cd3\"},\"articleSection\":[\"\u6280\u672f\",\"\u7b97\u6cd5\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/liangqi.org\/?p=159#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/liangqi.org\/?p=159\",\"url\":\"https:\/\/liangqi.org\/?p=159\",\"name\":\"Recursive\u9012\u5f52\u7684\u65f6\u95f4\u7a7a\u95f4\u590d\u6742\u5ea6\u8ba1\u7b97 - Liangqi\u2018s Technical Journey\",\"isPartOf\":{\"@id\":\"https:\/\/liangqi.org\/#website\"},\"datePublished\":\"2022-02-03T14:52:26+00:00\",\"dateModified\":\"2022-02-03T14:52:26+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/liangqi.org\/?p=159#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/liangqi.org\/?p=159\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/liangqi.org\/?p=159#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/liangqi.org\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Recursive\u9012\u5f52\u7684\u65f6\u95f4\u7a7a\u95f4\u590d\u6742\u5ea6\u8ba1\u7b97\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/liangqi.org\/#website\",\"url\":\"https:\/\/liangqi.org\/\",\"name\":\"Liangqi\u2018s Technical Journey\",\"description\":\"Chasing Excellence; Enjoy life.\",\"publisher\":{\"@id\":\"https:\/\/liangqi.org\/#\/schema\/person\/105c89d9b783fda67b62e3ce113d6cd3\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/liangqi.org\/?s={search_term_string}\"},\"query-input\":\"required name=search_term_string\"}],\"inLanguage\":\"en-US\"},{\"@type\":[\"Person\",\"Organization\"],\"@id\":\"https:\/\/liangqi.org\/#\/schema\/person\/105c89d9b783fda67b62e3ce113d6cd3\",\"name\":\"liangqi\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/liangqi.org\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/liangqi.org\/wp-content\/uploads\/2022\/01\/P1100089-3-scaled.jpg\",\"contentUrl\":\"https:\/\/liangqi.org\/wp-content\/uploads\/2022\/01\/P1100089-3-scaled.jpg\",\"width\":2560,\"height\":1920,\"caption\":\"liangqi\"},\"logo\":{\"@id\":\"https:\/\/liangqi.org\/#\/schema\/person\/image\/\"},\"sameAs\":[\"https:\/\/liangqi.org\"],\"url\":\"https:\/\/liangqi.org\/?author=1\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Recursive\u9012\u5f52\u7684\u65f6\u95f4\u7a7a\u95f4\u590d\u6742\u5ea6\u8ba1\u7b97 - Liangqi\u2018s Technical Journey","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/liangqi.org\/?p=159","og_locale":"en_US","og_type":"article","og_title":"Recursive\u9012\u5f52\u7684\u65f6\u95f4\u7a7a\u95f4\u590d\u6742\u5ea6\u8ba1\u7b97 - Liangqi\u2018s Technical Journey","og_description":"\u57fa\u672c\u6982\u5ff5 \u9012\u5f52\u53ef\u4ee5\u5c42\u6b21\u53ef\u4ee5\u901a\u8fc7tree\u7684\u5f62\u5f0f\u5c55\u73b0\u3002 \u6bd4\u5982\u4e0b\u9762\u7684\u9012\u5f52\uff1a \u65f6\u95f4\u590d\u6742\u5ea6:\u5c31\u662f\u603b\u7684\u6811\u7684\u8282\u70b9s\u6570\u3002\u5982\u679c\u6bcf\u4e00\u6b21\u5c42\u5d4c\u5957\u90fd\u5305\u6db52\u5c42\u5e73\u884c\u7684call\uff0c\u90a3\u65f6\u95f4\u590d\u6742\u5ea6\u5c31\u662fO(2^N).\u5982\u679c\u6709\u56db\u5c42\uff0c\u90a3\u4e48\u5c31\u662fO\uff084^N). \u7a7a\u95f4\u590d\u6742\u5ea6:\u5c31\u662f\u603b\u7684\u6811\u7684\u6df1\u5ea6\u3002\u5728\u8fd9\u91cc\u5c31\u662fN \u6df1\u5ea6\u4f18\u5148\u7b97\u6cd5(DFS: Depth First Search) \u6df1\u5ea6\u4f18\u5148\u7b97\u6cd5\u662f\u4e00\u4e2a\u9012\u5f52\u8c03\u7528\u3002\u5bf9\u4e8e\u56fe\u7684\u6df1\u5ea6\u4f18\u5148\uff0c\u6211\u4eec\u6709Vertices\u548cEdge\u7684\u6570\u91cf\uff0c\u5206\u522b\u7528V\u548cE\u6765\u8868\u793a\u3002 \u65f6\u95f4\u590d\u6742\u5ea6\uff1a\u56e0\u4e3a\u662f\u56fe\uff0c\u6240\u4ee5\u5728\u9012\u5f52\u7684\u65f6\u5019\u6bcf\u4e00\u6b21\u5c42\u6709\u591a\u5c11\u8282\u70b9\u662f\u4e0d\u77e5\u9053\u7684\uff0c\u6240\u4ee5\u6ca1\u529e\u6cd5\u6309\u71672^n\u7684\u666e\u904d\u7b97\u6cd5\u6765\u7b97\u3002\u4f46\u662f\u6362\u4e00\u4e2a\u601d\u8def\u5c31\u662f\u65e0\u8bba\u5982\u4f55\u6bcf\u6761\u8fb9\u90fd\u81f3\u5c11\u9700\u8981\u8d70\u4e00\u904d\u3002\u65f6\u95f4\u590d\u6742\u5ea6\u5c31\u662f\u603b\u7684\u8fb9\u7684\u6570\u91cf\uff0c\u6bcf\u6761\u8fb9\u4f1a\u88ab\u8bbf\u95ee\u4e24\u6b21\uff0c\u4e00\u6b21\u662f\u904d\u5386\uff0c\u4e00\u6b21\u662f\u4f1a\u9000\u3002O(E). \u7a7a\u95f4\u590d\u6742: \u5982\u679c\u6240\u6709\u7684Vertices\u90fd\u662f\u76f8\u8fde\u7684\uff0c\u90a3\u4e48\u5c31\u4f1a\u6709V\u5c42\u6df1\u5ea6\u7684\u4e66\u3002\u90a3\u7a7a\u95f4\u590d\u6742\u5ea6\u5c31\u662fO(V) \u5e7f\u5ea6\u4f18\u5148\u7b97\u6cd5(BFS: Breadth First Search) todo \u65f6\u95f4\u590d\u6742\u5ea6: O(V+E). \u8fd9\u91cc\u4e0d\u662f\u8bf4O(E)\u6bd4O\uff08V+E\uff09\u597d\u3002\u5176\u5b9eO(E)\u662fO(2E).\u56e0\u4e3a\u590d\u6742\u5ea6\u8ba1\u7b97\u5ffd\u7565\u5e38\u91cf\uff0c\u8fd9\u91cc\u5bb9\u6613\u5f15\u8d77\u8bef\u89e3\u3002 \u7a7a\u95f4\u590d\u6742: O(V) Reference: https:\/\/stackoverflow.com\/questions\/43298938\/space-complexity-of-recursive-functionhttps:\/\/zhuanlan.zhihu.com\/p\/95081559#:~:text=%E5%9C%A8%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2%E7%AE%97%E6%B3%95,%E5%BA%A6%E4%B8%BAO(V)%E3%80%82","og_url":"https:\/\/liangqi.org\/?p=159","og_site_name":"Liangqi\u2018s Technical Journey","article_published_time":"2022-02-03T14:52:26+00:00","og_image":[{"url":"https:\/\/liangqi.org\/wp-content\/uploads\/2022\/02\/image.png"}],"author":"liangqi","twitter_card":"summary_large_image","twitter_misc":{"Written by":"liangqi","Est. reading time":"1 minute"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/liangqi.org\/?p=159#article","isPartOf":{"@id":"https:\/\/liangqi.org\/?p=159"},"author":{"name":"liangqi","@id":"https:\/\/liangqi.org\/#\/schema\/person\/105c89d9b783fda67b62e3ce113d6cd3"},"headline":"Recursive\u9012\u5f52\u7684\u65f6\u95f4\u7a7a\u95f4\u590d\u6742\u5ea6\u8ba1\u7b97","datePublished":"2022-02-03T14:52:26+00:00","dateModified":"2022-02-03T14:52:26+00:00","mainEntityOfPage":{"@id":"https:\/\/liangqi.org\/?p=159"},"wordCount":84,"commentCount":0,"publisher":{"@id":"https:\/\/liangqi.org\/#\/schema\/person\/105c89d9b783fda67b62e3ce113d6cd3"},"articleSection":["\u6280\u672f","\u7b97\u6cd5"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/liangqi.org\/?p=159#respond"]}]},{"@type":"WebPage","@id":"https:\/\/liangqi.org\/?p=159","url":"https:\/\/liangqi.org\/?p=159","name":"Recursive\u9012\u5f52\u7684\u65f6\u95f4\u7a7a\u95f4\u590d\u6742\u5ea6\u8ba1\u7b97 - Liangqi\u2018s Technical Journey","isPartOf":{"@id":"https:\/\/liangqi.org\/#website"},"datePublished":"2022-02-03T14:52:26+00:00","dateModified":"2022-02-03T14:52:26+00:00","breadcrumb":{"@id":"https:\/\/liangqi.org\/?p=159#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/liangqi.org\/?p=159"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/liangqi.org\/?p=159#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/liangqi.org\/"},{"@type":"ListItem","position":2,"name":"Recursive\u9012\u5f52\u7684\u65f6\u95f4\u7a7a\u95f4\u590d\u6742\u5ea6\u8ba1\u7b97"}]},{"@type":"WebSite","@id":"https:\/\/liangqi.org\/#website","url":"https:\/\/liangqi.org\/","name":"Liangqi\u2018s Technical Journey","description":"Chasing Excellence; Enjoy life.","publisher":{"@id":"https:\/\/liangqi.org\/#\/schema\/person\/105c89d9b783fda67b62e3ce113d6cd3"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/liangqi.org\/?s={search_term_string}"},"query-input":"required name=search_term_string"}],"inLanguage":"en-US"},{"@type":["Person","Organization"],"@id":"https:\/\/liangqi.org\/#\/schema\/person\/105c89d9b783fda67b62e3ce113d6cd3","name":"liangqi","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/liangqi.org\/#\/schema\/person\/image\/","url":"https:\/\/liangqi.org\/wp-content\/uploads\/2022\/01\/P1100089-3-scaled.jpg","contentUrl":"https:\/\/liangqi.org\/wp-content\/uploads\/2022\/01\/P1100089-3-scaled.jpg","width":2560,"height":1920,"caption":"liangqi"},"logo":{"@id":"https:\/\/liangqi.org\/#\/schema\/person\/image\/"},"sameAs":["https:\/\/liangqi.org"],"url":"https:\/\/liangqi.org\/?author=1"}]}},"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/liangqi.org\/index.php?rest_route=\/wp\/v2\/posts\/159","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/liangqi.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/liangqi.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/liangqi.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/liangqi.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=159"}],"version-history":[{"count":6,"href":"https:\/\/liangqi.org\/index.php?rest_route=\/wp\/v2\/posts\/159\/revisions"}],"predecessor-version":[{"id":167,"href":"https:\/\/liangqi.org\/index.php?rest_route=\/wp\/v2\/posts\/159\/revisions\/167"}],"wp:attachment":[{"href":"https:\/\/liangqi.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=159"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/liangqi.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=159"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/liangqi.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=159"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}