알고리즘: 재귀 함수(return) 예제 공부하기! (피보나치 수열, 하노이탑, 이진탐색...)

1.  피보나치 수열

 

 

피보나치 수열의 n번째 값을 리턴하는 함수 만들고 10개 항을 출력 해봅시다

 

피보나치 수열이라 함은 전항과 전전항을 더해서 만들어진 수열입니다.

 

1, 1, 2, 3, 5, 8, 13, 21, 34, 55...

 

def fib(n):  # 피보나치 수열
   
    if n <= 2:  # base case
       return 1
       
    return fib(n - 1) + fib(n - 2)

       
   
 # fib(1)부터 fib(10)까지 출력
 
for i in range(1, 11):
    print(fib(i))

 

 

 

2. 삼각수

 

 

  삼각수란 자연수 1부터 n까지의 합을 의미합니다. n 값을 파라미터로 받고 n까지의 삼각수 값을 리턴합니다. 

 

def triangle_number(n):

    if n == 1:  # base case
        return n
        
    return n + triangle_number(n - 1)
    
    

# triangle_number(1)부터 triangle_number(10)까지 출력

for i in range(1, 11):
    print(triangle_number(i))

 

 

 

 

3.  자릿수 합 구하기

 

n이라는 값을 받았을 때, n의 각 자릿수의 합을 리턴해주는 재귀함수를 만듭니다.

 

예를 들어 22541이라는 값을 받았을 때, 각 자리수의 합은 2 + 2 + 5 + 4 + 1 = 14 이므로 14를 리턴합니다. 

 

def sum_digits(n):
   
    if n < 10:
        return n
    
    return n % 10 + sum_digits(n // 10)


print(sum_digits(22541))
print(sum_digits(92130))
print(sum_digits(12634))
print(sum_digits(704))
print(sum_digits(3755))

 

 

 

4. 리스트 뒤집어서 출력하기 

 

 

  파라미터로 리스트를 받아 이 리스트를 역순으로 리턴합니다. 

 

def flip(some_list):
    
    if len(some_list) == 0:
        return some_list

    return some_list[-1:] + flip(some_list[: -1])


some_list = [1, 2, 3, 4, 5, 6, 7, 8, 9]
some_list = flip(some_list)
print(some_list)

 

 

 

5. 이진 탐색 

 

 

  기존의 이진 탐색 알고리즘을 재귀적으로 해석합니다. 

 

def binary_search(element, some_list, start_index = 0, end_index = None): 
  # 간편함을 위해 옵셔널 파라미터를 지정해줍니다. 

    if end_index == None:
        end_index = len(some_list) - 1
    
    
    if end_index - start_index == 0:  # base case 
        
        return start_index
        
   
    
    mid_index = (start_index + end_index) // 2
    
    
    
    if element in some_list[start_index: mid_index + 1]:
       # element 값이 somelist 좌측에 있을 때
       
        return binary_search(element, some_list, start_index, mid_index)
        
        
    elif element in some_list[mid_index + 1: end_index + 1]:
       # element 값이 somelist 우측에 있을 때
       
        return binary_search(element, some_list, mid_index + 1, end_index )
    


print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))

 

0
None
2
1
4

 

 

 

6. 하노이탑 

 

 

  재귀 함수를 이용해 하노이탑 구현하기

 

하노이탑 (출처: 위키피디아)

 

 

def move_disk(disk_num, start_peg, end_peg):
    print("%d번 원판을 %d번 기둥에서 %d번 기둥으로 이동" % (disk_num, start_peg, end_peg))

def hanoi(num_disks, start_peg, end_peg):
  
    mid_peg = 6 - start_peg - end_peg  # mid_peg는 다음과 같이 정의됩니다. 세 개의 기둥 값의 합은 언제나 6이기 때문에 
  
  
    if num_disks == 1:                             # base case
        
        move_disk(num_disks, start_peg, end_peg)
        
    elif num_disks == 2:
    
        hanoi(num_disks - 1, start_peg, mid_peg)
        move_disk(num_disks, start_peg, end_peg)
        hanoi(num_disks - 1, mid_peg, end_peg)
        
    else: 
    
        hanoi(num_disks - 1, start_peg, mid_peg)
        move_disk(num_disks, start_peg, end_peg)
        hanoi(num_disks - 1, mid_peg, end_peg)
        
        


hanoi(3, 1, 3)

 

1번 원판을 1번 기둥에서 3번 기둥으로 이동
2번 원판을 1번 기둥에서 2번 기둥으로 이동
1번 원판을 3번 기둥에서 2번 기둥으로 이동
3번 원판을 1번 기둥에서 3번 기둥으로 이동
1번 원판을 2번 기둥에서 1번 기둥으로 이동
2번 원판을 2번 기둥에서 3번 기둥으로 이동
1번 원판을 1번 기둥에서 3번 기둥으로 이동