재귀 호출을 반복하는 함수에 대해 문의 드립니다.
아래 코드 중에서
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;
}
#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을 더하게 됩니다.
안녕하세요.
재귀 알고리즘은 walk(n)은 n까지의 최소값을 얻는 호출입니다.
walk(n - 2)는 n - 2까지의 최소 값을 구하는 거고,
walk(n - 3)은 n - 3까지의 최소 값을 구하는 기능입니다.
그리고 현재 n에서 n - 2와 n - 3에 각각 +1이 추가로 더해져야 n까지의 최소 값을 구할 수 있습니다.
그래서 +1이 있어야 합니다.
