萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

遞歸算法實戰:C++ 與 PHP 實作階乘、進制轉換與目錄遍歷

遞歸核心三要素

  1. 遞歸體:函數調用自身,問題規模縮小。
  2. 遞歸出口 (Base Case):終止條件,**必須存在且可達**,否則棧溢出。
  3. 狀態傳遞/返回:子問題結果向上傳遞,合成最終解。

優點:代碼極簡潔,自然表達分治/樹/圖問題。
缺點:函數調用開銷大 (棧幀)、深度受限 (PHP 默認 ~100-200k,C++ 更大)、重複計算風險 (需備忘錄/DP 優化)。

實例 1:階乘

C++

#include <iostream>
using namespace std;

long long factorial(int n) {
    if (n <= 1) return 1;          // 遞歸出口
    return n * factorial(n - 1);   // 遞歸體
}

int main() {
    int n; cout << "輸入整數: "; cin >> n;
    cout << n << "! = " << factorial(n) << endl;
    return 0;
}

PHP

<?php
function factorial(int $n): int {
    if ($n <= 1) return 1;
    return $n * factorial($n - 1);
}

echo "5! = " . factorial(5) . "\n"; // 120
// 注意:PHP int 範圍有限,大數用 GMP/bcmath
echo "20! = " . factorial(20) . "\n"; // 2432902008176640000 (64位溢出為負數!)
// 大數正確做法:
function bcfactorial(int $n): string {
    $res = '1';
    for ($i = 2; $i <= $n; $i++) $res = bcmul($res, (string)$i);
    return $res;
}
echo "20! = " . bcfactorial(20) . "\n"; // 正確
?>

實例 2:十進制轉任意進制 (2/8/16)

C++

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string toBase(int n, int base) {
    if (n == 0) return "0"; // 出口
    string digits = "0123456789ABCDEF";
    string res;
    while (n > 0) {         // 迭代寫法更高效
        res.push_back(digits[n % base]);
        n /= base;
    }
    reverse(res.begin(), res.end());
    return res;
}
// 遞歸版 (教學用)
string toBaseRec(int n, int base) {
    if (n == 0) return "";
    return toBaseRec(n / base, base) . digits[n % base];
}

int main() {
    int n, base; cin >> n >> base;
    cout << n << " 在 " << base << " 進制 = " << toBase(n, base) << endl;
    return 0;
}

PHP

<?php
function toBase(int $n, int $base): string {
    $digits = '0123456789ABCDEF';
    if ($n === 0) return '0';
    $res = '';
    while ($n > 0) { // 迭代優於遞歸
        $res = $digits[$n % $base] . $res;
        $n = (int)($n / $base);
    }
    return $res;
}

// 遞歸版 (尾遞歸優化 PHP 不支持,慎用深層)
function toBaseRec(int $n, int $base): string {
    $digits = '0123456789ABCDEF';
    if ($n === 0) return '';
    return toBaseRec((int)($n / $base), $base) . $digits[$n % $base];
}

echo "255 in hex: " . toBase(255, 16) . "\n"; // FF
echo "255 in bin: " . toBase(255, 2) . "\n";  // 11111111
?>

實例 3:目錄樹遍歷 (PHP 實戰場景)

遞歸天然適合樹形結構 (文件系統、DOM、組織架構)。

<?php
/**
 * 遞歸列出目錄樹
 * @param string $dir  起始目錄
 * @param int    $level 當前層級 (內部用)
 */
function listTree(string $dir, int $level = 0): void {
    $dh = @opendir($dir);
    if (!$dh) {
        echo str_repeat('  ', $level) . "⚠ 無法讀取: $dir\n";
        return;
    }

    // 讀取並排序 (目錄優先、按名)
    $entries = [];
    while (($entry = readdir($dh)) !== false) {
        if ($entry === '.' || $entry === '..') continue;
        $path = $dir . DIRECTORY_SEPARATOR . $entry;
        $entries[] = ['name' => $entry, 'path' => $path, 'isDir' => is_dir($path)];
    }
    closedir($dh);
    
    usort($entries, fn($a, $b) => ($a['isDir'] === $b['isDir']) 
        ? strcmp($a['name'], $b['name']) 
        : ($a['isDir'] ? -1 : 1));

    foreach ($entries as $e) {
        $prefix = str_repeat('│  ', $level) . ($e['isDir'] ? '├─📁 ' : '├─📄 ');
        echo $prefix . $e['name'] . "\n";
        if ($e['isDir']) {
            listTree($e['path'], $level + 1); // 遞歸進入子目錄
        }
    }
}

// 使用
listTree(__DIR__); // 列出當前腳本目錄樹
?>

輸出示例:

├─📁 src
│  ├─📁 Controller
│  │  ├─📄 UserController.php
│  │  └─📄 PostController.php
│  └─📁 Model
│     └─📄 User.php
├─📁 public
│  └─📄 index.php
└─📄 composer.json

PHP 遞歸優化技巧

  1. 優先用迭代:階乘、進制轉換、斐波那契 (DP/矩陣快速冪) 等線性遞歸**務必用循環**。
  2. 尾遞歸無優化:PHP 不做尾調用優化 (TCO),深度遞歸必爆棧。
  3. 備忘錄/動態規劃**:重疊子問題 (如斐波那契、編輯距離) 必須緩存中間結果。
  4. 生成器替代遞歸遍歷:大目錄樹用 `RecursiveIteratorIterator` + `RecursiveDirectoryIterator` (SPL),內存恆定、可中斷。
  5. <?php
    $iterator = new RecursiveIteratorIterator(
        new RecursiveDirectoryIterator(__DIR__, FilesystemIterator::SKIP_DOTS),
        RecursiveIteratorIterator::SELF_FIRST
    );
    foreach ($iterator as $path => $info) {
        $level = $iterator->getDepth();
        echo str_repeat('  ', $level) . ($info->isDir() ? '📁 ' : '📄 ') . $info->getFilename() . "\n";
    }
    ?>
  6. 增加深度限制**:`ini_set('xdebug.max_nesting_level', 500);` (需 Xdebug) 或自行計數器保護。

何時選擇遞歸?

  • 樹/圖遍歷 (目錄、AST、組織架構、分類樹)。
  • 分治算法 (快速排序、歸併排序、二分查找)。
  • 回溯算法 (N 皇后、全排列、迷宮求路、子集生成)。
  • 動態規劃遞歸實現 (自頂向下 + 備忘錄)。

原則:問題天然遞歸結構 + 深度可控 (通常 < 1000) + 代碼可讀性收益 > 效能損耗 → 用遞歸。否則改迭代/生成器/顯式棧。

copyright © 萬盛學電腦網 all rights reserved