使用 Laravel 以遞迴方式實現費波那契 (Fibonacci) 數列

1. 創建一個 Laravel 控制器 (Controller)

首先，讓我們創建一個控制器來處理費波那契邏輯。您可以使用 Artisan 命令來完成：

Bash

php artisan make:controller FibonacciController

2. 在控制器中實現遞迴費波那契邏輯

現在，打開 app/Http/Controllers/FibonacciController.php 並添加以下程式碼：

PHP

<?php

namespace App\Http\Controllers;

use Illuminate\Http\Request;

class FibonacciController extends Controller
{
    /**
     * 使用遞迴方式計算第 n 個費波那契數。
     *
     * @param int $n 費波那契數列中的位置。
     * @return int 費波那契數。
     */
    public function calculate($n)
    {
        if ($n <= 0) {
            return 0;
        } elseif ($n == 1) {
            return 1;
        } else {
            // 遞迴調用：F(n) = F(n-1) + F(n-2)
            return $this->calculate($n - 1) + $this->calculate($n - 2);
        }
    }

    /**
     * 顯示特定的費波那契數。
     *
     * @param int $n 要顯示的費波那契數列中的位置。
     * @return \Illuminate\Http\Response
     */
    public function show($n)
    {
        $fibonacciNumber = $this->calculate($n);
        return response()->json([
            'n' => $n,
            'fibonacci_number' => $fibonacciNumber
        ]);
    }

    /**
     * 顯示直到給定限制的費波那契數列。
     *
     * @param int $limit 數列的上限。
     * @return \Illuminate\Http\Response
     */
    public function sequence($limit)
    {
        $sequence = [];
        for ($i = 0; $i <= $limit; $i++) {
            $sequence[] = $this->calculate($i);
        }
        return response()->json([
            'limit' => $limit,
            'fibonacci_sequence' => $sequence
        ]);
    }
}

解釋：

• calculate($n) 方法：

  • 這是核心的遞迴函數。
  • 基本情況 (Base Cases)：
    • 如果 $n 小於或等於 0，它返回 0（第一個費波那契數）。
    • 如果 $n 等於 1，它返回 1（第二個費波那契數）。
  • 遞迴步驟 (Recursive Step)： 對於任何其他 $n，它遞迴地調用自身，傳入 $n-1 和 $n-2，並返回它們的和。這直接實現了費波那契的定義：$F(n)=F(n-1)+F(n-2)$。

• show($n) 方法：

  • 此方法接受一個整數 $n 作為輸入，使用 calculate($n) 計算第 n 個費波那契數，並以 JSON 響應的形式返回。

• sequence($limit) 方法：

  • 此方法接受一個 $limit 作為輸入，從 0 迭代到 $limit，使用 calculate($i) 計算數列中的每個費波那契數，並以 JSON 響應的形式返回整個數列。

3. 定義路由 (Routes)

接下來，您需要在 routes/web.php (用於網頁存取) 或 routes/api.php (用於 API 存取，這種類型的服務通常更適合) 中定義路由。讓我們使用 routes/api.php 來建立一個乾淨的 API 端點：

PHP

<?php

use Illuminate\Http\Request;
use Illuminate\Support\Facades\Route;
use App\Http\Controllers\FibonacciController;

/*
|--------------------------------------------------------------------------
| API Routes
|--------------------------------------------------------------------------
|
| 此處是您可以為應用程式註冊 API 路由的地方。這些
| 路由由 RouteServiceProvider 加載，並被分配到
| "api" 中間件群組。盡情建立您的 API 吧！
|
*/

Route::get('/fibonacci/{n}', [FibonacciController::class, 'show']);
Route::get('/fibonacci-sequence/{limit}', [FibonacciController::class, 'sequence']);

4. 測試您的實現

啟動您的 Laravel 開發伺服器：

Bash

php artisan serve

現在，您可以使用網頁瀏覽器或工具（如 Postman/Insomnia）進行測試：

• 獲取第 10 個費波那契數：

  在瀏覽器中打開：http://127.0.0.1:8000/api/fibonacci/10

  您應該會看到：{"n":10,"fibonacci_number":55}

• 獲取直到第 7 個的費波那契數列：

  在瀏覽器中打開：http://127.0.0.1:8000/api/fibonacci-sequence/7

  您應該會看到：{"limit":7,"fibonacci_sequence":[0,1,1,2,3,5,8,13]}

遞迴費波那契的重要考量：

• 效能 (Performance)： 儘管概念簡單，但費波那契數列的遞迴實現對於較大的數字來說效率非常低。這是因為它們涉及冗餘計算。例如，要計算 F(5)，它會計算 F(4) 和 F(3)。要計算 F(4)，它又會再次計算 F(3) 和 F(2)，依此類推。許多值會被重複計算多次。
• 堆疊溢位 (Stack Overflow)： 對於非常大的 $n 值，您可能會遇到「堆疊溢位」錯誤，因為每個遞迴調用都會向調用堆疊中添加一個框架。
• 更好的替代方案： 對於實際應用，尤其是處理較大的費波那契數時，迭代解決方案或記憶化 (動態規劃) 的效率會顯著更高。

迭代 (更有效率) 的費波那契數列範例 (在 Laravel 中)：

如果您要為了效能而實現它，那麼迭代方法會好得多：

PHP

<?php

namespace App\Http\Controllers;

use Illuminate\Http\Request;

class FibonacciController extends Controller
{
    /**
     * 使用迭代方式計算第 n 個費波那契數。
     *
     * @param int $n 費波那契數列中的位置。
     * @return int 費波那契數。
     */
    public function calculateIterative($n)
    {
        if ($n <= 0) {
            return 0;
        } elseif ($n == 1) {
            return 1;
        }

        $a = 0; // 初始化為 F(0)
        $b = 1; // 初始化為 F(1)
        for ($i = 2; $i <= $n; $i++) {
            $next = $a + $b; // 計算下一個費波那契數
            $a = $b;         // 將目前的 F(i-1) 變成下一個的 F(i-2)
            $b = $next;      // 將目前的 F(i) 變成下一個的 F(i-1)
        }
        return $b; // 返回 F(n)
    }

    // 您可以在您的 show 和 sequence 方法中使用這個迭代方法
    public function showIterative($n)
    {
        $fibonacciNumber = $this->calculateIterative($n);
        return response()->json([
            'n' => $n,
            'fibonacci_number' => $fibonacciNumber
        ]);
    }
}