# 재귀(Recursion)

* 자기 자신을 호출하는 과정/함수(A process/function that calls itself)
* 입력값이 다른 동일한 함수를 `base case`에 도달하기 전까지 호출 (Invoke the same function with a different input until you reach your base case)
  * `Base Case`: 재귀가 멈추는 조건 (Condition that recursion ends)
  * `Recursive Case`: 재귀가 시작하는 조건(Condition that resumes recursion)

    ```javascript
    function countDown(num) {
      if (num <= 0) {
        console.error("Finish!");
        return; // Base Case
      }
      console.log(num);
      num--;
      countDown(num);
    }
    countDown(10);
    ```

## 재귀함수와 콜스택(Recursive functions and CallStack)

* 재귀함수는 반복해서 함수를 콜스택에 추가

  ```javascript
  function recursive(x) {
    if (x > 0) {
      console.log(x);
      recursive(x - 1);
    }
  }
  ```

  ![Recursion\_CallStack](/files/-MaQx8QDOlqjgcVE6HRU)

  > ## 💡재귀 호출의 콜스택으로 인한 추가적인 메모리 필요
  >
  > * 재귀 호출 운영체제의 메모리 스택에 저장되어야 하기 때문에 재귀 알고리즘은 추가적인 공간 복잡도 비용이 필요합니다.
  > * 콜스택이 n만큼 호출된 경우 공간복잡도는 O(n)입니다.
  > * 때에 따라서 재귀 보다 반복 루프를 활용한 해결책도 고려해야 합니다.
  > * 잘못 구현된 재귀함수는 스택 오버플로우(stack overflow) 오류를 일으켜 프로그램을 중단시킬 수 있습니다.

## ※ 재귀함수 필수 요소

1. **`Base Case`**

   ```javascript
   function factorial(num) {
     // if(num === 1) return 1;  // 👿No base case
     return num * factorial(num - 1);
   }
   // Maximun call stack size exceeded(Stack overflow)
   ```
2. **`Return`**

   ```javascript
   function factorial(num) {
     if (num === 1) console.log(1); // 👿No return
     return num * factorial(num - 1);
   }

   function factorial(num) {
     if (num === 1) return 1;
     return num * factorial(num); // 👿Wrong return!
   }
   // Maximun call stack size exceeded(Stack overflow)
   ```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://yong2401.gitbook.io/til-by-ellie/algorithm-1/recursion.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.