[프로그래밍언어론] 22. 재귀(Recursion)

재귀(Recursion)

• 함수나 프로시저가 본문 내에서 자신을 호출하는 경우 이를 재귀적이라고 한다.
• 재귀는 튜링 완전성을 얻기 위한 또 다른 메커니즘이다.
• 재귀는 수학에서 흔히 나타나는데, 이를 귀납적 정의라고도 합니다.
  
  • n = 1일 때 : factorial(n) = 1 
    나머지 : n*factorial(n-1)

 

---

프로그래밍 언어에서 재귀

• 재귀는 반복에 비해 비효율적인 것으로 간주되는 경우가 많다.
• 계속해서 자신을 호출하기 때문이다.
• 호출할 때마다 새 활성화 레코드를 스택에 푸시하여 매개변수와 반환 값을 저장해야 한다.

int fact(int n) {
	if(n == 1)
		return 1;
	else
		return n*fact(n-1);
}

 

---

꼬리 재귀(Tail Recursion)

• 각 재귀 호출에 대한 활성화 기록을 공유하고 반환 값을 기다리지 않으면 더 효율적이다.
• 별도의 계산 없이 재귀 호출의 반환 값만 반환하는 tail recursion을 사용하면 가능하다.
• 중간 결과를 매개변수로 저장하기 위해 새로운 변수를 도입할 수 있다.

// Recursion

int fact(int n) {
	if(n == 1)
		return 1;
	else
		return n*fact(n-1);
}

// Tail Recursion

int fact(int n, int acc) {
	if(n == 1)
		return acc;
	else
		return fact(n-1, n*acc);
}

 

• 꼬리 재귀에는 추가 계산이 없으므로 각 재귀 호출은 동일한 활성화 레코드를 공유할 수 있다.
• 재귀 호출은 거의 동일한 코드이므로 활성화 레코드에 저장된 항목이 동일해야 한다.
• 각 재귀 호출의 값을 간단히 업데이트할 수 있다.