알고리즘 공부에서 재귀에 대한 내용을 공부해보았습니다.

아래는 오늘 공부한 내용을 요약한 노트입니다.

용어 정리

• 재귀 호출 : 자기 자신을 호출합니다.

• 재귀 함수 : 자기 자신을 호출하는 함수힙니다.

요구 사항

문제의 크기가 점점 작아져야 하고, 재귀 호출의 종료에 대한 조건이 있어야 합니다.

예시

아래는 팩토리얼을 재귀함수로 구현했습니다.

int factorial(int i)
{
    if(n==0)
        return 1;
    else
        return n*factorial(n-1);
}

잘못된 재귀 호출

무한히 반복되는 재귀호출은 잘못된 것입니다.

함수 호출은 시스템 스택을 사용하기때문에 스택 오버플로우 오류 발생합니다.

피보나치 수열

int fibo(int i)
{
    if(n==1||n==2)
        return 1;
    else
        return fibo(n-1) + fibo(n-2);
}

피보나치 수열 역시 문제의 크기가 점점 작아지므로 재귀 호출로 사용할 수 있습니다.

트리

재귀 호출도 트리 다이어그램으로 나타낼 수 있습니다.

위 피보나치 수열에서는 fibo(n-1)와 fibo(n-2) 서로가 서브트리로 쪼개져서 트리 레벨이 높아진다.

그리고 마지막 레벨까지 도달한다면, 리턴값이 반환되면서 다시 최상위 루트 노드에 결과값이 나옵니다.

하노아의 탑

조건 : 세개의 기둥과 서로 다은 크기의 n개의 원반이고, 원반은 반드시 하나의 기둥에 있어야합니다.

자신보다 작은 원반 위에 그 원반을 올릴 수 없습니다.

알고리즘 순서

1. 첫번째 기둥에서 n-1개의 원반을 세번째 기둥을 이용해 두번째 기둥으로 옮깁니다.

2. 첫번째 기둥에서 1개의 원반을 세번째 기둥으로 옮깁니다.

3. 두번째 기둥에서 n-1개의 원반을 첫번째 기둥을 이용해 세번째 기둥으로 옮깁니다.

void hanoi(int i, int from,int by,int to)
{
    if(n==1)
        move(from, to);
    else
        hanoi(n-1,from,to,by);
        move(from,to);
        hanoi(n-1,by,from,to);
}

재귀호출이 하는 일

재귀 수열을 계산할 수 있으며, 반복되는 패턴의 그림을 그릴 수도 있습니다. 또한 깊이와 범위를 모르는 문제를 해결할 수 있습니다.

분할 정복 알고리즘 또한 구할 수 있습니다.