[알고리즘] 재귀(1) - 설명

재귀 알고리즘은 문제를 해결하는 과정에서 자기 자신을 사용하여 문제를 해결하는 것이다

예시로 1부터 n까지 합을 구하는 sum을 들어보겠다

Alg sum(n)

1. if (n=1)

return 1    

   else

return n + sum(n-1)

여기서 if(n=1)은 베이스케이스(base case)로 루프문을 나가기 위한 조건이 된다

else는 재귀케이스(recursive case)로 자기자신을 계속 호출한다

재귀 알고리즘 프로그램을 작성할때에 항상 베이스케이스(탈출조건)가 있어야하고, 재귀케이스는 베이스케이스를 향하는 방향으로 진행되어야 한다

예시에서는 n값이 1씩 감소하면서 베이스케이스n=1이라는 조건을 향하고 있다

출처

제목: 알고리즘 원리와 응용

저자: 국형준

출판사: 21세기사