C語(yǔ)言函數(shù)數(shù)的遞歸調(diào)用
2022-04-25 23:00:47

@TOC

一、什么是遞歸

程序調(diào)用自身的編程技巧稱(chēng)為遞歸( recursion) 。遞歸做為一種算法在程序設(shè)計(jì)語(yǔ)言中廣泛應(yīng)用。一個(gè)過(guò)程或函數(shù)在其定義或說(shuō)明中有直接或間接調(diào)用自身的一種方法,它通常把一個(gè)大型復(fù)雜的問(wèn)題層層轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的規(guī)模較小的問(wèn)題來(lái)求解,遞歸策略只需少量的程序就可描述出解題過(guò)程所需要的多次重復(fù)計(jì)算,大大地減少了程序的代碼量。遞歸的主要思考方式在于:把大事化小

遞歸的兩個(gè)必要條件：

1. 存在限制條件,當(dāng)滿足這個(gè)限制條件的時(shí)候,遞歸便不再繼續(xù)。
2. 每次遞歸調(diào)用之后越來(lái)越接近這個(gè)限制條件。

   int main()
   {
   printf("hehe
   ");
   main();
   return 0;
   }

   函數(shù)自己調(diào)用自己，一直打印 “hehe” 但是一會(huì)程序自己會(huì)停下來(lái)。這不是真正的遞歸，是一個(gè)死循環(huán)（不滿住遞歸的兩個(gè)條件）
   ?
   遞歸實(shí)現(xiàn)：接收一個(gè)整型值（無(wú)符號(hào)），按照順序打印它的每一位。例如：輸入：1234，輸出：4321
   
   

   
   void print(unsigned int n)
   {
   if (n > 9)
   {
       print(n / 10);
   }
   printf("%d", n % 10);
   }
   int main()
   {
   unsigned int num = 0;
   scanf("%u", &num);
   //遞歸-函數(shù)自己調(diào)用自己
   print(num);
   return 0;
   }

基本的實(shí)現(xiàn)邏輯如圖：
![image.png](https://s2.51cto.com/images/20220425/1650890354614516.png)
 
寫(xiě)遞歸代碼的時(shí)候注意：
1. 不能死遞歸，都有跳出條件，每次遞歸逼近跳出條件
2. 遞歸層次不能太深（可能會(huì)棧溢出）

## 二、遞歸與迭代
求第n個(gè)斐波那契數(shù)，（可以遞歸實(shí)現(xiàn)也可以迭代實(shí)現(xiàn)）(不考慮溢出)
我們知道像：1，1，2，3，5，8，13，21，34…… 這樣第n個(gè)數(shù)等于第n-1個(gè)數(shù)加上n-2個(gè)數(shù)的和的一個(gè)數(shù)列就是**斐波那契數(shù)列**

- 遞歸實(shí)現(xiàn)求斐波那契數(shù)，直接看代碼：
```c
int Fib(int n)
{
    if (n <= 2)
        return 1;
    else
        return Fib(n - 1) + Fib(n - 2);
}
int main()
{
    int n = 0;
    scanf("%d",&n);
    int ret = Fib(n);
    printf("%d
", ret);
    return 0;
}

當(dāng)我們求很小的斐波那契數(shù)時(shí)，計(jì)算機(jī)計(jì)算很快。但是當(dāng)我們要求的一個(gè)很大的，比如第50個(gè)斐波那契數(shù)，計(jì)算機(jī)就會(huì)算很久（大概要五分鐘）。大家可以試一試。

為什么會(huì)這么慢呢。因?yàn)檫f歸實(shí)現(xiàn)效率太低，要重復(fù)大量的計(jì)算（計(jì)算層次太多）。
代碼實(shí)現(xiàn)的基本邏輯如圖：

我們可以看一下代碼在計(jì)算過(guò)程中 n=3（計(jì)算第三個(gè)斐波那契數(shù)） 這一步要執(zhí)行的次數(shù)：
在計(jì)算第40個(gè)斐波那契數(shù)時(shí)，要計(jì)算三千多萬(wàn)次第三個(gè)斐波那契數(shù)。可想而知遞歸實(shí)現(xiàn)的效率有多低。而且計(jì)算太大還會(huì)造成程序崩潰。
?

• 循環(huán)迭代實(shí)現(xiàn)求斐波那契數(shù)，直接看代碼：

  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
  ", ret);
  return 0;
  }

  循環(huán)迭代的方式計(jì)算很快
  ?
  提示：

  1. 很多問(wèn)題是以迭代的形式進(jìn)行解釋的，這只是因?yàn)樗确沁f歸的形式更為清晰。
  2. 但是很多問(wèn)題的迭代實(shí)現(xiàn)往往比遞歸實(shí)現(xiàn)的效率更低。雖然代碼的可讀性稍微差些。
  3. 當(dāng)一個(gè)問(wèn)題相當(dāng)復(fù)雜時(shí)，難以用迭代實(shí)現(xiàn)時(shí)，此時(shí)遞歸實(shí)現(xiàn)的簡(jiǎn)潔性便可以補(bǔ)償它所帶來(lái)的運(yùn)行開(kāi)銷(xiāo)。

三、典型的遞歸問(wèn)題

有興趣的可以了解一下：
漢諾塔問(wèn)題，青蛙跳臺(tái)階問(wèn)題
這都是典型的遞歸問(wèn)題。