Recursion (재귀)

https://www.youtube.com/watch?v=tuzf1yLPgRI&ab_channel=%EA%B6%8C%EC%98%A4%ED%9D%A0 

유튜브 권오흠님의 영상을 보고 공부했습니다.

 

 

- 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꿔라.

 

// 순차탐색 
int search(int data[], int n, int target)
{
	for(int i = 0; i < n; i++)
    {
    	if(data[i] == target)
        	return i;
            
         return -1;
    }
}

위의 search 함수는 일반적인 함수의 형태로, 0부터 n까지 배열을 탐색해서 내가 찾는값인 target의 인덱스를 찾는다.

이 함수에선 배열의 인덱스 0부터 n-1까지 탐색하는데, 검색 구간의 시작 인덱스 0은 보통 생략한다.

즉 0은 암시적 매개변수이다.

int search(int data[], int begin, int end, int target)
{
    // base case
    if(begin > end)
        return -1;

    else if(target == data[begin])
        return begin;

    else
        search(data, begin+1, end, target);
}

위의 함수는 재귀형태의 함수로, data[begin] 에서 data[end] 사이에서 target을 검색한다.

그런데 매개변수를 보면 begin과 end가 있다. 

이는 이전의 일반적인 함수 형태에서 암시적 매개변수인 0을 명시적 매개변수로 바꿔준 것이다.

 

즉 일반적인 함수에서 암시적 매개변수로 설정한 배열의 시작구간을 

재귀함수 형태에선 명시적으로 begin이라는 형태로 나타낸것이다. 

 

재귀함수에서 파라미터를 명시적으로 나타내 주는 이유는 암시적으로 나타냈을 경우 재귀 함수안에서 자기 자신을 호출할때 파라미터를나타낼 방법이 없어지기 때문.

---

- 재귀함수의 매개변수들은 외부에서 함수가 호출될때의 상황만 생각해서 매개변수를 설정해서는 안되고,

  자기자신이 자기자신을 호출할때 (재귀할때) 필요한 매개변수들까지 표현할수 있게 설정해야함.

 

---

int findMax(int data[], int begin, int end)
{
	// base case
    if(begin == end)
        return data[begin];

    // data 배열에서 최댓값을 찾는다는 것은
    // data[begin+1]에서 data[end]까지 중 최댓값을 찾은다음
    // 그 값과 data[begin]값과 비교해서 둘중에 더큰 값을 찾는것과 같다. 
    return max(data[begin], findMax(data, begin+1, end));
}

 

---