C語言 function recursion函數(shù)遞歸詳解
function recursion(函數(shù)遞歸)
函數(shù)遞歸: 是在 一個 過程 或 函數(shù) 在其定義或說明中有 直接 或 間接 調用自身 的一種方法
通常把一個 大型復雜的問題 層層 傳化 為一個與 原理相似的 ,規(guī)模較小 的問題
遞歸策略 只需 少量的程序 就可以描述出 解題過程 所需的 多次 重復 計算,大大減少了程序的代碼量
遞歸的中心思想為:
大事化小。
程序一
#include<stdio.h> int main() { printf("hehe"); main();//陷入死循環(huán),但因為棧溢出,最后會停下來 == stack overflow - 棧溢出 任何一次函數(shù)調用,它都會向內(nèi)存申請空間,分為三部分 棧區(qū),堆區(qū),靜態(tài)區(qū) 棧區(qū) :局部變量,函數(shù)的形參 堆區(qū): 動態(tài)開辟的內(nèi)存 - malloc(分配內(nèi)存) and calloc(動態(tài)內(nèi)存分配并初始化零) 靜態(tài)區(qū): 全局變量,static修飾的變量 return 0; }
遞歸的兩個必要條件
1,存在限制條件,當滿足這個限制條件的時候,遞歸將不再繼續(xù)
2.每次遞歸調用之后越來越接近這個條件
程序一:
#include<stdio.h> 一共調用三次 1 2 3 void print(int n)// n == 123 void print(int n)n == 12 void print(int n) m == 1 { // { { if (n > 9) // if (n > 9) if (n > 9) { // { { print(n / 10);// 這里再調用 print 函數(shù) print(n / 10); print(n / 10); } // } } printf("%d ",n%10); // 最后打印3 // printf("%d ",n%10); 再打印個2 printf("%d ",n%10); 首先打印 1 } // } } int main() { unsigned int num = 0; scanf("%d",&num);//123 //遞歸 print(num);//1 2 3 return 0; }
程序二:
#include<stdio.h> #include<string.h> 寫法1(計數(shù)器) int my_strlen(char* str)//str指針變量,需要返回整形 { int count = 0; while (*str != '\0') { count++; str ++; } return count; } 寫法2(遞歸) int my_strlen(char* str)//str指針變量,需要返回整形 { if (*str != '\0') { return 1 + my_strlen(str + 1); } else return 0; } int main() { char arr[] = "bit"; //int len = strlen(arr); //printf("%d\n", len); //模擬實現(xiàn)一個strlen函數(shù) int len = my_strlen(arr); printf("len = %d\n",len); return 0; }
練習
求n的階乘
迭代與遞歸
#include<stdio.h> 1 迭代方式 int facl(int n) { int i = 0; int ret = 1; for (i = 1; i <= n; i++) { ret = ret*i; } return ret; } 遞歸方式 int facl(int n) { if (n <= 1) { return 1; } else return n*facl(n - 1); 這里說明一下思維 假設 我們 要求 10 的階乘 1x1x2x3x4x5x6x7x8x9x10 我們的 n 一開始是 10, 10*facl(n-1) ,其實 facl 函數(shù) 就是 把 10 減一,遞歸就好像是循環(huán),循環(huán)的目的,就是 得到 10每次減一的結果,直到它等于1,再讓其鏈接起來, 你可以這么看 10 *(9 * (8 * (7 * ((6 * (5 * (4 *(3 * (2 * (1 * (1)))))))))) 等價于 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * 1 } int main() { int n = 0; scanf("%d",&n); int ret = facl(n);//循環(huán)方式 printf("%d\n",ret); return 0; }
再來道例題
斐波那契函數(shù) 1 1 2 3 5 8 13 21
從 第三個數(shù) 開始,該數(shù)等前面兩個數(shù)的和。
求第第n個斐波那契函數(shù)
#include<stdio.h> 這題用遞歸效率很低,很多數(shù)會重復計算 int fib(int n) { if (n <= 2) return 1; else return fib(n - 1)+fib(n - 2);// 因為 函數(shù) 每得到一個數(shù),就需要將得到的數(shù)進行分解成 2個 部分 } 2迭代(循環(huán))方式(簡單加法) 效率更高 int fib(int n) { int a = 1; int b = 1; int c = 1; while (n>2)// { c = a + b; a = b; b = c; n--; } return c; } int main() { int n = 0; scanf("%d",&n); int ret = fib(n); printf("%d\n",ret); return 0; }
到此這篇關于C語言 function recursion函數(shù)遞歸詳解的文章就介紹到這了,更多相關C語言 函數(shù)遞歸內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!