자료구조 정리하기: 재귀 호출(1)

CHAPTER03: 재귀 호출

3.1 재귀 호출의 개념

☆재귀 호출(recursion): a function is called by itself while running(함수가 실행 중에 자기 자신을 다시 호출하는 상황)

 

3.2 팩토리얼(factorial)

☆팩토리얼 계산 알고리즘 구현: 반복문 or 재귀 호출

☆종결 조건(exit condition): 재귀 호출에 반드시 포함되어야 한다. 잘못 설정할 경우 프로그램은 무한 반복에 빠진다.

 

재귀 호출문

n = 0이면 n! = 1

n >= 1이면 n! = n x (n - 1)!

factorial by recursion

반복문 구현

<for문>

factorial 함수::

for문에서 i = 1부터 N까지 fac에 i를 곱해서 fac에 저장(fac = fac * I;)해서 fac를 return

 

main 함수::

factorial() 함수 호출, 결과 출력

 

factorial by for loop

실행결과

N도 입력받아서 입력한 n의 팩토리얼을 구해서 출력하는 프로그램을 만들었다.

 

<while문>

while문은 더 간단하다.

factorial() 함수::

조건식으로 i <= N인 동안에, fac*=i; 연산을 수행하고 i++;로 i를 증가시키면 된다.

그리고 똑같이 fac를 return한다.

 

main() 함수::

for문의 코드 그대로 사용했다.

 

 

3.3 최대 공약수(GCD: Greatest Common Divisor)

<재귀 호출>

gcd(x, y) = gcd(y, x % y) if y > 0

gcd(x, 0) = x

 

y = 0이면 x를 최대 최대 공약수로 반환하여 종료한다.

y != 0이면 x % y를 인자로 사용해 다시 gcd 함수를 호출한다.

 

<for문>

main 함수::

gcd 함수를 호출한다. gcd 함수의 리턴값을 출력한다. 리턴값은 최대공약수이므로, 최대공약수가 출력된다.

 

gcd 함수::
인덱스 i = 1부터 x, y까지 증가하는 동안, x와 y로 나눴을 때 나머지가 0인 수를 g에 저장한다.

for문을 돌 때마다 g에 저장되는 i가 변하므로, 결과적으로 g에는 최대공약수가 저장되게 된다.

 

실행결과