2. 재귀함수

 

#1.재귀함수(recursive call)
* 함수 안에서 동일한 함수를 호출하는 형태
* 여러 알고리즘, 고급 정렬 알고리즘 작성시 자주 사용됨


### 1-1. 재귀 함수 호출 분석
* 2! = 1 * 2
* 3! = 1 * 2 * 3


### 1-2. 규칙
'''
n! = n (n-1)!
'''
* 함수로 만들기 = def factorial(num)
* factorial(num)은 num > 1 이라면 return n * factorial(n-1)
* factorial(num)은 num = 1 이라면 return n


### 1-3. 검증
* 2!
 * factorial(2)이면 2 > 1 이므로 2 * factoral(1)
 * factorial(1)은 1이므로 return 2 * 1
 * 결과는 2
 
 * 3!
    * factorial(3)이면 3 > 1 이므로 3 * factorial(2)
    * factorial(2)는 위 결과에 따라 2! 이므로 return 2* 1 = 2
  따라서 3 * factorial(2) = 3* 2 * 1
  * 결과는 6


#1-4. 코드 레벨로 만들어 보기
def factorial(num):
  if num > 1:
    return num * factorial(num-1)
  else:
    return num

for num in range(5):
  print(factorial(num))
-->
1
2
6
24

재귀호출의 예
https://pythontutor.com/visualize.html#mode=display

 

2. 재귀호출과 스택

 

###문제
회문은 "순서를 거꾸로 읽어도 제대로 읽은것과 같은 단어와 문장을 의미" 합니다. 회문을 판별할 수있는 함수를 만들어보자
  * 단, 재귀함수를 사용하며 결과는 회문일 경우 True,아니면 False를 반환

def pa(str):
  if len(str) <= 1:
    return True
  if str[0] == str[-1]:
    return pa(str[1:-1])
  else:
    return False
 
 pa('별똥별')
 pa('pa')
 -->
 True
 False
 
 
##문제 2
* 정수 n을 받아 아래와 같은 조건을 만족하는 프로그램을 만들어보자
* 조건
  1. n이 홀수면 3 * n + 1을 함
  2. n이 짝수면 n을 2로 나눔
  3. 위 계산을 반복해서 n이 결국 1이 될떄 까지 1과 2를 반복하여 실행
* 단 재귀함수를 사용
'''
3 <= 입력
10
5
'''

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

func(3)
-->
3
10
5
16
8
4
2
1
1


### 과제
정수 4를 1, 2, 3의 조합으로 나타내는 방법이 아래와 같이 총 7가지 있음
'''
1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2
1 + 3
3 + 1
'''
정수 n이 입력으로 주었을때 n을 1,2,3의 합으로 나타낼 수 있는 방법의 수를 구해보자
'''
def func(data):
  pass

func(4)
'''