[Algorithm] 재귀 알고리즘

📌 재귀함수

---

재귀 (recursion)란 선언한 함수 내부에서 자기 자신을 다시 호출하는 방법을 뜻합니다.

프로그래밍의 함수 정의에서 많이 사용됩니다.

예시를 통해 알아보겠습니다.

def countdown(n):
	print(n)
    countdown(n-1) ## 함수 자신을 다시 호출하는 부분

이 코드를 실행시키면 10부터 1씩 감소합니다.

음수 값이 끝없이 출력되는 것을 확인할 수 있습니다.

그렇기 때문에 재귀함수에는 종료 조건을 작성해주는 코드가 필요합니다.

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

이제 문제를 통해 연습해보겠습니다.

✅ 문제

---

재귀를 사용하여 팩토리얼(factorial)을 구하는 함수를 구현해주세요.

팩토리얼이란 1에서부터 n까지의 정수를 모두 곱한것을 말합니다.

1! = 1 2! = 1 2 5! = 1 2 3 4 * 5

📌 풀이

---

팩토리얼을 재귀함수로 다음과 같이 표현할 수 있습니다.

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