점화식과 재귀함수

1. 점화식

수 열의 규칙성을 정의하는 것.

n번째 항(일반항)을 그 전 항들을 이용하여 표현한 식.

ex) 2의 배수를 나열한 수에서 n번째 항의 수는? => 2n

​ 피보나치 수열에서 n번째 항은? F1 = F2 = 1, Fn = F(n-2) + F(n-1)

*점화식을 통해 수열의 규칙성을 발견하고 메서드 내 함수식으로 활용할 수 있음.

2. 재귀함수(Recursion)

함수 내에 자기 자신을 다시 호출하여 작업을 수행하는 함수.(마치 인셉션!)

[구조]
(변환타입)  메서드(함수)이름(매개변수) {
	//종료조건
	if(  ) {
		return
	}
	...
	메서드(함수)이름(매개변수)
	=> 재귀로 자신을 호출하는 부분들. 여러번 호출할 수도 있으며, 
    앞 뒤로 여러 작업들도 같이 진행할 수 있음.
	...
}

// 종료조건이 재귀 부분이나 다른 곳에 있을수 있음. 즉, 어떻게 구현하느냐에 따라 달라질 수 있음.
// 중요한 것은, 반드시 재귀를 탈출하도록 끝나는 곳이 있어야 한다는 것.

• 재귀함수 예시코드

  // 피보나치 수열의 n번째 수
  static int fibo(int n) {
      if(n<3) {
          return 1;
      }
      return fibo(n-2) + fibo(n-1);
  }
  

  // 팩토리얼
  static int fact(int n) {
      if(n==1) {
          return 1;
      }
      return n*fact(n-1);
  }
  

  // 최대공약수 (유클리드 호제법)
  static int gcdInt;
  public static void gcd(int a, int b) {
      int tempInt = Math.max(a, b);
      b = Math.min(a, b);
      a = tempInt;
    
      if(b != 0) {
          gcd(b, a%b);
      } else {
          gcdInt = a;
      }
  }
  

1) 모든 재귀함수는 반복문으로 표현이 가능하다. (역도 성립)

Q. 1, 2, 4, 8, 16, ... 의 n번째 수 구하기
    // 1) 반복문
    static int timesFor(int n) {
        int result = 1;
        for (int i = 1; i < n; i++) {
            result *= 2;
        }
        return result;
    }
    // 2) 재귀함수
    static int timesRe(int n) {
        if(n==1) {
            return 1;
        }
        return 2 * timesRe(--n);
    }

	[추가공부]
	// n을 r제곱 하는 메서드 오버라이딩
    static int timesRe(int n, int r) {
        if(r==1) {
            return n;
        }
        return n * timesRe(n, --r);
    }

2) 재귀함수를 표현하기 위해 반드시 필요한 것.

• 종료 조건 (인셉션에 빠져나와야 함)

• 문제의 정의

• => 선언적인 프로그래밍 방법(디클래러티브)

  “선언적인 프로그래밍”은 목표를 명시하지만 알고리즘을 명시하지 않음.

  vs 명령적인 프로그래밍(임퍼래이티브)

  반면, “명령적인 프로그래밍”은 알고리즘을 명시하지만 목표를 명시하지 않음.

  *컬스텍. 즉, 호출의 흐름을 잘 이해해야 함. (인셉션에서 어느 스텍에 있는지 알아야 함)

  *컬스텍이 쌓이기 때문에 메모리 공간을 많이 차지하며 복잡도가 증가함.

3) 재귀함수를 코드로 구현할 때 신경써야 할 것.

1) 재귀함수를 탈출해서 나올 때, 나와서의 값을 어떻게 처리할 지.

public static String recursive(String s) {
        String answer = "";
        String tmp = "";
        int num = 0;
        while(idx<s.length()) {
            if(Character.isDigit(s.charAt(idx))) {
                num = Character.getNumericValue(s.charAt(idx));
                idx++;
            } else if(s.charAt(idx)=='{') {
                idx++;
                tmp = recursive(s); 
                // 이 부분에서 재귀 탈출을 하는데, 그 값을 사용하기 위해 tmp 변수로 받아줌.
                answer += tmp.repeat(num);
            } else if(s.charAt(idx)=='}') {
                idx++;
                break;
            } else {
                answer += s.charAt(idx);
                idx++;
            }
        }

        return answer;

2) 맴버 변수, 혹은 매개변수를 통해 재귀에 전체적으로 활용할 변수 설정

public class test {
        static int idx = 0; // 해당 재귀함수에서는 맴버변수를 사용하여 인덱싱을 유지함.
    					  // depth를 +1씩 하여 매개변수로 다음 재귀에 전달해주는 방법도 있음.
    public static String solution(String code) {
        return recursive(code);
    }

    public static String recursive(String s) {
        String answer = "";
        String tmp = "";
        int num = 0;
        while(idx<s.length()) {
            if(Character.isDigit(s.charAt(idx))) {
                num = Character.getNumericValue(s.charAt(idx));
                idx++;
            } else if(s.charAt(idx)=='{') {
                idx++;
                tmp = recursive(s);
                answer += tmp.repeat(num);
            } else if(s.charAt(idx)=='}') {
                idx++;
                break;
            } else {
                answer += s.charAt(idx);
                idx++;
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        System.out.println(solution("5{he2{l}o}friends"));

    }
}

4) 재귀함수를 사용하는 이유.

• 코드 이해를 용이하게 하기 위해
• 유지보수를 용이하게 하기 위해

*재귀함수의 대명사, ‘하노이의 탑’

---

마지막 수정일시: 2022-08-25 15:20