C語言資料結構 - 遞迴

概述

遞迴指的是程式語言中一種函式呼叫自身的技術。呼叫自身的函式稱為遞迴方法。

特點

一個遞迴函式必須具備以下兩個特點。

• 基本情況(Base Case)

• 一組規則，透過減少情況來導致基本情況。

遞迴階乘

階乘是遞迴的經典示例之一。階乘是一個非負數，滿足以下條件。

• 0! = 1

• 1! = 1

• n! = n * n-1!

階乘用“!”表示。規則1和規則2是基本情況，規則3是階乘規則。

例如，3! = 3 x 2 x 1 = 6

int factorial(int n){
   //base case
   if(n == 0){
      return 1;
   } else {
      return n * factorial(n-1);
   }
}

遞迴斐波那契數列

斐波那契數列是遞迴的另一個經典示例。斐波那契數列是一系列整數，滿足以下條件。

• F₀ = 0

• F₁ = 1

• F_n = F_n-1 + F_n-2

斐波那契用“F”表示。規則1和規則2是基本情況，規則3是斐波那契規則。

例如，F₅ = 0 1 1 2 3

示例

#include <stdio.h>

int factorial(int n){
   //base case
   if(n == 0){
      return 1;
   } else {
      return n * factorial(n-1);
   }
}
int fibbonacci(int n){
   if(n ==0){
      return 0;
   }
   else if(n==1){
      return 1;
   } else {
      return (fibbonacci(n-1) + fibbonacci(n-2));
   }
}
main(){
   int n = 5;
   int i;
   printf("Factorial of %d: %d\n" , n , factorial(n));
   printf("Fibbonacci of %d: " , n);
   for(i=0;i<n;i++){
      printf("%d ",fibbonacci(i));            
   }
}

輸出

如果我們編譯並執行上述程式，則會產生以下輸出：

Factorial of 5: 120
Fibbonacci of 5: 0 1 1 2 3