2.재귀

1.재귀

- 재귀함수의 기본적인 이해

- 재귀 함수를 실행하는 중간에 다시 재귀 함수가 호출되면, 재귀 함수의 복사본을 하나 더 만들어서 복사본을 실행하게 됩니다.

2.Factorial

- n! = n x (n-1) x (n-2) x (n-3) x ... x 2 x 1

def factorial(num):
    if num <= 0:
        return 1
    return num * factorial(num - 1)

print(factorial(5))
---------------------------------
120

3.Fibonacii sequence 

1. 0, 1, 1, 2, 3, 5, 8, 13, 21

2. '앞에것 두 개 더해서 현재의 수를 만들어가는 수열'이다

3. 시간 복잡도는 O(2ⁿ)

def fibonacci(num):
    if num <= 1: // 피보나치 수열의 첫 번쨰 값을 요구하면,
        return 0
    elif num == 2: // 피보나치 수열의 두 번쨰 값을 요구하면,
        return 1
    else: // 피보나치 수열의 세 번쨰 이후의 값을 요구하면 
        return fibonacci(num - 1) + fibonacci(num - 2)

print(fibonacci(4))
----------------------------
3

4.이진 탐색 알고리즘의 재귀적 구현 

1. 탐색 범위의 중앙에 목표 값이 저장되었는지 확인

2. 저장되지 않았다면 탐색 범위를 반으로 줄여서 다시 탐색 시작

def r_binary_search(search_list, first, last, target):
    if first >= last:
        return

    mid = (first + last) // 2

    if target == search_list[mid]:
        return target
    elif target > search_list[mid]:
        return r_binary_search(search_list, mid + 1, last, target)
    else:
        return r_binary_search(search_list, first, mid - 1, target)


e_list = [1, 2, 3, 4, 5, 6, 7, 8, 23, 24]
print(r_binary_search(e_list, 0, len(e_list) - 1, 23))
----------------------------------------
23

 

5.하노이 타워

- 원반은 한 번에 하나씩만 옮길 수 있습니다. 그리고 옮기는 과정에서 작은 원반의 위에 큰 원반이 올려져서는 안됩니다.

- 하노이의 타워의 반복패턴 연구.

1. 작은 원반 n-1개를  a에서 b로 이동

2. 큰 원반 1개를 a에서 c 로 이동 

3. 작은 원반 n-1 개를 b에서 c로 이동

def hanoitower(num, h_from, h_by, h_to):
    if num == 1:
        print("원반1을 {}에서 {}로 이동 \n".format(h_from, h_to))
    else:
        hanoitower(num - 1, h_from, h_to, h_by)
        print('원반{}을 {}에서 {}로 이동\n'.format(num, h_from, h_to))
        hanoitower(num - 1, h_by, h_from, h_to)


hanoitower(3, 'A', 'B', 'C')
----------------------------------------------------
원반1을 A에서 C로 이동

원반2을 A에서 B로 이동

원반1을 C에서 B로 이동

원반3을 A에서 C로 이동

원반1을 B에서 A로 이동

원반2을 B에서 C로 이동

원반1을 A에서 C로 이동