[자바기초.021] 재귀 함수 실행(Tracing Recursive Methods)

[자바기초.021] 재귀 함수 실행(Tracing Recursive Methods)

 

[1] Tracing Recursive Methods

• 자바에서는 call stack이라는 것이 실행된 메소드들을 추적합니다.
• 스택(stack)이라는 것이 무엇인지 알아야 재귀함수(Recursive method) 실행과정을 이해할 수 있습니다.

 

[2] 스택(stack)

(출처: https://www.programiz.com/dsa/stack)

• 스택은 LIFO(Last In First Out) 원칙을 따르는 선형 데이터 구조입니다.
• 이는 스택 내부에 삽입된 마지막 요소가 먼저 제거됨을 의미합니다.
• 자바에서는 위와 같은 stack구조로 메소드가 저장되고 실행되는 것을 call stack 이라고 부릅니다.

위 그림에서는 다음을 수행할 수 있습니다.

1.stack안에 새 데이터를 넣기
2.상단 데이터 제거하기
3.하단에 있는 데이터를 원할 경우 먼저 상단에 있는 데이터를 모두 빼내야 합니다.
=> 이것이 바로 스택(stack) 데이터 구조가 작동하는 방식입니다.

 

[참고]
C, C++, Java, Python 또는 C#과 같은 프로그래밍 언어로 스택을 구현할 수 있지만 사양은 거의 동일합니다.

 

 

 

[예제1] 아래의 factorial 코드를 보면서 메소드가 stack 구조를 이루며 실행되는 과정을 이해해보자. 

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

• int n = factorial(0)을 실행하면, return 1이 실행되어, 변수 n = 1 이 된다.
• int n = factorial(1)을 실행하면, (1) return 1 * factorial(0)이 실행되고, (2) factorial(0)은 0 이므로, (3) 결과적으로 변수 n = 1 * 1, 즉,  n = 1이 된다.

 

 

[유제1] 아래 코드에서 fatorial(6)의 실행 결과 값은?

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

 

 

[유제2] 아래 코드에서 mystery(5)의 실행 결과 값은?

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

 

 

[유제3] 아래 코드에서 mystery(4,3)의 실행 결과 값은?

public static int mystery(int n, int a)
{
    if (n == 1)
    {
        return a;
    }
    return a * mystery(n-1,a);
}

 

 

[유제4] 아래 코드에서 bunnyEars(5)의 실행 결과 값은?

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

 

[유제5] 아래 코드에서 mystery(1234)의 실행 결과 값은?

public static void mystery (int x) {
   System.out.print(x % 10);
 
   if ((x / 10) != 0)
   {
      mystery(x / 10);
   }
   System.out.print(x % 10);
}

 

 

[유제6] 아래 코드에서 mystery("xyzxyxy")의 실행 결과 값은?

public static int mystery(String str)
{
   if (str.length() == 1)
   {
       return 0;
   }
   else
   {
      if (str.substring(0,1).equals("y"))
      {
          return 1 + mystery(str.substring(1));
      }
      else
      {
          return mystery(str.substring(1));
      }
   }
}

 

 

*substring 메소드 참고 사항

substring() 메소드는 다음과 같이 2가지 형태로 사용할 수 있습니다.

• public String substring(int startIndex): startIndex부터 끝까지의 문자열을 리턴합니다.
• public String substring(int startIndex, int endIndex)

substring(int startIndex) 예제 코드

String str = "Hello";         
System.out.println(str.substring(2)); // "llo"            
System.out.println(str.substring(5)); // "" 문자열의 마지막 index + 1 값을 startIndex로 지정하면, 빈 문자열을 리턴합니다.
System.out.println(str.substring(-1)); // StringIndexOutOfBoundsException
System.out.println(str.substring(6)); // StringIndexOutOfBoundsExceptio

 

substring(int startIndex, int endIndex) 예제 코드

String str = "Hello";
System.out.println(str.substring(2, 4)); // "ll"
System.out.println(str.substring(2, str.length())); // "llo"

 

 

 

 

---

 

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

[유제1 정답]

720

 

 

[유제2 정답]

32

 

[유제3 정답]

81

 

[유제4 정답]

10

 

[유제5 정답]

43211234

 

[유제6 정답]

 2

 (This method seems to be counting the number of y's in the string, but fails to check if a single character is a y) 

=> 정확한 값이 나오려면 아래와 같이 str.length() == 0 이 되어야 함.

if (str.length() == 0) {
         return 0;
}