27. 재귀 호출

1. 재귀 호출(recursive call)

파이썬의 os 모듈은 운영 체제와 상호 작용하는 많은 함수와 유틸리티를 제공합니다. 이 모듈을 사용하면 파일, 디렉터리 또는 운영 체제에 관한 작업을 수행할 수 있습니다.

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

 

1-1. 각 파일의 첫번째 라인을 찾아 변경하기

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

• n! = n * (n-1)!

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

 

 

1-2. 검증

 # 2!
 함수(2)이면 2>1 이므로 2*함수(1)
 함수(1)은 1이므로 return 2*1
 결과는 2
# 3!
함수(3)이면 3>1 이므로 3*함수(2)
함수(2)는 위의 식에 의해 2!이므로 return 2*1
3*함수(2)는 3*2=3*2*1
결과는 6
# 3!
함수(4)이면 3>1 이므로 4*함수(3)
함수(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

 

1-3. 재귀호출의 예

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

 

※ 문제 1

 

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

• 단 회문이면 결과를 True, 아니면 False를 반환

 

 

※ 문제 2

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

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