C語言 function recursion函數(shù)遞歸詳解

更新時間：2021年10月22日 10:18:01 作者：Dark And Grey

遞歸指的是在函數(shù)的定義中使用函數(shù)自身的方法，舉個例子：從前有座山，山里有座廟，廟里有個老和尚，正在給小和尚講故事呢！故事是什么呢？"從前有座山，山里有座廟，廟里有個老和尚，正在給小和尚講故事呢！故事是什么呢？"從前有座山，山里有座廟，循環(huán)下去

function recursion（函數(shù)遞歸）

函數(shù)遞歸：是在一個過程或函數(shù) 在其定義或說明中有直接或間接調(diào)用自身的一種方法

通常把一個大型復雜的問題層層傳化為一個與原理相似的，規(guī)模較小的問題

遞歸策略只需少量的程序就可以描述出解題過程所需的多次重復計算，大大減少了程序的代碼量

遞歸的中心思想為：

大事化小。

程序一

#include<stdio.h>
int main()
{
    printf("hehe");
    main();//陷入死循環(huán)，但因為棧溢出，最后會停下來 == stack overflow - 棧溢出

 任何一次函數(shù)調(diào)用，它都會向內(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.每次遞歸調(diào)用之后越來越接近這個條件

程序一：

#include<stdio.h>
一共調(diào)用三次 
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);// 這里再調(diào)用 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每次減一的結(jié)果，直到它等于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;
}

在這里插入圖片描述