파이썬
[재귀함수] 개념, 알고리즘 코드
주니코니
2023. 7. 29. 12:25
[재귀함수란?]
(안에 몇개가 들어가있는지 모르는) 마트로시카~! 🌟🌟
1) 1~N까지의 합
함수 사용해서 표현해보면?
def Func(N):
ret =0
for i in range(1,N+1):
ret += i
return ret
print(Func(10))이를 재귀함수로 표현해보면? (코드 대체로 재귀함수로 다 표현 가능)
def Func(N): #큰 오뚜기(Func(N))는
if N <= 0: #0이거나 음수일 때
return 0 #뱉어주다
return N + Func(N-1) #Func(N-1) 작은오뚜기
print(Func(5))
왜 ?
Func(0) =
Func(-1) = 0
왜 ? 더하기는 0에서부터 시작하니까
2) 1~N까지의 곱
함수 사용해서 표현해보면?
def Func(N):
ret =1
for i in range(1,N+1):
ret *= i
return ret
print(Func(10))이를 재귀함수로 표현해보면?
def Func(N):
if N <= 0:
return 1
return N * Func(N-1)
print(Func(5))Func(0) = 1
Func(-1) = 1
왜 ? 곱은 1부터 시작하니까
[수열이란?]
숫자를 일렬로 나열
피보나치 수열
1 1 2 3 5 8 13 21 34
앞의 앞 뒤 더한 숫자
점화식
항과 항 간의 관계 표현하는 식
피보나치 수열을 점화식으로 표현하면?Fn(N) = Fn(N-1) + Fn(N-2)
=> 컴퓨터 입장에서는 재귀함수와 똑같다
재귀함수로 표현해보면
def Func(N):
if N==1 or N ==2:
return 1
return Func(N-1) + Func(N-2)
for i in range(1,10):
print(Func(i),end=' ')
#1 1 2 3 5 8 13 21 34[재귀함수를 알고리즘에 적용해보면?]
재귀함수 - 부르트포스 문제에서 쓰기 추천! (모든 경우의 수를 계산해야할 때)
ex 로또문제
1) 일반 함수로 표현해보면
# 로또 : 번호 7개 중 6개씩 추출하는 경우의 수
def Fn(lotto_list=[1,2,3,4,5,6,7]):
#lotto_list =[1,2,3,4,5,6,7]
#idx 0,1,2,3,4,5,6
for idx in range(len(lotto_list)-1,-1,-1): #(인덱스 길이:6,-1,-1)
#print(idx,lotto_list[idx]) #확인해보고 가기
lotto_list_tmp = lotto_list.copy()
lotto_list_tmp.pop(idx)
print(lotto_list_tmp)#k개 중에 6개를 뽑아라 > '생각을 바꿔서 ' k개 중에 2개를 뽑아보자
def Fn(lotto_list=[1,2,3,4,5,6,7]):
n =len(lotto_list)
for idx in range(n):# 나와
for jdx in range(idx+1,n): #나보다 1 큰 애 뽑기
print(lotto_list[idx],lotto_list[jdx])2) 재귀함수로 표현해보면
10중,20중,(무한대) for문도 다음 4줄로 구현 가능하다! ⭐⭐⭐
lotto_list = [1,2,3,4,5,6,7]
ret_list = [0,0,0,0,0,0]
N =len(lotto_list)
def Fn(depth,idx):
# for 6개 이면 끝내줘! #안정해지면 while문처럼 무한대로 돌아
if depth == 6:
#print(ret_list)
return
for jdx in range(idx,N):
ret_list[depth] = lotto_list[jdx]
Fn(depth+1,jdx+1)
#Fn(0,0)
*마트로니카를 떠올려보세요!
