[JAVA] 재귀호출 / 비재귀 호출 / Stacking

문제: 사용자에게 정수 N을 입력받아 N!을 계산하는 연속적인 방정식을 기록하는 팩토리얼 프로그램을 만들어라. 예를 들면 입력이 4일 때 출력은 다음과 같을 수 있다.

Input)            N= 4

Output) 4!           = 4!
                         = 4 * 3!
                         = 4 * 3 * 2!
                         = 4 * 3 * 2 * 1!
                         = 4 * 3 * 2 * 1 * 0!
                         = 4 * 3 * 2 * 1 * 1

문제 해결 방법:

팩토리얼 문제를 해결하기 위한 방법으로는

                        1. 재귀 호출( Recursive )

                        2. 비재귀 호줄( Non-Recursive ) 반복문 사용

                        3. 스택을 사용( Stacking )

1. 재귀호출
소스코드( Recursive_Factorial.java )
import java.util.Scanner;

public class Recursive_Factorial
{              
            public String Res = new String();
               public int Factorial( int n )
               {
                              if( n < 0 )
                              {
                                             return 1;
                              }

                              Res = Res.substring( 0, Res.indexOf( "=" ) + 1 )
                                             + Res.substring( Res.indexOf( "=" ) + 1 ).replace( "!", " *" );

                              Res += " " + n + "!";

                              System.out.println( Res );

                              return n * Factorial( n - 1 );

               }

               public static void main( String[] args )
               {
                              Scanner sc = new Scanner( System.in );
                              Recursive_Factorial Recur = new Recursive_Factorial();
                              int N;

                              System.out.print( "Input a Interger : " );

                              N = sc.nextInt();

                              Recur.Res = "" + N + "! = ";

                              Recur.Factorial( N ); // 재귀 함수 호출

                              System.out.println( Recur.Res.replace( "* 0!", "* 1" ) );
               }
}


2. 비재귀 호출 ( 반복문 사용 )
소스코드( Non_Recursive_Factorial.java)

import java.util.Scanner;

public class Non_Recursive_Factorial
{
               public static void main( String[] args )
               {
                              int i, N;
                              String Res;
                              Scanner sc = new Scanner( System.in );

                              System.out.print( "Input a Integer : " );

                              N = sc.nextInt();

                              Res = "" + N + "! = ";

                              //반복문 for, while, do~while을 사용할 수 있다.
                              for( i = N; i >= 0; i-- )
                              {
                                             Res = Res.substring( 0, Res.indexOf( "=" ) + 1 ) + Res.substring( Res.indexOf( "=" ) + 1 ).replace( "!", " *" );
                                             Res += " " + i + "!";
                                             System.out.println( Res );
                              }
                              System.out.println( Res.replace( "* 0!", "* 1" ) );
               }
}

3. Stacking

import java.util.Scanner;

public class Stacking_Factorial
{
               private int Top, nStack[];
               public Stacking_Factorial()
               {
                              Top = -1;
                              nStack = new int[ 100 ];
               }

               public int pop()
               {
                              if ( Top < -1 )
                                             return -1;
                              return nStack[ Top-- ];
               }

               public void push( int n )
               {
                              if( Top >= 100 )
                              {
                                             System.out.println( "Stack is oveerflow" );
                              }

                              nStack[ ++Top ] = n;
               }

               public int top()
               {
                              if( Top == -1 )
                              {
                                             System.out.println( "Stack is underflow." );
                                             return -1;
                              }

                              return nStack[ Top ];
               }

               public boolean isEmpty()
               {
                              if( Top == -1 )
                                             return false;
                              else
                                             return true;
               }

               public static void main( String[] args )
               {
                              String Res;
                              int N, Temp;
                              
                              Stacking_Factorial stacking = new Stacking_Factorial();
                              Scanner sc = new Scanner( System.in );

                              System.out.print( "Input a Integer : " );
                              N = sc.nextInt();

                              stacking.push( N );

                              Res = "" + N + "! = ";

                              while( stacking.top() != -1 )
                              {

                                             Temp = stacking.pop();
               
                                             stacking.push( Temp );
                                             stacking.push( Temp -1 );

                                             Res = Res.substring( 0, Res.indexOf( "=" ) + 1 ) + Res.substring( Res.indexOf( "=" ) + 1 ).replace( "!", " *" );
                                             Res += " " + Temp + "!";
                                             
                                             System.out.println( Res );
                              }

                              System.out.println( Res.replace( "* 0!", "* 1" ) );

                              stacking.pop();
                              stacking.pop();

                              Temp = 1;
                              while( stacking.isEmpty() )
                              {
                                             if( !stacking.isEmpty())
                                                            break;
                                             Temp = stacking.pop();
                                             
                                             if( !stacking.isEmpty())
                                                            break;
                                             Temp *= stacking.pop();
                                             
                                             stacking.push( Temp );
                              }
                              
                              System.out.println( Temp );
               }
}


결과 화면

Click!!!

학교 과제가 나와서 한번

팩토리얼을 재귀호출 / 비재귀호출(반복문) / 스태킹으로 구현해 봤다.

출력하는게 조금 짜증 났는데..


간단하게 리플래이스 함수로 처리를 했는데..

뭐 재귀 호출 과정에서 저렇게 되어 버리니.. 느릴거라는게 예상된다..


리플레이스 함수를 안쓰게 미리 정리해서 하면 되겠지만.. 영 생각이 안나서.. 그냥..


내머리도 돌이 다 되어 가는 듯...