TIL 21. [알고리즘] 재귀함수(recursion)

sooo·2020년 10월 25일
0

재귀함수(Recursion)

재귀함수란, 함수 내에서 자기 자신을 다시 호출하는 함수를 말한다.

Countdown

def countdown(n):
    print(n)
    
    if (n==0):
    	return None
    
    countdown(n-1)

해당 함수를 실행하면, n부터 0까지 숫자가 카운트다운되면서 출력된다.

재귀 함수를 작성할 때는 꼭 종료 조건을 넣어주어야 한다. 위 코드에서 n이 0일 때 함수를 종료하는 조건이 없다면 함수는 마이너스까지 내려가서 무한 루프에 빠지게 될 것이다.

Factorial

def factorial(n):

    if (n==1):
    	return None
    else:
    	return n*factorial(n-1)  

팩토리얼 또한 대표적인 재귀함수의 예시 중 하나이다.

재귀 함수는 반복문으로도 작성할 수 있고, 반복문 역시 재귀함수로 작성할 수 있다.
재귀 함수는 반복문에 비해 속도가 느리고, stack 메모리를 사용하기 때문에 호출 횟수가 많아질 경우 stack overflow가 발생할 수 있다.

재귀의 문제점을 해결하기 위한 방법으로 '꼬리재귀'라는 것이 있다.
이에 대한 글은 다음에...

0개의 댓글