한 걸음 한 걸음 알고리즘 (재 귀 와 스 택)

【 성명: 판권 소유, 전재 환영, 상업 용도 로 사용 하지 마 십시오. 연락처: feixiaoxixing @ 163. com]
    제 앞의 블 로 그 를 본 친구 들 은 함수 호출 은 주로 ebp 와 esp 의 스 택 상호작용 에 의 해 이 루어 진 다 는 것 을 잘 알 고 있 습 니 다.그러면 재 귀 는 가장 중요 한 특징 은 함수 가 스스로 자신 을 호출 하 는 것 이다.만약 한 함수 가 자신 자 체 를 호출 한다 면, 이 함 수 는 재 귀 함수 이다.
    우 리 는 일반 함수 의 호출 이 어떤 지 볼 수 있다.함수 A 가 함수 B 를 호출 하고 함수 B 가 함수 C 를 호출 하면 스 택 에 있 는 데 이 터 는 어떻게 저장 합 니까?

  A    ^
  B    |    (    )
  C    |

    재 귀 함수 라면 간단 한 재 귀 함 수 를 예 로 들 면:

int iterate(int value)
{
	if(value == 1)
		return 1;
	return value + iterate(value -1);
}

    다음은 우리 가 하나의 함 수 를 사용 하여 호출 을 진행 하여 어떤 상황 이 발생 할 지 봅 시다.

void process()
{
	int value = iterate(6);
}

    이때 메모리 스 택 이 어떤 지 볼 까요?

iterate(int 1) line 96
iterate(int 2) line 97 + 12 bytes
iterate(int 3) line 97 + 12 bytes
iterate(int 4) line 97 + 12 bytes
iterate(int 5) line 97 + 12 bytes
iterate(int 6) line 97 + 12 bytes
process() line 102 + 7 bytes
main() line 108
mainCRTStartup() line 206 + 25 bytes
KERNEL32! 7c817067()

    여러분 도 위의 코드 를 보 았 습 니 다. 재 귀 함수 와 일반적인 함수 도 별 차이 가 없습니다.자신 이 호출 한 자 체 를 제외 하고 그 는 일반적인 함수 이다.그럼 이 함 수 는 언제 까지 재 귀적 합 니까?이것 이 바로 재 귀 함수 의 관건 이다.우 리 는 iterate 함수 가 1 이 되면 멈 추 는 것 을 보 았 기 때문에 위의 스 택 은 (value = 1) 즉 return 입 니 다.그래서 재 귀 함수 의 가장 관건 적 인 부분 은 두 가지 입 니 다. (1) 재 귀 전략 입 니 다.(2) 함수 출구.
    이곳 을 보면 재 귀 함수 가 이 정도 에 불과 하 다 고 느 낄 수 있 지만 사실은 그렇다.하지만 한 가지 더 명심 해 야 할 것 이 있 습 니 다. 귀환 의 깊이 는 우리 가 반드시 고려 해 야 할 문제 입 니 다.재 귀 깊이 만 통제 가능 한 범위 내 에 있 으 면 전체 재 귀 과정 은 통제 가능 하 다.그럼 언제 컨트롤 이 안 돼 요?그것 이 바로 귀속 깊이 가 일정한 숫자 를 초과 한 것 입 니까?이 숫자 는 구체 적 인 스 레 드 스 택 길이 와 관계 가 있 습 니까?스 택 이 넘 치면 얻 은 데 이 터 는 진실성 을 잃 기 때문에 의미 가 없다.
    우 리 는 위의 문 제 를 보급 시 킵 시다. 어떻게 자신 이 정의 한 스 택 으로 위의 재 귀적 호출 을 모 의 합 니까?이렇게 하면 재 귀적 속성 을 만족 시 킬 수 있 을 뿐만 아니 라 함수 의 깊이 를 조절 할 수 있 도록 확보 할 수 있다.
    여러분 은 먼저 자신의 방안 을 써 도 됩 니 다. 다음은 저 개인의 생각 일 뿐 입 니 다.

int iterate(int value)
{
	int count = 0;
	int number  =0;

	push(value);
	while(-1 != (number = pop()))
	{
		if(1 != number)
			push(number -1);
		count += number;
	}

	return count;
}

[예고: 다음 블 로그 소개 알고리즘 과 메모리]