tft每日頭條

 > 生活

 > 在c語言中如何使用遞歸函數

在c語言中如何使用遞歸函數

生活 更新时间:2025-01-15 15:42:59
引言

前面我們講了函數的組成部分以及傳參詳解,函數指針等知識,對函數相關知道有了一定了解,已經足夠應對平時的開發和學習了。今天我們再來說說一個比較特殊的函數,就是我們的今天的主題——遞歸函數,為什麼說是特殊呢,這是因為平時我們寫的函數都是通過别人或者說是其他代碼來調用的,而遞歸函數是自己來調用自己, 是不是覺得很特别呢?遞歸函數也是常常在筆試題中出現的哦~

計算階乘

遞歸函數本質也是函數,隻是函數的特殊性,應用在某些特殊的場景,以下我們介紹幾種遞歸函數的應用場景,來感受下其美麗吧。以下是計算數字5階乘,具體代碼如下所示:

#include <stdio.h> int cal_factorial(int n) { //1.參數判斷 if(n < 1) { printf("n必須大于等于1.\n"); return -1; } //2.退出遞歸條件判斷 if(n == 1) { //2.1不滿足遞歸條件,則退出 return 1; } else { //2.2滿足遞歸條件,繼續遞歸 return (n*cal_factorial(n-1)); } } int main(void) { int res = cal_factorial(5); printf("5! = %d.\n", res); return 0; }

分析:

1.首先我們定義了一個遞歸函數int cal_factorial(int n),傳入參數n是指要計算階乘的數,返回值為最終計算階乘的結果。

2.在cal_factorial函數内部,首先判斷傳入的參數sizh是否符合規範,比如要計算的階乘,那麼必須是一個大于等于1的正整數。

3. 重點:接着if(n == 1)作為遞歸退出條件,因為我們知道當計算到乘以1時,說明已經完成了階乘的計算(所謂的階乘是指一個數n,一直乘以不斷減1的數,直到乘以1為止:n*(n-1)*(n-2)....*1),而這裡的return 1,是返回1本身,并與之前遞歸的結果(result=n*(n-1)*(n-2)....*2) 相乘(*1),得到完成的計算階乘的式子。否則(else),返回 (n*cal_factorial(n-1)); 這裡就用到遞歸, 這裡我們以計算5階乘為例子,那麼第一調用該遞歸函數時,就會進到else語句部分中,即執行 5*cal_factorial(5-1),而這裡的cal_factorial(5-1), 還是會進到else部分中,即變成了 5 * 4 * cal_factorial(4-1), 同理再次進入else部分,變成5*4*3*cal_factorial(3-1),接着還是同理變成5*4*3*2*cal_factorial(2-1),到了這裡cal_factorial中傳入參數等于1,再次調用遞歸函數時,就會進入if(n==1)語句部分,直接返回1,退出遞歸,此時結果就成了5*4*3*2*1。

4. 然後我們在主函數中定義一個int變量res來接收遞歸函數cal_factorial返回值,并通過printf打印

編譯運行結果:

在c語言中如何使用遞歸函數(C語言學習篇27)1

使用遞歸函數的條件

首先要說明的是并不是所有的問題都能用遞歸解決,要使用遞歸函數的就必須具備以下2個條件:

  • 要有遞歸的方式

遞歸的思想是指: 為了解決當前問題 F(n),就需要解決問題 F(n–1),而 F(n–1) 的解決依賴于 F(n–2) 的解決……就這樣逐層分解,分解成很多相似的小事件,當最小的事件解決完之後,就能解決高層次的事件。這種“逐層分解,逐層合并”的方式就構成了遞歸的思想。

  • 要有終止條件

每當進行一次遞歸,我們都需要判斷條件是否滿足,繼續遞歸還是退出。如果沒有遞歸終止條件或者這個條件不能被滿足,則這個遞歸就沒有收斂性,而沒有收斂性是一個非常可怕的事情,因為函數遞歸占用的是棧内存,每次遞歸調用都會消耗一些棧内存,因此必須在棧内存耗盡之前就要完成遞歸收斂,否則就會出現棧溢出,嚴重時就會宕機。

#include <stdio.h> void digui(int n) { int a[1000]; if(n > 1) { digui(n); } } int main(void) { digui(3); return 0; }

在上面我們定義了遞歸函數digui,并且沒有做遞歸退出處理(digui(n)),導緻一直遞歸下去,同時我們每次遞歸都定義1000個大小int類型的數組,用來撐爆棧内存。我們看看編譯運行的結果:

在c語言中如何使用遞歸函數(C語言學習篇27)2

遞歸函數的執行順序

遞歸函數的執行和返回就類似剝洋蔥一般,首先一層一層的往裡剝,剝到最深處後,再一層一層往外褪去,我們可以通過以下例子來感受下:

#include <stdio.h> void digui(int n) { printf("遞歸前: n = %d.\n", n); if(n > 1) { digui(n - 1); } else { printf("結束遞歸. n = %d.\n", n ); } printf("遞歸後:n = %d.\n", n); } int main(void) { digui(3); return 0; }

說明:

1.首先我們定義一個遞歸函數void digui(int n), 判斷n大于1時(if(n>1)),進入函數都打印遞歸的值

2. 當n=1時,進入else語句部分,打印結束遞歸,和n的值,這裡n的值肯定為1哦

3. 接着我們打印遞歸後的n的值

4. 在主函數中我們向遞歸函數傳入3,用來依次打印遞歸前後值的變化

我們先編譯運行,看看結果:

在c語言中如何使用遞歸函數(C語言學習篇27)3

從結果我們可以看出,一進入遞歸函數,就會打印遞歸前的值(當前n的值), 然後一直執行if(n > 1)語句中的遞歸函數,直到n=1;遞歸函數才運行到printf("結束遞歸. n = %d.\n", n );(這裡大家可以看到在此之前一直都沒有執行printf("遞歸後:n = %d.\n", n))退出了if(n > 1)重複遞歸, 然後依次打印了3此遞歸後的值, 并且可以看到值是1, 2, 3。 這是理解遞歸執行順序的重點: 首先打印的是1,而不是3, 這裡是因為在之前一直遞歸到n=1(剝洋蔥剝到最深處了),然後依次退出來, 順序就是1,2,3。大家好好感受下其中的妙處。這是真正理解遞歸函數的重點,一定要掌握!

總結

遞歸的主要目的是為了簡化程序設計,使結構簡潔清晰,可讀性強。 在數學方面應用的頗多,如典型的計算階乘,求斐波那契數列等。但是遞歸的缺點也是很明顯的,比如速度慢,運行效率低,對棧空間占用多,大量的函數調用,特别占用cpu,每次函數調用都需要保存上下文,因此大家在使用遞歸函數的時候需要慎重小心。

在c語言中如何使用遞歸函數(C語言學習篇27)4

,

更多精彩资讯请关注tft每日頭條,我们将持续为您更新最新资讯!

查看全部

相关生活资讯推荐

热门生活资讯推荐

网友关注

Copyright 2023-2025 - www.tftnews.com All Rights Reserved