12_재귀호출

1. 재귀 호출 (recusive 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)은 n>1 이면 return n*함수(n-1)

 

 

1-3. 검증

• 2!
  • 함수(2)이면 2 > 1 이므로 2 * 함수(1)
  • 함수(1)은 1이므로 return 2 * 1, 답은 2
• 3!
  • 함수(3)이면 3 > 1 이므로 3 * 함수(2)
  • 함수(2)는 위 계산에 의해 2! 이므로 return 2 * 1 = 2
  • 3*함수(2) = 3 * 2 = 3 * 2 * 1 , 답은 6
• 4!
  • 함수(4)이면 4>1 이므로 4 * 함수(3)
  • 함수(3)은 위 계산에 의해 3 * 2 * 1 = 6
  • 4 * 함수(3) = 4 * 6, 4 * 3 * 2 * 1 , 답은 24

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

factorial(4)

24

 

1-4. 재귀호출의 시간 복잡도

• factorial(n)은 n-1번의 factorial() 함수를 호출해서 곱셈을 함
  • n-1번 반복문을 호출한 것과 동일
  • factorial() 함수를 호출할 때마다 지역변수 n이 생성됨
  • 시간 복잡도는 O(n-1)이므로 O(n)

 

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

• 함수는 내부적으로 스택처럼 관리
• 코드분석

 

문제

회문(순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 의미)을 판별하는 함수를 리스트 슬라이싱을 활용하여 만들어보자

• 재귀함수를 사용
• 회문이면 True, 아니면 False 반환
• [참고사항] (https://dojang.io/mod/page/view.php?id=2331)

def palindrome(string):
    pass

palindrome('우영우')

palindrome('김사과')

word = input('단어를 입력하세요: ')
 
palindrome = True                   # 회문 판별값을 저장할 변수, 초깃값은 True
for i in range(len(word) // 2):     # 0부터 문자열 길이의 절반만큼 반복
    if word[i] != word[-1 - i]:     # 왼쪽 문자와 오른쪽 문자를 비교하여 문자가 다르면
        palindrome = False          # 회문이 아니면 False 반환
        break
 
print(palindrome)                 # 회문 판별값 출력

단어를 입력하세요: 아이오이아

True

 

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

palindrome('우영우')

True

palindrome('김사과')

False

 

문제

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

1. n이 홀수면 3 * n+1 계산
2. n이 짝수면 n을 2로 나눈 계산
3. 이렇게 계속 반복해서 n이 결국 1이 될 때까지 1번, 2번 계산을 실행

• 단, 재귀함수로 작성

예)

3

10

5

16

8

4

2

1

 

def input_num(n):
    print(n)
    if n == 1:
        return n
    if n % 2 == 1:
        return (input_num((3*n)+1))
    else:
        return (input_num(int(n/2)))
    pass

input_num(3)

 

3

10

5

16

8

4

2

1