오늘은 왠일로 새로운 알고리즘 개념에 대해 배워보는 날이었다!

재귀 알고리즘?

재귀(recursion)란, 자신을 정의할 때 자기 자신을 호출하는 방법을 뜻하며, 프로그래밍의 함수정의에서 많이 사용된다.

def countdown(n):
  print(n)
  countdown(n-1)
 
countdown(10);
def countdown(n):
  print(n)
  countdown(n-1)

countdown(10);

예를들면, countdown 함수는 받은 인자를 출력한다.
그런데 위의 함수를 실행하면 10에서 시작해서 무한으로 마이너스 값까지 내려간다. (말도 안되쟈나)

이렇게 땅 끝까지 파고드는 상황을 방지하기 위해, 재귀함수는 아래의 절차가 꼭 필요하다.

언제 멈출것인가?

이를 고려해 0이 되면 더이상 재귀를 이어나가지 않도록 종료 조건을 추가해보자.

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

countdown(10);

문제

재귀를 사용하여 팩토리얼(factorial)을 구하는 함수를 구현해주세요.
: 팩토리얼이란 1에서부터 n까지의 정수를 모두 곱한것을 말합니다.

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

---

model solution

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

1~n까지의 모든 정수를 곱한 것을 리턴보내기 때문에,
0일 경우에 대한 종료 조건만 추가해주면 된다.

아직 재귀 알고리즘에 대한 이해가 부족한 상태이기 때문에, 더 잘 공부해보아야 할 것 같다.. ㅠㅠ