Java 中的 DSA - 遞迴

概述

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

特點

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

• 基本情況

• 一系列規則，透過減少情況最終導致基本情況。

遞迴階乘

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

1. 0! = 1

2. 1! = 1

3. n! = n * n-1!

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

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

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

遞迴斐波那契數列

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

1. F₀ = 0

2. F₁ = 1

3. F_n = F_n-1 + F_n-2

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

例如，F₅ = 0 1 1 2 3

演示程式

RecursionDemo.java

package com.tutorialspoint.algorithm;

public class RecursionDemo {
   public static void main(String[] args){
      RecursionDemo recursionDemo = new RecursionDemo();
      int n = 5;
      System.out.println("Factorial of " + n + ": "
         + recursionDemo.factorial(n));
      System.out.print("Fibbonacci of " + n + ": ");
      for(int i=0;i<n;i++){
         System.out.print(recursionDemo.fibbonacci(i) +" ");            
      }
   }

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

   private int fibbonacci(int n){
      if(n ==0){
         return 0;
      }
      else if(n==1){
         return 1;
      }
      else {
         return (fibbonacci(n-1) + fibbonacci(n-2));
      }
   }
}

如果我們編譯並執行上述程式，則它將產生以下結果：

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