함수와 재귀함수(Python)

함수

 

 

💡 1. 함수는 def 함수이름(파라미터) 구조로 선언하며, namespace에 등록된다.

 

       2. sum, list 등 built-in예약어(고유한 이름을 가진 예약어) 를 덮어 씌우지 않도록 주의한다.

 

       3. return 이 없다면 반환값이 존재하지 않는다.

 

# 들어온 인자를 리스트로 묶어 반환하는 함수 선언
def some_func(pa1, pa2):
	return [pa1, pa2]
    
print(some_func(1,2)) # [1,2] 실행

 

 

# 리턴문 없는 경우는?

def some_func(pa1, pa2):
	my_list = [pa1,pa2]
    
print(some_func(1,2)) # -> NONE 반환

print(my_list) # 에러가 뜰 것이다. 지역 변수인 my_list는 함수를 벗어나면 적용되지 않기 때문.

 

재귀함수

 

💡 함수 내에서 동일한 함수가 실행되는 함수

 

 

 

피보나치 수열의 재귀함수 구현

 

-> 피보나치 수열은 각 숫자가 앞의 두 숫자의 합으로 정의된다.

 

def fibo(n):
	if n < 2 :  # 1은 더 쪼개지지 않음
		return n
	else:
		return fibo(n-1) + fibo(n-2)  # 재귀 호출

print(fibo(10)) # 55

 

1. fibo(10)을 호출

2. n이 2보다 크므로, fibo(9)와 fibo(8)을 호출하여 각각의 값을 계산.

3. fibo(9)를 계산하기 위해 fibo(8)과 fibo(7)을 호출하고, fibo(8)을 계산하기 위해 fibo(7)과 fibo(6)을 호출하는 식으로 계속하여 재귀적으로 호출.

4.fibo(1)과 fibo(0)에서는 더 이상 재귀 호출이 일어나지 않고, 각각 1과 0을 반환

 

 

이렇게 반환된 값들이 차례로 더해지면서 최종적으로 fibo(10)의 값을 계산한다.

 

 

 

 

메모이제이션(Memoization) 기법을 사용하여 계산 (참고용)

memo = [0, 1]

def fibo(n):
    if n >= 2 and n >= len(memo):
        memo.append(fibo(n-1) + fibo(n-2))
    return memo[n]

print(fibo(10))


# 처음에 fibo(10)을 호출
# fibo 함수는 memo 리스트의 길이를 확인하고, 10번째 값이 없으면 재귀적으로 fibo(9)와 fibo(8)을 호출하여 값을 계산
# 이 과정이 반복되면서 필요한 값들이 memo 리스트에 저장
# 이미 계산된 값은 다시 계산하지 않고, memo 리스트에서 값을 가져옴
# 최종적으로 memo[10] 값을 반환

메모이제이션은 이전에 계산한 값을 저장해 두고, 필요할 때 이를 재사용함으로써 중복 계산을 피하는 기법이다.

 

 

 

이진탐색 방법

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]

def binary_search(low, high, target):
    if low > high:
        return '찾지 못함'

    mid = (low + high) // 2
    if target == nums[mid]:
        return mid
    elif target < nums[mid]:
        return binary_search(low, mid-1, target)
    elif target > nums[mid]:
        return binary_search(mid+1, high, target)

print(binary_search(0, len(nums)-1, 7))

#처음에 binary_search(0, 8, 7)을 호출
#mid 값은 (0 + 8) // 2 = 4가 되고, nums[4]는 5
#7은 5보다 크므로, 오른쪽 절반에서 다시 탐색: binary_search(5, 8, 7)
#이번엔 mid 값이 (5 + 8) // 2 = 6가 되고, nums[6]는 7
#목표값을 찾았으므로, 인덱스 6을 반환