재귀 호출을 반복하는 함수에 대해 문의 드립니다.

Question

아래 코드 중에서

return min(walk(n - 2) +1,walk(n - 3) + 1)

여기서 왜 +1을 하는 것인지 설명 부탁드립니다.

또, 재귀 호출 문이 두번씩이나 이루어지기도 하는데 아래 코드가 해석이 가능하신 답변자분 찾습니다.

#include <stdio.h>

int min(int x, int y)

{

if (x < y)return x;

return y;

}

int walk(int n)

{

if (n == 0) return 0;

if (n < 0 || n == 1) return 9999999;

return min(walk(n - 2) +1,walk(n - 3) + 1);

}

int main()

{

int n = 16;

printf("%d\n", walk(n));

return 0;

}

Answer 1

#include <stdio.h>

int min(int x, int y)

{

if (x < y)return x;

return y;

}

int walk(int n)

{

if (n == 0) return 0;

if (n < 0 || n == 1) return 9999999;

return min(walk(n - 2) +1,walk(n - 3) + 1);

}

int main()

{

int n = 16;

printf("%d\n", walk(n));

return 0;

}

위 코드에서 +1을 하는 이유는 자기 자신을 호출 하기 위함입니다.

재귀호출을 하는중 자신을 빼고 min(x,y) 가 호출 되기 때문에

현재의 자신을 호출하기 위해 1을 더하게 됩니다.

Answer 2

안녕하세요.

재귀 알고리즘은 walk(n)은 n까지의 최소값을 얻는 호출입니다.

walk(n - 2)는 n - 2까지의 최소 값을 구하는 거고,

walk(n - 3)은 n - 3까지의 최소 값을 구하는 기능입니다.

그리고 현재 n에서 n - 2와 n - 3에 각각 +1이 추가로 더해져야 n까지의 최소 값을 구할 수 있습니다.

그래서 +1이 있어야 합니다.