[알고리즘] 재귀 용법(Recursive Call) (Python)

1. 재귀 용법(Recursive Call)

• 함수 안에서 동일한 함수를 호출하 형태
• Python에서는 재귀함수 깊이가 1000회 이하여야 함(Python 자체적으로 고정된 stack공간을 잡아놨기 때문)

 

2. 일반적인 형태

• 임의의 입력이 주어진다.
• 임의의 조건이 주어진다.
• 입력이 임의의 조건을 충족시킬 때까지 재귀호출이 된다.

 

3. 코드 구현

팩토리얼 연산은 조금 식상한 면이 있어서 좀 신박한 예제들을 재귀 용법을 통해 구현해봤다.

 

3.1 회문(palindrome) 판별기

def palindrome(input):
    if len(input)<=1:
        return True
    if input[0] == input[-1]:
        return palindrome(input[1:-1])
    else:
        return False

 

 

3.2 정수 n이 입력으로 주어졌을 때, n을 1,2,3의 합으로 나타낼 수 있는 방법의 가짓수

• f(n) = f(n-1) + f(n-2) + f(n-3)이란 패턴 도출한 후

def func(n):
    if n==1:
        return 1
    elif n==2:
        return 2
    elif n==3:
        return 4
    elif n>=4:
        return func(n-1) + func(n-2) + func(n-3)