Python 자료구조 & 알고리즘 - 재귀호출

1. 재귀호출(recusive call)

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

---

1-1. 재귀 호출 분석

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

 

---

1-2. 규칙

• n! = n * (n-1)!
  • 함수로 만들어 보자
  • 함수(n)은 n=1
  • 함수(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! 이므로 return 321 = 6
  • 4 * 함수(3) = 4*6 = 4 * 3 * 2 * 1, 답은 24

 

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

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

 

---

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

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

 

---

문제

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

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

문제

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

1. n이 홀수이면 3 * n + 1을 계산
2. n이 짝수이면 n을 2로 나눈 계산
3. 이렇게 계속 반복해서 n이 결국 1이 될 때까지 1보느 2본 계산을 실행
4. 재귀함수로 작성 
5. 3 10 5 16 8 4 2 1