2. 재귀함수

1. 재귀 함수(recursion)

• 자기 자신을 호출하는 함수

#ex)
def countdown(n):
	if n>0:
		print(n)
		countdown(n-1)

• 재귀적으로 문제를 풀다
  같은 형태의 더 작은 문제(Subproblem)를 풀고 그 답을 이용해서 기존 문제를 푸는 것
  base case, recursive case를 나누어서 모두 생각해야함(base case: 너무 작아서 문제가 쉽게 풀리는 경우-즉, 함수를 닫는 코드)

• 재귀 활용 예시 - 팩토리얼(Factorial)
  n! n=0인 경우, n! = 1
  n>0인 경우, n! = (n-1)! x n
  

   (4,3,2,1은 0이 아니므로 else로 들어가서 다음 함수를 호출)

• 재귀함수 vs 반복문

재귀함수는 함수 내에서 다시 함수를 호출할 때 call stack으로 불러올 위치를 저장해둔다. 너무 많이 호출하면 stack overflow가 발생한다(파이썬은 1000번으로 제한)

효율성을 고려해서 재귀함수와 반복문을 선택 사용해야한다

2. 재귀함수 문제풀이

1. 피보나치 수열

# n번째 피보나치 수를 리턴
def fib(n):
    if n<3:    #닫는 문장
        return 1
    else:
        return fib(n-1)+fib(n-2)

print(fib(4))

fib(4) = fib(3)+fib(2)

fib(3) = fib(2) + fib(1)

fib(2)=1 fib(1)=1

—> fib(3) = 1+1 =2

fib(4) = 2+1 =3

2. 숫자 합

# 1부터 n까지의 합을 리턴
def triangle_number(n):
    if n<=1 :
        return 1
    else:
        return n + triangle_number(n-1)

3. 자릿 수 합

# n의 각 자릿수의 합을 리턴
def sum_digits(n):
    if n>=1:
        return sum_digits(n//10)+ n%10
    else:
        return 0

4. 리스트 뒤집기

# 파라미터 some_list를 거꾸로 뒤집는 함수
def flip(some_list):
    if len(some_list)==0 or len(some_list)==1 :
        return some_list
    else:
        return some_list[-1:]+flip(some_list[:-1])

[1,2,3,4,5] → [5,4,3,2,1] = [5] + flip([1,2,3,4])

[1,2,3,4] → [4,3,2,1] = [4] + flip([1,2,3])

...

5. 이진 탐색 재귀로 구현

def binary_search(element, some_list, start_index=0, end_index=None):
    # end_index가 따로 주어지지 않은 경우에는 리스트의 마지막 인덱스
    if end_index == None:
        end_index = len(some_list) - 1

    # start_index가 end_index보다 크면 some_list안에 element는 없다
		#element를 찾기 위해서 범위를 줄이면서 start_index>end_index가 되면 확실하게 element가 없음을 알 수 있다.
    if start_index > end_index:
        return None
      
    # 범위의 중간 인덱스를 찾는다
    mid = (start_index + end_index) // 2
  
    # 이 인덱스의 값이 찾는 값인지 확인을 해준다
    if some_list[mid] == element:
        return mid

    # 찾는 항목이 중간 값보다 작으면 리스트 왼쪽을 탐색해준다
    if element < some_list[mid]:
        return binary_search(element, some_list, start_index, mid - 1)

    # 찾는 항목이 중간 값보다 크면 리스트 오른쪽을 탐색해준다
    else:
        return binary_search(element, some_list, mid + 1, end_index)

6. 하노이의 탑

#n:원반의 개수
#from_pos: 출발기둥번호
#to_pos: 도착기둥번호
#aux_pos: 중간에거치는기둥번호
def hanoi(n, from_pos, to_pos, aux_pos):
	if n==1:
		print(from_pos, "->", to_pos)
	#원반 n-1개는 aux_pos로 이동(to_pos가 보조기둥으로)
	hanoi(n-1, from_pos, aux_pos, to_pos)
	#from_pos에 남아있던 가장 큰 원반1개를 to_pos로 이동
	print(from_pos, "->", to_pos)
	#aux_pos에 있는 원반 n-1개를 to_pos로 이동(from_pos를 보조기둥으로)
	hanoi(n-1, aux_pos, to_pos, from_pos)