[자바기초.020] 재귀(Recursion)

[자바기초.020] 재귀(Recursion)

 

[1] 재귀(Recursion) 이란?

• 재귀는 "원래 자리로 되돌아 온다"라는 뜻이다.(두 "재": 재차, 두 번, 다시 한번 / 돌아갈 "귀": 돌아가다)
• 자바에서는 "재귀함수(Recursive method)"라는 말로 사용되고, 함수 자기 자신을 다시 실행시키는 형태를 말한다.

 

[예제1] 재귀 함수의 아래 예시 코드를 보자.

 

public static void neverEnd()
{
  System.out.println("This is the method that never ends!");
  neverEnd();
}

 

• 위 코드에서 재귀함수를 실행하는 부분(함수 자신을 다시 call 하는 부분)은 몇 번째 줄이가요? => ( 4 번째 줄)
• 위의 코드는 글자를 출력하고 다시 자기 자신을 계속 호출(실행)하는 함수이다. 그래서 이 함수는 무한 재귀(infinite recursion)으로서 실행에 끝이 없다. 따라서 이런 함수는 컴퓨터에 무리가 발생하므로 좋지 못한 코드이다.

[APCSA 시험 참고]
-AP CSA 시험에서는 약 4-6 recursion 관련 문제가 나온다.
-AP CSA 시험에서는 재귀 함수의 실행 과정과 출력 결과를 계산할 줄 알면 된다.
-AP CSA 시험에서는 재귀 함수를 코딩하라는 것은 나오지 않는다.

 

 

[유제1-1] 아래 코드는 재귀함수(Recursive method) 인가요? (Yes/No)

public static int mystery()
{
   int total = 0;
   for (int i=10; i>0; i--)
   {
      total = total + i;
   }
   return total;
}

 

[유제1-2] 아래 메소드는 재귀(Recursive)인가요?

public static int mystery2(int x)
{
   if (x == 1) return 1;
   else return x + mystery2(x-1);
}

 

 

[2] 재귀(ecursive)를 사용하는 이유는?

• 재귀함수(Recursive method)는 뭔가 반복되는 구조일 때 사용하면 편합니다.
• 예를 들어, 수학에서 Factorial 공식을 반복문(for, while) 보다는 재귀를 사용하면 더 짧은 코드로 만들 수 있습니다.

 

[예제2] 아래의 Factorial 메소드를 살펴보면서 재귀 함수의 편리성을 이해해 보자. 

public static int factorial(int n)
{
    if (n == 0)
        return 1;
    else
        return n * factorial(n-1);
}

 

 

[유제2-1] 위 Factorial 코드에서, 몇 번째 줄이 재귀(Recursive)를 하는 부분입니까? => ( 6 번째 줄)

 

 

[유제2-2] 아래 코드를 실행해 보세요. 그리고 fatorial of 6, factorial of 1 값이 출력되게 코딩을 추가해 보세요.

public class Main {
  public static int factorial(int n) {
      if (n == 0) return 1;
      else return n * factorial(n - 1);
  }
  
  public static void main(String[] args) {
    System.out.println("3!=" + factorial(3));
    System.out.println("4!=" + factorial(4));
    System.out.println("5!=" + factorial(5));
    // add 6!
    // add 1!
  }
}

 

 

[3] Base case

• Base case: The part of a recursive definition or algorithm that is not defined in terms of itself.
• Base case는 재귀 함수가 더 이상 자기 자신을 호출하지 않고 재귀를 멈추는 경우(case)를 말한다.
• 모든 재귀 함수는 적어도 하나의 base case를 가진다.
• base case는 보통 if 조건문으로 실행되어 재귀가 무한반복되지 않고 끝나게 한다.
• factorial method는 변수 n == 0 인 경우 1을 리턴하며 재귀를 하지 않는데, 이 경우가 바로 factorial method의 base case이다.

[요약]
The thing that stops a recursive method from calling itself is called the base case. A method can have more than one base case (way to stop the recursion).

 

[예제3] 아래 코드에서 base case를 실행하기 위해 조건을 검사하는 부분은 몇 번째 줄인가요? => ( 2 번째 줄)

public static int factorial(int n) {
      if (n == 0) return 1;
      else return n * factorial(n - 1);
}

 

 

[유제3-1] 아래의 재귀함수가 자기 자신 호출하는 것을 멈출 때 변수 n의 값은? (What is the value of n when this method stops calling itself (when it reaches the base case)?)

public static int product(int n) {
   if(n == 1)
      return 1;
   else
      return n * product(n - 2);
}

 

 

[유제3-2] 아래 코드가 base case에 도달하는 경우에 변수 bunnies의 값으로 맞는것은?

(What is/are the values of the variable bunnies when this method stops calling itself (when it reaches the base case)?)

 

 

public static int bunnyEars(int bunnies) 
{
   if (bunnies == 0) return 0;
   else if (bunnies == 1) return 2;
   else return 2 + bunnyEars(bunnies - 1);
}

 

 

[유제3-3] 아래의 메소드는 재귀함수(Recursive method)입니까? (Yes/No)

public static int bunnyEars(int bunnies)
{
   int total = 0;
   for (int i = 0; i < bunnies; i++)
   {
      total = total + 2;
   }
   return total;
}

 

 

---

 

[유제 정답은 아래의 "더보기" 클릭]

[유제1-1 정답]

No. (함수 자신을 호출하지 않기 때문에 재귀함수가 아니고, 단순 반복문이다.)

 

 

[유제1-2 정답]

Yes. (any method that contains at least one call to the same method is recursive)

 

 

[유제2-1 정답]

6 번째 줄

 

 

[유제2-2 정답]

public class Main {
  public static int factorial(int n) {
      if (n == 0) return 1;
      else return n * factorial(n - 1);
  }
  
  public static void main(String[] args) {
    System.out.println("3!=" + factorial(3));
    System.out.println("4!=" + factorial(4));
    System.out.println("5!=" + factorial(5));
    System.out.println("6!=" + factorial(6));
    System.out.println("1!=" + factorial(1));
  }
}

 

 

[유제3-1 정답]

1    (This method stops calling itself when n equals 1 (line 3))

 

 

[유제3-2 정답]

C.  (This method stops calling itself when bunnies is either 0 or 1)

 

 

[유제3-3 정답]

No.    (There is no call to the same method, so it is not recursive. This uses iteration instead)

 

 

---