(파이썬) 재귀 함수

1. 재귀호출(recursive call)

• 함수 안에서 동일한 함수를 호출하는 형태
• 여러 알고리즘, 고급 정렬 알고리즘 작성시 사용됨

 

 

1-1. 재귀 호출 분석

2! = 1 * 2
3! = 1 * 2 * 3
4! = 1 * 2 * 3 * 4 = 4 * 3!

 

 

1-2. 규칙

n! = n * (n-1)!

• 규칙을 함수로 표현해보기

    함수(n)은 n>1 이면 return n*함수(n-1)
    함수(n)은 n=1 이면 return n

 

 

1-3. 검증

1. 2!

함수(2)이면 2>1 이므로 2*함수(1)
함수(1)은 1이므로 return 2*1
결과는 2

1. 3!

함수(3)이면 3>1 이므로 3*함수(2)
함수(2)는 1번식에 의해 2!이므로 return 2*1
3*함수(2)는 3*2=3*2*1
결과는 6

1. 4!

함수(4)이면 4>1 이므로 4*함수(3)
함수(3)은 2번식에 의해 3*2*1 = 6
4*함수(3) = 4*6=4*3*2*1
결과는 24

 

In [ ]:

def factorial(num):
    if num > 1:
        return num* factorial(num-1)
    else:
        return num

 

In [ ]:

factorial(4)

 

Out[ ]:

24

 

 

1-4. 재귀호출의 전형적인 예

• 재귀 함수는 내부적으로 스택처럼 관리
• 파이썬에서 재귀함수의 깊이가(한번에 호출되는) 1000회 이하로 되어야 함
• 코드분석

 

 

문제

회문(순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 의미)을 판별할 수 있는 함수를 리스트 슬라이싱과 재귀함수를 활용하여 만들어보자. (단, 회문이면 결과를 True, 아니면 False를 변환)

 

In [ ]:

def palindrome(str):
    str = str.strip()
    if len(str) <= 1:
        return True
    elif str[0] == str[-1]:
        return palindrome(str[1:-1])
    else:
        return False

 

In [ ]:

palindrome('네가 본 스리랑카랑 리스본 가네')

 

Out[ ]:

True