제 6장: 그 외의 알고리즘들(4)

71. 재귀 호출을 이용해 N의 팩토리얼 구하기

• 재귀호출: 함수에서 값을 구하기 위해 자기자신을 호출하는 표현이 포함된 상황
• 재귀 호출에서 자기 자신을 다시 호출하기만 하는 경우에는 무한 루프에 빠질 수 있으므로 아래 등을 적용해 무한루프를 막아야한다.
  • 자기자신을 다시 호출하는 경우와 단순하게 결과값만 반환하는 경우를 분리
• n의 팩토리얼(n!)을 구하는 알고리즘을 이용해보자.
  • n! = 1 * 2 * 3 * … * (n-1) * n
  • 이 때 (n-1)을 미리 구했다면 (n-1)! * n 으로 구할 수 있다.
  • 즉, n!을 구하는 함수를 fact(n)이라고 했을 경우
  • fact(n) = fact(n-1)! * n과 같이 함수가 스스로를 호출하도록 표현할 수 있다.
    • n = 1 → 1! = 1
    • n ≥ 2 일 경우 fact(n-1)! * n을 반환

칼럼: 알고리즘과 플로우 차트(순서도)

• 플로우차트: 알고리즘의 처리 흐름(해결 방법)을 시각적으로 명확화
• 미리 약속된 기호들을 사용해 처리의 흐름을 설명
• 대표적인 기호
  • 터미널: 시작과 종료 표시
  • 처리: 처리 내용 기재
  • 판단: 적혀있는 조건에 따라 처리 분기
  • 반복: 루프(반복처리)의 시작과 끝을 기재
  • 정의된 처리: 다른 곳에서 정의된 처리(보조 프로그램)를 호출
  • 흐름선: 처리 흐름을 표시. 화살표를 사용해 처리 방향을 명확히 표시