[Algorithm] 재귀(Recursion)

안녕하세요! 공대남입니다.

오늘은 재귀 알고리즘에 대해 알아볼게요.

 

재귀(Recursion) 알고리즘이란?

하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 알고리즘이다.

 

재귀함수 ? 재귀호출 ?

자기자신을 호출하는 함수를 재귀함수라고 하며, 이때 하는 호출을 재귀호출이라고 합니다.

 

재귀함수의 장점과 단점

• 직관적이다

• 무한루프에 빠질수있다.
• 재귀 호출의 깊이가 너무 깊어지면 너무 많은 메모리를 사용한다.
• 불필요한 반복 연산을 하게 될 가능성이 있다. => 메모이제이션을 통해 해결가능

 

팩토리얼 문제 

def factorial(n):
    if n <= 1:
        return 1
    
    else:
        return n * factorial(n - 1)

n = int(input())
print(factorial(n))

 

피보나치 문제

int fibonacci(int n) {
    if (n == 1 || n == 2) return 1;
    else return fibonacci(n - 1) + fibonacci(n - 2);
}
 
int fibonacci_memo(int n) {
    if (n == 1 || n == 2) return 1;
    if (memo[n] != 0) return memo[n]; // 메모이제이션
    else memo[n] = fibonacci_memo(n - 1) + fibonacci_memo(n - 2); // memo 에 저장
    return memo[n];
}

 

하노이 탑, 플러드 필, 프랙탈 트리, 파일 탐색 등등