파이썬 기초(23)-재귀 함수

 

*이 글을 읽기전에 작성자 개인의견이 있으니, 다른 블로그와 교차로 읽는것을 권장합니다.*

1. 재귀 호출(recursive call)

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

1-1. 재귀 호출 규칙(팩토리얼!)

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

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

1-2. 검증

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

```
2!
함수(2)이면 2>1 이므로 2*함수(1)
함수(1)은 1이므로 return 2*1
결과는 2
```
def factorial(n):
    if n >1:
        return n * factorial(n-1)
    else:
        return n
factorial(4)

#설명
#factorial(4)=4*factorial(3)=4*3*factorial(2)=4*3*2*factorial(1)=4*3*2*1

1-3. 재귀호출의 예

재귀함수는 내부적으로 스택처럼 관리합니다. 파이썬에서 재귀함수의 깊이(한번에 호출되는)는 1000회 이하로 되어야 합니다.

• [코드분석 툴] (https://pythontutor.com/)-> python tutor로 연산처리과정 확인가능

python tutor 사용 예

문제

회문(순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 의미)을 판별할 수 있는 함수를 만들어보자.

• 재귀함수 사용
• 회문이면 결과를 True, 아니면 False 반환

결과값이 True, False 2가지로 나눠있다면 경우의 수가 2가지밖에 없으므로, if, else만으로 해결가능하다. 회문은 변수[start:stop:빈도=-1]로 할 경우 거꾸로 읽게 된다.

#어떤 문자열이나 문장을 입력하더라도 회문이면 True가 판별
a=input('입력하세요')
def factorial(a):
    if a == a[::-1]:
        return True
    else:
        return False

factorial(a)

문제

정수 n을 입력받아 아래와 같이 처리되는 프로그램을 만들어보자.

• n이 홀수면 3n+1을 함(3 * 3 + 1 -> 10)
• n이 짝수면 n을 2로 나눔( 10 / 2 ->5)
• 이렇게 계속 진행하여 n이 결국 1이 될때까지 위 조건을 반복하면서 실행

위 경우의 수는 n이 홀수일 때, n이 짝수일 때, n이 1일 때로, 총 3가지로 나뉘는 것을 유의해야 한다. 또한 n이 짝수일 때와, n이 홀수일때 모두 재귀함수가 들어가는 것을 유념해야 한다.

def oo(n):
    print(n)
    if n ==1:
        return n
    if n % 2 >0:
        return oo(3*n+1)
    else:
        return  oo(int(n/2))

n=int(input('n을 입력하세요'))
oo(n)