PYTHON - 재귀 함수 (피보나치, 하노이의 탑, 최소공배수 등)

2024. 11. 21. 17:35·개발/PYTHON
목차
  1. 재귀함수 (recursion)
  2. 순차탐색
  3. 2진수 변환
  4. 배열의 합
  5. 0~n 까지의 합계 구하기
  6. 1~n 까지의 곱 구하기
  7. x^n 구현
  8. 피보나치 수열
  9. 최대공약수 (유클리드 호제법)
  10. 하노이 타워
728x90
반응형

재귀함수 (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')

 

728x90
반응형
저작자표시 (새창열림)

'개발 > PYTHON' 카테고리의 다른 글

PYTHON - LOG 파일명  (0) 2024.11.25
PYTHON - LOG파일 일별, 날짜별 생성  (0) 2024.11.23
Python 용량 변환  (0) 2024.11.11
Python IMAP 메일 연동  (1) 2024.11.08
CGI, WSGI, ASGI  (4) 2024.09.12
  1. 재귀함수 (recursion)
  2. 순차탐색
  3. 2진수 변환
  4. 배열의 합
  5. 0~n 까지의 합계 구하기
  6. 1~n 까지의 곱 구하기
  7. x^n 구현
  8. 피보나치 수열
  9. 최대공약수 (유클리드 호제법)
  10. 하노이 타워
'개발/PYTHON' 카테고리의 다른 글
  • PYTHON - LOG 파일명
  • PYTHON - LOG파일 일별, 날짜별 생성
  • Python 용량 변환
  • Python IMAP 메일 연동
joolog
joolog
  • joolog
    JOO
    joolog
  • 전체
    오늘
    어제
    • 분류 전체보기 (165)
      • 개발 (83)
        • JAVA (29)
        • PYTHON (9)
        • AWS (15)
        • DOCKER (2)
        • PERCONA (2)
        • ORACLE (14)
        • MYSQL (1)
        • 알고리즘 (0)
        • 기타 (11)
      • 툴 (5)
        • MARKDOWN (1)
        • GIT (1)
        • DOCKER (1)
        • PyCharm (2)
        • IntelliJ (0)
      • 일상 (35)
        • 맛집 (6)
        • 카페 (2)
        • 요리 (4)
        • 글씨 연습 (2)
        • 그저 일상 (7)
        • 내돈 내산 (11)
        • 홍보 (1)
      • 국내 여행 (1)
      • 해외 여행 (15)
        • 체코-오스트리아 (10)
        • 일본 (5)
      • 암 일지 (26)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
    • 글쓰기
    • 관리
    • 티스토리 홈
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    자바
    mysql
    오스트리아
    잘츠부르크
    갑상선 암
    동위원소
    저요오드식
    오닉스 리프3
    글씨연습
    체코
    jdbc
    히로시마
    Oracle
    오라클
    성모샘쉼터
    재발
    자바JDBC
    오블완
    요양병원
    티스토리챌린지
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
joolog
PYTHON - 재귀 함수 (피보나치, 하노이의 탑, 최소공배수 등)

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.