재귀( Recursion )

func 함수를 만들어보자!

스터디를 본격적으로 시작하기전에, 잠시 5분정도 인풋값 n 부터 1까지를 출력하는 재귀함수를 만들어보자💥

정답 (모범답안)

void func1(int n){
  if(n == 0){
    return;
  }
  cout << n << ' ';
  func(n-1);
}

---

절차지향적 사고 vs 귀납적 사고

인풋 n 이 주어졌을때 n, n-1, ... , 3 2 1 이 어떻게 출력될 수 있는지를 증명해보시오. 즉, 함수 func(n) 이 n 부터 1 까지를 출력하는 함수임을 증명하시오.

1. 절차지향적 사고

n을 출력 - func(n-1) 을 호출 - n-1을 출력 - ... - func(1) 호출 - 1을 출력 - func(0) 호출 - 재귀종료

2. 귀납적 사고

위 함수 func 를 귀납적인 사고로 생각해보자. 아래와 같은 귀납적 표현을 통해 증명할 수 있어야한다.

1. func(1) 이 1을 출력한다.
2. func(k) 가 k, k-1, k-2, ... , 1 을 출력하면,
   func(k+1) 은 k+1 k, k-1, ... , 1 을 출력할 것이다.

• 증명 : func(k+1) 이 호출될때 k+1 이 출력되고 func(k) 가 호출되는데, func(k) 는 k, k-1, k-2, ... , 1 을 출력한다고 가정했으므로 func(k+1) 은 k+1, k, ... , 2, 1 까지를 출력함을 알 수 있다.

---

재귀(recursion) 유형 접근법

1. base condition 설정
2. 일정한 패턴을 찾아내서 재귀식을 만고, 함수를 정의하자.

---

재귀에 대한 스킬

1. base condition

• 모든 입력은 base condition 으로 수렴해야 한다.
  • 만일 func 함수가 n == 0 으로 수렴안했다면 무한루프 돌았을거임!

2. 메모리와 시간

• 재귀 코드를 짜는것은 가급적 지양하자.
• 몰론 재귀없이 구현하면 코드가 너무 복잡해지는 일부 문제들은 재귀로 구현하는게 좋다!

3. 중복되는 재귀호출을 여러번 호출한다?

ex) 피보나치 함수

4. stack memory limitation

• 메모리 제한을 보고(ex. 512MB) 재귀로 풀지 다른 방법을 선택할지 결정해야 한다.
• SW Expert ACADEMY 의 메모리 제한 : 메모리 제한이 너무 적다.

5. stack frame 의 구성성분

• 각 stack frame 에는 지역변수도 들어간다.
• stack frame : Stack + Heap + Data + Code + ...

• 런타임에러 가 뜬다면 2가지로 의심해볼 수 있다.
  • 1. 너무 깊은 재귀호출
  • 2. 너무 큰 배열 ex. int arr[4000][4000]

---

이번주 실습문제

BOJ 1629번 : 곱셈
https://www.acmicpc.net/problem/1629