遞迴是什麼？遞迴是什麼？遞迴是什麼？（真的要無限嗎OAO?）

鏡子! 就像無數遞迴一樣

你照鏡子時會看到自己，對吧？（廢話　
如果你站在鏡子前，背後又同時有鏡子呢？
畫面就會不斷反射，形成無限循環！
這個概念，正是遞迴的核心思想。

基本概念

當一個函數在執行時呼叫自己，就是遞迴。
以下為以C++作為示範。

void recursion(int& n){
  if(n == 0) return;      
  // ↑ Base Case: 若n==0，終止遞迴

  // ↓ Recursive Case：遞迴要執行的邏輯
  // 這裡可以是一些操作或計算
  
  recursion(n - 1);       
  // ↑ 在函式裡呼叫自己，n-1 為減少需處理的n
}

核心概念：

1. Base Case (基底條件)：當滿足某個條件時，就停止呼叫自己，避免無限迴圈。
2. Recursive Case (遞迴邏輯)：在每一次呼叫中，將規模縮小或轉換，並再次呼叫同一個函式。

實際應用：計算階乘

還記得這個公式嗎？

\[ \begin{aligned} 5! &= 5 \times 4 \times 3 \times 2 \times 1 \end{aligned} \]　

這在中學的時候學的階乘！讓我們在C++實現。

int factorial(int n) {
    if (n <= 1) {
        return 1; // Base Case：1! 或 0! 都視為 1
    }
    return n * factorial(n - 1); // Recursive Case：n * (n-1)!
}

為何 \(N\le1\)就要返回\(1\)？

首先，這是Base Case，這樣可以確保抵達某個數值時結束運算並返回結果。

其次就是在階乘裡\(0!\ = 1\div1\)

階乘的公式為 \( (n-1)! = \frac{n!}{n} \) 或 \( n! = \frac{(n+1)!}{n+1} \)

\[ \begin{aligned} n! &= 1 \\ (1-1)! &= \frac{1!}{1} \\ 0! &= \frac{1}{1} \end{aligned} \]

由此得出\(n\le1\)是需要返回\(0\)。

為什麼用遞迴？

1. 程式碼簡潔：幾行程式就能重複執行同一段邏輯。
2. 思維符合數學定義：許多數學公式本身就是遞迴（或歸納法）。
3. 容易理解問題拆解：遞迴能將大問題不斷拆成小問題。

遞迴vs.迴圈

總結

在這篇文章，以C++說明了遞迴的基礎知識。若你對編程知識有興趣，不坊定期回來查看我的新文章。你亦可以在右上角註冊會員以接收訂閱的。

What is Recursion? What is Recursion? (Do we really need infinity? OAO)

Mirror! Just like infinite recursion!

When you look at yourself in a mirror, you can see yourself, right?
But what if you stand in front of a mirror, and there's another mirror behind you?
The mirrors will keep reflecting, creating an infinite loop of images!
This concept is a core idea of recursion.

Basic Concept

When a function calls itself during execution, it is called recursion.
Below is an example written in C++:

void recursion(int& n){
  if(n == 0) return;      
  // ↑ Base Case: When n == 0, the recursion stops.

  // ↓ Recursive Case：The logic that needs to be executed in recursion.
  // This can include some operations or calculations.
  
  recursion(n - 1);       
  // ↑ Calls itself inside the function, reducing n by 1.
}

Core Concepts:

1. Base Case: When a certain condition is met, the function stops calling itself to avoid an infinite loop.
2. Recursive Case: In each function call, the scale is reduced or transformed, and the same function is called again.

Practical Application: Calculating Factorial

Do you remember this formula?

\[ \begin{aligned} 5! &= 5 \times 4 \times 3 \times 2 \times 1 \end{aligned} \]　

This is the factorial you learned in middle school! Let's implement it in C++.

int factorial(int n) {
    if (n <= 1) {
        return 1; // Base Case: 1! and 0! are both defined as 1  
    }
    return n * factorial(n - 1); // Recursive Case：n * (n-1)!
}

Why return \(1\) when \(N\le1\)？

First, this is the Base Case, which ensures that the recursion stops when a certain value is reached and returns the result.

Next, this is based on the definition of factorial: \(0!\ = 1\div1\)

The factorial formula is: \( (n-1)! = \frac{n!}{n} \) or \( n! = \frac{(n+1)!}{n+1} \)

\[ \begin{aligned} n! &= 1 \\ (1-1)! &= \frac{1!}{1} \\ 0! &= \frac{1}{1} \end{aligned} \]

Thus, we conclude that when\(n\le1\), we must return\(0\)。

Why Use Recursion?

1. Simplifies Code: A few lines of code can repeatedly execute the same logic.
2. Matches Mathematical Definitions: Many mathematical formulas are naturally recursive (or defined by recurrence relations).
3. Helps with Problem Decomposition: Recursion can break down large problems into smaller subproblems.

Recursion versus Loop

Summary

In this article, I explained the basics of recursion using C++. If you're interested in programming concepts, feel free to check back for new posts! You can also subscribe in the top-right corner to receive updates.