C# 문법 - 재귀함수

재귀함수란

특정 조건이 true가 될 때까지 자기 자신을 반복 호출하는 함수 입니다.

 

 

재귀함수의 구조

// 조건이 충족될 때까지 스스로를 호출
static int recursive (인자){
	
    // 종료 조건
    if(true){
    	return 결과;
    
    } 
    
    // 재귀 호출
    else{
    	return recursive(작업된 인자)
    }

}

 

 

 

재귀함수의 특징

• 자기 자신을 호출 : 조건이 true가 될때까지 자기 자신 호출합니다.
• 스택 메모리 사용 : 재귀함수는 호출될 때마다 스택에 새로운 프레임을 생성하며, 각 호출의 상태를 저장합니다. 이는 메모리를 더 많이 사용할 수 있으며, 스택 오버플로우(Stack OverFlow)를 발생 시킬 수 있습니다.
• 종료 조건 이 없으면 무한 반복됩니다

 

 

응용문제

 

하노이의 탑

피보나치 수열

 

 

 

꼬리 재귀 최적화 : 스택 메모리 사용의 단점을 보완하기 위해 나왔습니다. 재귀 함수를 컴퓨터가 재해석 해서 선형 알고리즘으로 만들어 실행시켜 주는 기능입니다. 따라서 사용하는 언어가 꼬리 재귀 최적화 기능을 지원하는지 확인하고 사용하는것이 좋습니다.

 

 

도움이 된 블로그

https://wania0.com/entry/C-%EC%9E%AC%EA%B7%80%ED%95%A8%EC%88%98

[C#] 재귀함수