TIL_21 : 재귀 함수

3464 단어 algorithmTILTIL

🙄 재귀 함수


➡ 재귀 함수(Recursive Function)란?

  • 자기 자신을 호출하는 함수
ex)
def countdown(n):
	if n > 0:
    print(n)
    countdown(n - 1)
    
countdown(4)

# 4
# 3
# 2
# 1



🙄 재귀 활용 예시_1 : 팩토리얼


➡ 재귀적으로 문제를 푼다는 것
= 같은 형태의 더 작은 문제(부분 문제)를 풀고 부분 문제의 답을 이용해서 기존 문제를 푸는 것

n = 0인 경우   n! = 1			# base case
n > 0인 경우   n! = (n-1)! * n		# recursive case

재귀적으로 문제를 풀 때는 항상 base caserecursive case를 모두 생각해내야 함

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

print(factorial(4))

# 24



🙄 재귀 함수 vs 반복문


  • 반복문을 써서 풀 수 있는 문제는 재귀 함수로 풀 수 있다
  • 재귀 함수를 써서 풀 수 있는 문제는 반복문으로 풀 수 있다
  • 반복문으로 쓰면 코드가 지저분하지만 재귀 함수를 쓰면 깔끔해지는 경우 사용
  • 반복문이 더 깔끔하거나 효율적일 때가 있고, 재귀 함수가 더 깔끔하거나 효율적일 때가 있다.

StackOverflowError
재귀 함수 호출이 너무 많으면 call stack이 많아지고 결국 과부하로 프로그램 중단

좋은 웹페이지 즐겨찾기