{"id":556,"date":"2007-03-05T11:24:00","date_gmt":"2007-03-05T03:24:00","guid":{"rendered":"http:\/\/note.systw.net\/note\/?p=556"},"modified":"2023-11-04T11:26:56","modified_gmt":"2023-11-04T03:26:56","slug":"recursive","status":"publish","type":"post","link":"https:\/\/systw.net\/note\/archives\/556","title":{"rendered":"Recursive"},"content":{"rendered":"\n

recursive(\u905e\u8ff4)
\u7c21\u6f54\u6613\u61c2,\u4f46\u6548\u7387\u5dee,\u9069\u5408\u63cf\u8ff0\u6f14\u7b97\u6cd5
\u53ef\u5206\u70ba\u4ee5\u4e0b3\u7a2e:
direct recursion:\u76f4\u63a5\u547c\u53eb\u81ea\u5df1
indirect recursion:\u5148\u547c\u53eb\u5176\u5b83\u7a0b\u5e8f\u82e5\u5e72\u5c64\u5f8c,\u6700\u5f8c\u53c8\u547c\u53eb\u56de\u81ea\u5df1
tail recursion:\u5728\u6700\u5f8c\u4e00\u500b\u547d\u4ee4\u53c8\u547c\u53eb\u81ea\u5df1\u672c\u8eab(\u7531\u65bc\u5c3e\u7aef\u905e\u8ff4\u7684\u8fd4\u56de\u4f4d\u5740\u662f\u7a0b\u5f0f\u7684\u7d50\u675f\u6307\u4ee4,\u5373\u6642\u8fd4\u56de\u4e5f\u4e0d\u9700\u9032\u884c\u8655\u7406)
\u82e5\u628a\u6b64\u6539\u6389,\u53ef\u4ee5\u4e0d\u9700\u8981\u5132\u5b58\u8fd4\u56de\u4f4d\u5740\u8207\u7a0b\u5f0f\u72c0\u614b,\u800c\u80fd\u5920\u63d0\u6607\u57f7\u884c\u6548\u7387<\/p>\n\n\n\n

\u905e\u8ff4\u51fd\u6578=\u57fa\u672c\u5143\u7d20+\u5efa\u7acb\u5176\u4ed6\u65b0\u5143\u7d20\u6240\u9700\u898f\u5247
\u905e\u8ff4\u6f14\u7b97\u6cd5=\u905e\u8ff4\u95dc\u4fc2+\u7d42\u6b62\u689d\u4ef6(\u9700\u6709\u4e00\u689d\u8def\u5f91\u4e0d\u518d\u9032\u884c\u905e\u8ff4\u547c\u53eb)
(\u82e5\u7121\u6cd5\u5230\u9054\u7d42\u6b62\u689d\u4ef6\u6703\u9020\u6210\u7121\u7aae\u8ff4\u7aae)<\/p>\n\n\n\n

\u5206\u6790\u905e\u8ff4\u8907\u96dc\u5ea6\u7684\u5de5\u5177:
\u905e\u8ff4\u6a39:\u7528\u6a39\u72c0\u7d50\u69cb\u8868\u793a\u905e\u8ff4\u7684\u547c\u53eb\u60c5\u6cc1
\u905e\u8ff4\u95dc\u4fc2\u5f0f=\u7528\u95dc\u4fc2\u5f0f\u8868\u793a\u547c\u53eb\u905e\u8ff4\u7684\u95dc\u4fc2<\/p>\n\n\n\n

\u7576\u905e\u8ff4\u95dc\u4fc2\u5f0f\u53ef\u8868\u793a\u6210\u70ba:
T(n)=a<\/strong>T(n\/b<\/strong>)+c<\/strong>n^k<\/strong>,a\u8207b=\u6574\u6578\u5e38\u6578,c\u8207k\u70ba\u6b63\u5e38\u6578,a>=1,b>=2,\u5728\u6bd4\u8f03a,b^k\u5927\u5c0f\u95dc\u4fc2,\u53ef\u4ee5\u5f97\u5230:
T(n)={
\u3000O(n^logb(a)),if a< b^k
\u3000O(n^k log n),if a=b^k
\u3000O(n^k),if a< b^k <\/p>\n\n\n\n

removal of recursion \u905e\u8ff4\u8f49\u6210\u975e\u905e\u8ff4
1\u5806\u758a\u6cd5:indirect recursion\u548cdirect recursion\u8655\u7406\u7a0d\u6709\u4e0d\u540c
2folding(\u6298\u758a\u6cd5)<\/p>\n\n\n\n

……………..<\/p>\n\n\n\n

fibonacci(\u8cbb\u6c0f\u6578\u5217)<\/strong>\u00a0O(2^n)
\u905e\u56de\u8ff4\u95dc\u4fc2\u5f0f:t(n){0,if n=0; 1,if n=1; t(n-1)+t(n-2)+c,otherwise
\u63a8\u5c0e\u904e\u7a0b:t(n-1)+t(n-2)+c=t(t(n-2)+t(n-3)+c<\/strong>)+t(t(n-3)+t(n-4)+c<\/strong>)+c=…2^(n-1)*t(1)+(2^(n-1)-1)*c
\u6240\u4ee5t(n)=(2^n-1)*c > big O(2^n)<\/p>\n\n\n\n

int fibonacci(int n){\n\u3000if(n=0)return (0);\n\u3000else if(n=1)return (1);\n\u3000else return(fibonacci(n-1)+fibonacci(n-2));\n}\nint fibonacci(int n){\n\u3000int fib_n,fib_n_1,fib_n_2;\n\u3000if(n==0)return(0);\n\u3000else if(n==1)return(1);\n\u3000else{\n\u3000\u3000fib_n_2=0;fib_n_1=1;\n\u3000\u3000for(i=2;i<=n;i++){\n\u3000\u3000\u3000fib_n=fib_n_1+fib_n_2; fib_n_1=fib_n_2; fib_n_2=fib_n;\n\u3000\u3000}\n\u3000return(fib_n);\n\u3000}\n}<\/code><\/pre>\n\n\n\n
hanoi(\u6cb3\u5167\u5854\u554f\u984c)<\/strong> O(2^n)
\u905e\u8ff4\u95dc\u4fc2\u5f0f:T(n){
2T(n-1)+c ,n>=2 where c\u5c6c\u65bcconstant(\u905e\u8ff4\u95dc\u4fc2)
c ,n=1 where c\u5c6c\u65bcconstant(\u7d42\u6b62\u689d\u4ef6)
\u63a8\u5c0e…
ps:\u642c\u52d5n\u500b\u5957\u74b0\u97002^n-1\u6b21<\/p>\n\n\n\n
bin_search(\u4e8c\u5143\u641c\u5c0b)<\/strong>,O(2\u5e95log n)
\u905e\u8ff4\u95dc\u4fc2\u5f0f:T(n)={
T(n\/2)+c ,n>=2 where c\u5c6c\u65bcconstant(\u905e\u8ff4\u95dc\u4fc2)
c , n=1 where c\u5c6c\u65bcconstant(\u7d42\u6b62\u689d\u4ef6)<\/p>\n\n\n\n
\u6700\u5927\/\u6700\u5c0f\u554f\u984c<\/strong>,O(n)
\u905e\u8ff4\u95dc\u4fc2\u5f0f:T(n)={
2T(n\/2)+c ,n>=2 where c\u5c6c\u65bcconstant(\u905e\u8ff4\u95dc\u4fc2)
c , n=1 where c\u5c6c\u65bcconstant(\u7d42\u6b62\u689d\u4ef6)<\/p>\n\n\n\n
\u9078\u64c7\u554f\u984c<\/strong> O(n^2)<\/p>\n\n\n\n
\u77e9\u9663\u4e58\u6cd5\u554f\u984c<\/strong> O(n^3)
\u905e\u8ff4\u95dc\u4fc2\u5f0f,\u63a8\u5c0e…<\/p>\n\n\n\n
volker strassen<\/strong> O(n^2.81)
\u905e\u8ff4\u95dc\u4fc2\u5f0f,\u63a8\u5c0e…<\/p>\n\n\n\n
…<\/p>\n\n\n\n
\/\/\u627e\u7e3d\u6578<\/strong>
int findsum(int n){ \/\/1+2+…n
\u3000if(n==1)return(1); \/\/\u7d42\u6b62\u689d\u4ef6
\u3000else return(findsum(n-1)+n); \/\/\u905e\u8ff4\u689d\u4ef6
}
int findsum(int n){
\u3000int result,i;
\u3000for(i=n;i>1;i++){result+=i;}
\u3000return result;
}<\/p>\n\n\n\n
\/\/\u627e\u6700\u5927<\/strong>,\u5c1a\u672a\u6e2c\u8a66
int findmax(int a[],int max,int i){ \/\/find(a,1,\u9663\u5217\u5143\u7d20);
\u3000if(i==0){return max}
\u3000else{
\u3000\u3000if(max < a[i] )max=a[i];
\u3000\u3000findmax(a,max,i-1);
\u3000}
}<\/p>\n\n\n\n
\/\/\u627e\u6700\u5927\u516c\u56e0\u6578<\/strong><\/p>\n\n\n\n
int findgcd(int x,int y){\n\u3000return((y==0)?x:findgcd(y,x%y))\n}\nint findgcd(int x,y){\n\u3000if(y==0)return(x);\n\u3000else return(findgcd(y,x%y));\n}\nint findgcd(int x,y){\nint remainder=x%y;\n\u3000while(remainder!=0){\n\u3000\u3000x=y;y=remainder;\n\u3000\u3000remainder=x%y;\n\u3000}\n\u3000return(y);\n}<\/code><\/pre>\n\n\n\n
\u627e\u4e00\u5b57\u4e32\u7684\u6240\u6709\u6392\u5217<\/strong><\/p>\n\n\n\n
void permutation(char list[],int i,int n){\n\u3000int j,temp;\n\u3000if(i==n){ printf(\"%s\",list);}\n\u3000else{\n\u3000\u3000for(j=i;j<=n;j++){\n\u3000\u3000\u3000swap(list[i],list[j],temp);\n\u3000\u3000\u3000permutation(list,i+1,n);\n\u3000\u3000\u3000swap(list[i],list[j],temp);\n\u3000\u3000}\n\u3000}\n}\nt(n)={c ,if n=1; n*t(n-1)+c*n ,if n>=2;\nt(n)=n*t(n-1)+c*n=n*t((n-1)*t((n-1)-1)+c*(n-1)<\/strong>)+c*n=(n*(n-1))*t(n-2)+c*(n+(n-1))=.....=O(n!)<\/code><\/pre>\n\n\n\n
ackermann<\/strong>
……<\/p>\n","protected":false},"excerpt":{"rendered":"
recursive(\u905e\u8ff4)\u7c21\u6f54\u6613\u61c2,\u4f46\u6548\u7387\u5dee,\u9069\u5408\u63cf\u8ff0\u6f14\u7b97\u6cd5 …<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"fifu_image_url":"","fifu_image_alt":"","_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[15],"tags":[],"class_list":["post-556","post","type-post","status-publish","format-standard","hentry","category-algorithm"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/556","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/comments?post=556"}],"version-history":[{"count":0,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/posts\/556\/revisions"}],"wp:attachment":[{"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/media?parent=556"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/categories?post=556"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/systw.net\/note\/wp-json\/wp\/v2\/tags?post=556"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}