1. 재귀함수

① 개념

• 함수 내에 자기자신(함수)이 들어있는 함수

② 효과

• 스스로를 이용하기 때문에 코드 효율이 높아짐

③ 주의사항

• 무한의 굴레에 빠질 수 있음
• 함수에서 빠져나오는 코드 필수

2. 예시

① 카운트 다운

- 문제 설명

• 재귀함수를 사용해 60부터 0까지 표현해보자

- 설계

• 규칙 찾기: 함수의 결과가 자기자신의 인자로 들어가 또 다른 결과를 도출한다. 그러므로 재귀함수 사용이 가능하다.
• 탈출 조건: n == 0 또는 n < 0

- 함수 인자에 60이 들어가면
- 함수는 59(=60-1)를 반환한다.

- 함수 인자에 59가 들어가면
- 함수는 58(=59-1)를 반환한다.

- 함수 인자에 58이 들어가면
- 함수는 57(=58-1)를 반환한다.

.
.
.

- 함수 인자에 2가 들어가면
- 함수는 1(=2-1)을 반환한다.

- 함수 인자에 1가 들어가면
- 함수는 0(=1-1)을 반환한다.

- 함수 인자에 0이 들어가면
- 함수를 탈출한다.

- 코드 및 코드 설명

input = 60

def count_down(time): 1) time = 60일 때 / 2) time = 59  / 3) time = 58

    # 탈출 조건: time이 0보다 작으면 함수에서 탈출하기
    if time < 0:         	# 1-1) 60 < 0 -> false 
    	return 			# 2-1) 59 < 0 -> false
        			# 2-3) 58 < 0 -> false
      
    # 시간 현시하기	        # 1-2) 60
    print(time)			# 2-2) 59
    				# 2-3) 58
	
    # 재귀함수: count_down 함수에 인자를 60-1로 넣어 다시 count_down 함수 부르기 
    return count_down(time-1)   # 1-3) count_down(59)
    				# 2-3) count_down(58)
                    		# 3-3) count_down(57)


count_down(input)

② 팩토리얼: 연속된 수 곱하기

- 문제 설명

• 재귀함수를 사용해 n부터 1까지 모든 자연수를 곱한 결과를 반환해보자

- 설계

• 규칙 찾기: n! = n x (n-1)!
• 탈출 조건: n == 1

- n == 5일 때
- 5 * 4!을 반환한다.

- n == 4일 때
- 4 * 3!을 반환한다.

- n == 3일 때
- 3 * 2!을 반환한다.

- n == 2일 때
- 2 * 1!을 반환한다.

- n == 1일 때
- 탈출한다.

- 코드 및 코드 설명

def factorial(number): 1) number = 5일 때 / 2) number = 4  / 3) number = 3

    # 탈출 조건:
    if number == 1:         	# 1-1) 5 == 1  -> false 
    	return 1 			# 2-1) 4 == 1 -> false
        			# 2-3) 3 == 1 -> false
      
	
    # 재귀함수: 
    return number * factorial(number-1)   # 1-3) factorial(5) = 5 * factorial(4)
    					  # 2-3) factorial(4) = 4 * factorial(3)
                    		  	  # 3-3) factorial(3) = 3 * factorial(2)


print(factorial(input))

③ 회문 검사

- 문제 설명

• '토마토'와 같이 정방향 또는 역방향 음절이 동일한 문자인지 확인하기

- 설계

• 규칙 찾기: 첫 글자와 마지막 글자 동일한지 확인하기
• 탈출 조건: 글자를 모두 확인했을 때 or 비교 시 서로 다른 글자가 있을 때

- string = 'abcba'일 때,

- 첫 글자 'a'와 마지막 글자 'a'가 같은지 확인한다.
- 틀리면 false를 반환하고 함수를 탈출한다.
- 만약 글자를 모두 확인했다면
- True를 반환하고 함수를 탈출한다.
- 위 2가지 조건을 모두 만족하지 않으면 두 번째 'b'와 마지막에서 두번째 'b'를 비교한다.

- 코드 및 코드 설명

input = 'abcba'

def palindrome(string):
	
    # 첫 글자와 마지막 글자가 같은지 확인한다.
    # 틀리면 false를 반환하고 함수를 탈출한다.
    if string[0] != string[-1]:
       return False
      
    # 만약 글자를 모두 확인했다면
    # True를 반환하고 함수를 탈출한다.
    if len(string) <= 1:
       return True

    # 위 2가지 조건을 모두 만족하지 않으면 두 번째 'b'와 마지막에서 두번째 'b'를 비교한다.
    return palindrome(string[1:-1])
    
print(palindrome(input))

3. 배운 점

① 코드 구현하기

• 규칙 찾기: 일종의 슈도코드이다. 생각한 방법을 코드화하고 한글로 적어보는 것이다. 그리고, 규칙을 찾아본다. 이러면 어떻게 코드를 짜야할지 감이 온다.
• 결과 반복 3회: 위 슈도코드의 반복 또는 규칙을 발견했다면 그 다음은 작은 수나 간편한 수를 넣어 실험해 보는 것이다. 한글로 작성한 코드에 작은 수를 넣어보고 그 결과를 관찰한다.
• 코드 작성: 결과 반복 3회의 결과가 내가 생각한 결과와 일치한다면 코드 작성을 시작한다. 코드 작성 시 가장 중요한 부분은 시작, 종료, 반복하는 부분이다.

② 응용

• 모든 지식은 사용하지 않을 때에는 쓸모가 없다.
• 단순히 지식을 쌓기 위해서 알고리즘을 배우는 것이 아니다.
• 배운 후에는 적용하기 위해 스스로 문제를 만들고 풀어보자.
• 배운 지식 뿐만 아니라 문제의 특징을 이용한 타 방법도 고려해보자.
• 그래야만이 비교군이 형성되고, 본 지식의 효용성을 더 명확하게 인지할 수 있을 것이다.