[알고리즘] 재귀함수(recursion)란?

재귀 : 원래의 자리로 되돌아가거나 되돌아옴

 

재귀 함수 : 자기 자신을 호출하는 함수

 

장점 : 코드가 간결해지고, 수정이 용이해짐 (여러개의 반복문을 사용하지 X)

변수를 여러개 사용할 필요가 없음

 

단점 : 코드 흐름 직관적이지 X

반복문에 비해 메모리 사용 많음

 

재귀 함수 사용 위한 조건 : 문제의 단위를 잘게 쪼갤 수 있을 것, 재귀 호출 종료되는 시점이 존재할 것

---

재귀적 사고 방법

 

1. 재귀 함수의 입력값, 출력값 정의

어떤 요소를 입력받아 어떤 타입을 리턴하는지!

ex) [int] -> int 식으로 미리 적어놓음

 

2. 문제를 쪼개고 경우의 수 나누기

입력값이나 문제의 순서, 크기로 문제를 쪼개본다.

이때 구분된 문제를 푸는 방식이 순서, 크기에 관계없이 모두 같아야함!

 

ex) arrSum(new int[]{1,2,3,4}) 푸는 방법과 arrSum(new int[]{2,3,4}) 푸는 방법이 동일하도록

 

3. 단순한 문제 해결하기 

  = 재귀 탈출조건 구성하기

  = 재귀 호출이 멈추는 조건

 

4. 복잡한 문제 해결하기

 

5. 코드 구현하기 

*** 재귀 함수 템플릿 ***

public type recursive(input1, input2, ...) {
  // Base Case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
  // 예1. someValue + recursive(input1Changed, input2Changed, ...)
  // 예2. someValue * recursive(input1Changed, input2Changed, ...)
}

ex) 1부터 num까지의 합 구하기 

public class Solution { 
  public int sumTo(int num){
    //TODO..
    //더 이상 쪼갤 수 없는 경우
   if(num==0) return 0;

    //반복되는 (작은단위 쪼갤 수 있는)
    return num + sumTo(num-1);
  }
}

---

이때부터 ... 개념을 문제에 직접 적용시켜 코드로 구현하는게 어렵다는것이 확 체감되었다.

친절하고 인내심강한(!) 페어분을 만나서 잘 배웠는데

 

항상

1. 입력 인자와 출력 타입을 정의해두고, 
2. 문제를 작은 단위로 쪼개고, (재귀함수가 도는 부분)
3. 더 이상 쪼갤 수 없는 경우 = 탈출조건 을 구성

 

하는 방식으로 문제를 풀어나가시는걸 볼 수 있었다.

 

그리고 재귀 문제들에서는 문제를 쪼갤때

배열등을 head와 tail로 나누고, (0번째 index를 head, 나머지 배열을 tail)

copyofRange(원본길이, 복사할길이) 메서드를 써서 재귀함수를 구현시키는 경우가 많았다.

 

copyofRange - 원본 배열 값에 영향을 끼치지 않기 위해 배열을 잘라다가 복사해옴

 

오늘 공부해본 결과 dfs에도 사용되는 것 같으니 문제로 다시금 복습해야겠다,,어려버