學點C語言(35):函數 - 遞歸

1. 遞歸就是: 函數自己調用自己

這是一個最簡單的遞歸, 不過它會一直執行, 可用Ctrl+C 終止.

#include　<stdio.h>

void　prn(void)　{
　　printf("C++Builder　2009\n");
　　prn();　/*　自調用;注意它會一直執行,可用Ctrl+C終止執行　*/
}

int　main(void)
{
　　prn();
　　getchar();
　　return　0;
}

2. 使用遞歸一定要有跳出的條件:

#include　<stdio.h>

void　prn(int　num)　{
　　printf("%d\n",　num);
　　if　(num　>　0)　prn(--num);
}

int　main(void)
{
　　prn(9);
　　getchar();
　　return　0;
}

3. 實例: 翻轉字符串

#include　<stdio.h>

void　revers(char　*cs);

int　main(void)
{
　　revers("123456789");

　　getchar();
　　return　0;
}

void　revers(char　*cs)
{
　　if　(*cs)
　　{
　　　　revers(cs　+　1);
　　　　putchar(*cs);
　　}
}

4. 實例: 階乘

#include　<stdio.h>

int　factorial(int　num);

int　main(void)
{
　　int　i;
　　for　(i　=　1;　i　<=　9;　i++)
　　printf("%d:　%d\n",　i,　factorial(i));

　　getchar();
　　return　0;
}

int　factorial(int　num)
{
　　if　(num　==　1)
　　　　return(1);
　　else
　　　　return(num　*　factorial(num-1));
}

5. 實例: 整數到二進制

#include　<stdio.h>

void　IntToBinary(unsigned　num);

int　main(void)
{
　　IntToBinary(255);　/*　11111111　*/
　　getchar();
　　return　0;
}

void　IntToBinary(unsigned　num)　{
　　int　i　=　num　%　2;
　　if　(num　>　1)　IntToBinary(num　/　2);
　　putchar(i　?　'1'　:　'0');
//　　putchar('0'　+　i);　/*　可代替上面一句　*/
}

6. 剖析遞歸:

#include　<stdio.h>

void　prn(unsigned　n);

int　main(void)
{
　　prn(1);
　　getchar();
　　return　0;
}

void　prn(unsigned　n)　{
　　printf("%d:　%p\n",　n,　&n);　/*　A　*/
　　if　(n　<　4)
　　　　prn(n+1);　　　　　　　　/*　B　*/
　　printf("%d:　%p\n",　n,　&n);　/*　C　*/
}

本例輸出效果圖:

分析:

程序運行到 A, 輸出了第一行.

此時 n=1, 滿足 < 4 的條件, 繼續執行 B 開始了自調用(接著會輸出第二行); 注意 n=1 時語句 C 還有待執行.

...如此循環, 一直到 n=4, A 可以執行, 但因不滿足條件 B 執行不了了; 終於在 n=4 時得以執行 C.

但此時內存中有四個函數都等待返回(分別是 n=1、2、3、4 時), 咱們分別叫它 f1、f2、f3、f4.

f4 執行 C 輸出了第五行, 函數返回, 返回給 f3(此時 n=3), f3 得以繼續執行 C, 輸出了第六行.

f3 -> f2 -> 繼續 C, 輸出了第七行.

f2 -> f1 -> 繼續 C, 輸出了第八行, 執行完畢!

如此看來, 遞歸函數還是很費內存的(有時不如直接使用循環), 但的確很巧妙.

返回“學點C語言 - 目錄”