캐나다 IT 코딩 Recursion

Recursion 알고리즘은 함수가 자기 자신을 호출하여 문제를 해결하는 알고리즘입니다. Base case(기본 사례)에서는 재귀 호출을 멈추는 조건을 설정하고, Recursive case(재귀 사례)에서는 문제를 더 작은 부분 문제로 나누어 자기 자신을 호출하여 해결합니다.

Recursion (재귀) 알고리즘의 정의

Recursion 알고리즘은 앞서 잠깐 언급한 것과 같이 두 가지 요소로 구성됩니다: base case(기본 사례)와 recursive case(재귀 사례).

• Base case(기본 사례): Recursion 알고리즘이 멈추는 조건을 정의합니다. Base case에서는 일반적으로 단순한 문제를 해결하거나, 재귀 호출을 멈추는 조건을 설정합니다. 이 조건이 설정되지 않으면 Infinite Loop(무한 루프)에 빠지게 됩니다.
• Recursive case(재귀 사례): Recursion 알고리즘이 자기 자신을 호출하여 문제를 해결하는 부분입니다. Recursive case에서는 문제를 더 작은 부분 문제로 나누고, 자기 자신을 호출하여 부분 문제를 해결합니다. 이렇게 작은 부분 문제들이 해결되면, 그 결과를 결합하여 원래 문제의 해답을 얻습니다.

Recursion 알고리즘은 문제를 더 작은 단위로 나누어 해결하는 효과적인 방법입니다. 그러나 올바른 base case와 recursive case를 정의하는 것이 중요하며, 재귀 호출이 무한히 반복되지 않도록 주의해야 합니다.

 

Recursion 알고리즘 코딩 예제

앞서 설명한 Recursion 알고리즘에 대한 코딩 예제를 Python으로 구성해서 보여주고 있습니다

# 팩토리얼 계산 함수
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(5))

위의 예제는 재귀 알고리즘인 팩토리얼 계산을 보여줍니다. factorial 함수는 주어진 숫자 n의 팩토리얼을 계산하는 함수입니다. n이 0인 경우에는 1을 반환하고, 그 외에는 n과 factorial(n-1)을 곱하여 재귀적으로 팩토리얼을 계산합니다. 이 예제에서는 factorial(5)를 호출하여 5의 팩토리얼인 120을 출력합니다.

 

Recursion 알고리즘 작동 기본 이미지

Recursion 알고리즘 작동 기본 원리

Recursion 알고리즘의 장, 단점

장점

• 코드의 간결성: 재귀를 사용하면 복잡한 문제를 명확하고 간결한 코드로 표현할 수 있습니다. 특히 분할 정복(Divide and Conquer)과 같은 알고리즘을 구현할 때 유용합니다.
• 문제 해결의 용이성: 일부 문제는 재귀적 접근이 더 자연스럽고 이해하기 쉽습니다. 전형적인 예를 들어, 트리나 그래프 구조를 탐색하거나, 피보나치수열과 같은 수학적 문제를 해결할 때 재귀가 효과적입니다. 
• 코드의 재사용성: 재귀 함수는 종종 모듈화가 용이하여 다른 문제에 적용하기 쉽습니다.

단점

• 성능과 메모리 문제: 재귀 호출은 함수 호출에 따른 오버헤드가 발생하며, 각 호출은 스택 메모리를 사용합니다. 따라서 너무 깊은 재귀는 스택 오버플로우를 일으킬 수 있습니다. 여기에서 Stack Memory를 사용한다는 의미는 함수 내에서 자기 자신을 호출해서 실행할 때에 그 함수에 대한 실행 메모리가 그 함수를 호출한 수만큼 별도로 Memory에 쌓이고 (Stack 메모리 구조로) 실행된다는 의미이기 때문에 메모리 문제가 있을 수 있습니다.
• 디버깅과 추적의 어려움: 재귀 함수는 간단해서 직관적이긴 하지만, 실제 문제가 생겼을 시에 디버깅하기 어려울 수 있으며, 함수 호출 스택이 복잡해지면 버그를 추적하기가 어려워집니다.
• 효율성 문제: 일부 재귀 알고리즘은 중복 계산을 수행할 수 있어, 동적 프로그래밍이나 다른 방법으로 최적화하지 않는 한 비효율적일 수 있습니다.

코딩 테스트 실제 기출문제 - Recursion 알고리즘

캐나다 IT 회사에서 출제된 Recursion 알고리즘 관련 실제 기출문제를 소개합니다. 영문 자체를 한글로 굳이 번역해서 소개하지 않는 이유는 이런 패턴에 익숙해지셔야 하기 때문입니다. 그리고 Solution을 보시기 전에 반드시 우선 문제 자체를 풀어 보시고 접근하시기 바랍니다.

 

Question 1: Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

 

(실제 아래의 예제에서는 TreeNode를 구성하는 부분은 문제에서 주어질 것입니다. 그렇게 구성된 Tree 형식의 구조에서 어떻게 Recursion을 적용하는 지를 구성하시면 됩니다.)

 

Example:

Input:

    3
   / \\
  9  20
    /  \\
   15   7

Output: 3

 

Solution:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxDepth(root):
    if root is None:
        return 0
    else:
        left_depth = maxDepth(root.left)
        right_depth = maxDepth(root.right)
        return max(left_depth, right_depth) + 1

# Test the function
# Create the binary tree from the example
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(maxDepth(root))

 

 

Question 2: Write a recursive function to calculate the nth number in the Fibonacci sequence.

Example: Input: 6   Output:8

Solution:

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

# Test the function
print(fibonacci(6))  # Output: 8

---

 

캐나다 IT 코딩 Binary Search

캐나다 IT 코딩 Selection Sort