답변자님,
정보를 공유해 주세요.
재귀함수 (recursion)
함수 정의 내에 같은 이름의 함수가 올 때 이를 재귀함수라 부른다.
반드시 탈출조건이 있어야 stack overflow를 방지할 수 있다.
같은 행위가 반복될 때 재귀함수를 사용한다.
예시 - 순차탐색
def search(li, begin, end, target): if begin>end: return -1 elif target == li[begin]: return begin else: return search(li, begin+1, end, target) li = [1,6,10,7,2,5] target = 10 search(li, 0, 5, 10) # 2 |
예시 - 2진수 변환
def print_binary(n): if n<2: print(n, end='') else: print_binary(n//2) print(n%2,end='') print_binary(15) #1111 |
예시 - 배열의 합
li[0]에서 li[n-1] 까지의 합을 구하여 리턴
재귀적 사고방식: li[n-1] + (li[n-2] 까지의 합) 을 구한다
def sum(n, li): if n<=0 or n >= len(li): return 0 return li[n-1] + sum(n-1, li) |
예시 - 0~n 까지의 합계 구하기
def sum(n): # 이 함수의 목표는 0~n 까지의 합을 구하는 것이다 if n == 0: # n=0 이면 합은 0이다 return 0 return n + sum(n-1) # n이 0보다 크면 0에서 n 까지의 합은, n-1까지의 합에 n을 더한 것이다. sum(4) # 10 |
예시 - 1~n 까지의 곱 구하기
def factorial(n): if n == 0: return 1 return n * factorial(n-1) factorial(4) |
예시 - x^n 구현
def power(x, n): if n == 0: return 1 return x * power(x, n-1) power(2,10) # 1024 |
예시 - 피보나치 수열
# 피보나치 수열의 index n의 값을 리턴 # 피보나치 수열 : 1, 1, 2, 3, 5, 8, 13, 21, 34 ... def fibo(n): # 재귀함수는 탈출조건이 꼭 필요하다. if n == 0 or n == 1: return 1 return fibo(n-2) + fibo(n-1) # index n까지의 피보나치 수열 구하기 def fibo_list(n): for i in range(n): print(fibo(i), end= " ") |
예시 - 최대공약수 (유클리드 호제법)
참고: 두수의 곱을 최대공약수로 나누면 최소공배수가된다.
def gcd(m, n): if m < n: m, n = n, m if m % n == 0: return n else: return gcd(n, m%n) print(gcd(48, 60)) # 12 |
예시 - 하노이 타워
A에 있는 n개의 원반 중 맨 아래에 있는 n번째 원반을 제외한 나머지 원반을 모두 B로 옮긴다.
A에 남은 하나의 원반을 C로 옮긴다.
B의 모든 원반을 C로 옮긴다.
def hanoi(num, _from, _by, _to): #탈출 조건 if num == 1: print("{}에서 {}로 {} 번째 원반 이동".format(_from, _to, num)) return hanoi(num-1, _from, _to, _by) print("{}에서 {}로 {} 번째 원반 이동".format(_from, _to, num)) hanoi(num-1, _by, _from, _to) if __name__ == "__main__": while 1: numOfTray = int(input("원반의 개수를 입력하세요!(종료 : 0) :")) if numOfTray == 0: break hanoi(numOfTray, 'A', 'B', 'C') |
2019.09.18.
-
채택
질문자가 채택한 답변입니다.
- 참여
UP이 많은 답변일수록 사용자들에게 더 많이 노출됩니다.
