[파이썬, Python] 알고리즘 - 1️⃣ 재귀호출(recursive call)

1. 재귀호출이란❓

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

 

1-1. 재귀 호출 분석

• 2! = 1 * 2
• 3! = 1 * 2 * 3 = 3 * 2!
• 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. 검증

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

def factorial(num):
  if num > 1:
    return num * factorial(num - 1)
  else:
    return num
    
for num in range(6):
  print(factorial(num))

>>> 
0
1
2
6
24
120

1-4. 재귀 호출의 일반적인 형태

 

1️⃣ 첫번째

def factorial(num):
  if num > 1:
    return num * factorial(num - 1)
  else:
    return num
    
for num in range(6):
  print(factorial(num))
  
>>> 
0
1
2
6
24
120

 

2️⃣ 두번째

def factorial(num):
  if num <= 1:
    return num
  return num * factorial(num-1)
  
for num in range(10):
  print(factorial(num))

>>> 
0
1
2
6
24
120
720
5040
40320
362880

 

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

• 함수는 내부적으로 스택처럼 관리

[코드분석]https://pythontutor.com/visualize.html#mode=display

Python Tutor code visualizer: Visualize code in Python, JavaScript, C, C++, and Java

 

파이썬에서는 재귀 함수 깊이가(한번에 호출되는) 1000회 이하로 되어야 함!!!

 

 

✅ 다음 함수를 재귀 함수를 활용해서 1부터 num 까지의 곱이 출력되도록 만들어보자.

def multiple(data):
  return_data = 1
  for index in range(1, num + 1):
    return_data = return_data * index
  return return_data

multiple(10)
>>> 362880

 

 

✅ 회문은 "순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 의미".

회문을 판별할 수 있는 함수를 리스트 슬라이싱을 활용하여 만들어보자.

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

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

print(palindrome('wow'))
print(palindrome("aabbccbbaa"))
print(palindrome('motor'))

>>> 
True
True
False

 

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

• n이 홀수면 3 * n + 1을 함
• n이 짝수면 n을 2로 나눔
• 이렇게 계속 진행해서 n이 결국 1이 될 때 까지 1과 2를 반복하며 실행
• 재귀함수를 사용

def func(num):
  print(num)
  if num == 1:
    return num

  if num % 2 == 1:
    return func(3*num + 1)
  else:
    return func(int(num)/2)
    
func(3)

>>> 
3
10
5.0
16.0
8.0
4.0
2.0
1.0
1.0