ch7. programming with Recursion (재귀)
(개인적으로 재귀가 한 번 일어날 때마다 트리에서 자식 노드가 하나 추가된다고 생각하니까 이해가 편함- 부모에서 재귀가 발생하면 자식의 리턴값(혹은 cout되는 구문)이 코드 상에서 그 재귀부분을 대체하게 되는 거임)
(일단 재귀 호출이 되면 자식 노드부터 냅다 그리고→ 일단 가지를 친 후 생각하자! base case까지 가서!!!!!!!!!! 다시 거슬러 오는 거임)
!!!!!!!!!!base case가 될 때까지 일단 가지침
! 따라서 일단 (tree 문제의 경우) 자식 등으로 이동만! 하고 싶다면 그냥 tree→next를 파라미터로 넣어서 호출만 시킴(따로 리턴값이 없으면 그냥 이동만 하고 아무것도 부모노드에게 가져오지 않으므로)
레퍼런스 쓰는 이유
즉, 그냥 단순히 자식노드에서 종료되어 리턴값만 필요하면(EX. 피보나치 수열의 결괏값) 그냥 굳이 레퍼런스로 파라미터를 안 해줘도 되는데, 자식 노드에서 변화된 값(EX. 객체에서 이름 바뀜)을 부모노드에서도 활용해야 하면 레퍼런스로 활용해준다.
- Direct recursion: method directly calls itself , 가장 일반적인 형태. 자기가 자기 내부에서 자신을 호출함
- Indirect recursion: 체인 형태를 통해 다시 처음의(자기)를 호출함 ex)A→B→C→A
- 재귀호출은 반복문(iterative solutions)보다 효율적이지 않다 →함수호출에 대한 오버헤드 때문에
- Base case: 더 이상 재귀적이지 않게 되는 것-해답을 알고 있는 경우( 종료 조건)
- General case: 더 작은 버전의 자기 자신을 해결책으로 제시하는 것( 일반적인 재귀 경우)
- Rercusive alrogithm is expressed in terms of smaller instances of itself and a base case
- 재귀 호출은 호출된 함수가 호출하는 함수와 동일한 함수 호출
- 다시 말하면 자기 자신을 호출하면 재귀호출이 되는 것임.
- We must avoid making an infinite sequence of function calls (infinite calls) →무한 호출을 반드시 피해야 한다
1.재귀가 종료되는 조건(base case)가 반드시 필요함
2.call by value로 recursive function을 하면 안됨
→ 웬만하면 파라미터들을 참조변수들로 넘겨줌.
일단 그래야 낭비가 덜하고, 어쨌든 “함수”를 호출하는거니까 지역변수화 되는 것을 막을 수 있음
→ 즉, 그냥 단순히 자식노드에서 종료되어 리턴값만 필요하면(EX. 피보나치 수열의 결괏값) 그냥 굳이 레퍼런스로 파라미터를 안 해줘도 되는데, 자식 노드에서 변화된 값(EX. 객체에서 이름 바뀜)을 부모노드에서도 활용해야 하면 레퍼런스로 활용해준다.
( 내가 이해한 것처럼 트리형태라고 생각하면 자식에서 부모로 거슬러 올라가는 건데, 갱신된 내용이 자식 노드에서만 해당되게 되면 안 되므로)
base case가 될 때까지 일단 가지침
- 각각의 재귀호출은 점점 정답이 나오는(알려진) 상황에 점점 다가가야 한다.
- a case for which the answer is known is called a base case
- Each recursive algorithm must have at least one base case, as well as the general(recursive) case
int Factorial(int number){
if(number == 0) //base case - 답을 알고 있는 경우(정해진 경우)
return 1;
else //general case
return number*Factorial(number-1); //즉 재귀가 발생하면 트리 형태처럼
//자식 노드 형태로 하나가 붙고,
//그 자식의 리턴값이 부모 노드 코드에서 재귀호출부분으로 들어오게 되는 거임
}//재귀호출 2번이상 되는 경우
int Combinations(int n, int k){
if(k==1){ //base case1
return n;
}else if(n==k){ //base case 2 (답을 알고 있는 또 다른 경우)
return 1;
}else{
return Combinations(n-1,k)+Combinations(n-1,k-1);//이렇게 재귀 호출이 2번 된다는 거임
//이러면 트리 형태로 생각했을 때 자식 노드가 2개 생김
}- Three-questions method of verifying recursive functions
- Base-case questions: 함수를 탈출할 있는 비재귀적인 경우가 있는가?
- Smaller-Caller Questions: 각각의 재귀 함수 호출이 원래의 문제상황보다 basecase에 가까이 다가가는가?
- General-Case Question: 각 재귀호출이 제대로 동작하는가?각 재귀 호출이 올바르게 작동한다고 가정하면 전체 함수가 올바르게 작동하는가?(최적의 원칙을 만족하는가?)
📌 **recursive가 이해는 더 쉬워도, function call overhead때문에 반복문이 더 효율적이다** 하지만 특정 문제에 대해서, recursive해법이 가장 **자연스러운** 방법이면 recursive를 사용한다. (ex) RevPrint(listData); +)Why use recursion? However, for certain problems the recursive solution is the most natural solution. This often occurs when pointer variables are used.
//반복문보다 재귀가 더 자연스러운 경우- recPrint
//이거를 반복문으로 반복하려면 각 노드까지 for문을 통해 가서 print하는 과정을
//각 노드에 대해 일일히 반복해야 하지만, 재귀호출은 그럴 필요 없음.
void RevPrint(NodeType* listPtr){
if(listPtr!=NULL){
RevPrint(listPtr->next); //base case가 될 때까지 일단 가지침(일단 자식 노드 생성)
cout<<listPtr->info<<endl;
}
//general case: 만약 listPtr이 null이면 do nothing.- It is necessary that there be a return to the correct place in the calling block after the function code is executed.(즉 자식 재귀노드의 리턴값은 부모 노드 코드에서의 재귀호출 부분으로 대체할 수 있게 된다)
- This correct place is called the return address.
- 함수 호출은 run-time stack에 쓰인다. 그리고 이 스택은 activation record(stack frame)에 위치한다.
- activation record가 저장하는 것: return address,parameters,local variables,return value
- 특정 함수 호출에 대한 활성화 레코드는 함수 코드의 마지막 닫는 중괄호에 도달하거나 함수 코드에서 반환 문에 도달할 때 런타임 스택에서 빠져나온다.
- 이 때,(호출된 자식 재귀함수 노드가 종료되면) 함수의 return value(혹은 출력되는 구문)이 부모노드의 코드에서 호출되는 부분을 대체하게 된다.
- 보통 종료조건(base case)를 잘못 잡아서 재귀를 너무 많이 해버리면 stack overflow가 발생하게 된다.
Tail recursion
- 개념: 부모 함수노드가 단 하나의 재귀 호출을 가지고, 부모 함수노드 코드의 마지막에서 재귀 호출을 하는 것
Recursion vs Iteration
- 반복문은 recursion을 대체할 수 있다!
- iterative algorithm은 looping contruct
- recursive algorithm은 branching sturcture임(위에서 내가 계속 언급했던, 재귀를 한 번 하면 자식 노드가 추가됨)
- Recursive solutions are often less efficient, in terms of both time and space,than iterative solutions.
- Recursion can simplify the solution if a problem,often resulting in shorter,more easily understood source code.
언제 recusive를 써야 하는가?
- 문제의 크기에 비해서 recursive depth가 상대적으로 얕을 때(”shallow”일 때)-자식 노드를 많이 추가하지 않아도 될 때
- recursive version이 아닌 것과 같은 양의 양을 할 때(효율이 비슷할 때)
- recursive version이 아닌 것보다 더 짧고 간단할 때
- SHALLOW DEPTH 2.EFFICIENCY 3.CLARITY
