재귀함수

이 글은 공부한 내용을 정리하는 목적으로 적는 글이오니 건전한 비판은 환영합니다.

 

먼저 함수에 대해서 이야기를 해보자면

1. 값을 입력받아 특정 연산을 수행하는 결과를 반환

예를 들면

public static void main(String[] args){

	System.out.println(getResult(3));

}

static int getResult(int n){

	return n*n;
}

위와 같이 어떤 값을 함수에 넣었을 때 그 값을 받아서 어떠한 로직을 처리한 다음에 리턴해주게 되어있다.

 

2. 함수간의 완변학 분담

예를 들면

public static void main(String[] args){

	System.out.println(getResult(3));결과 9
    System.out.println(result(3));//결과 0

}

static int getResult(int n){

	return n*n;
}

static int result(int n){
	return n-n;
}

이렇게 하면 서로 다른 함수에서 작동하기 때문에 서로 영향을 줄 수가 없다. 왜냐하면 서로 영향을 줄 수가 없기 때문이다.

 

3. 의미단위의 프로그래밍을 한다.

public static void main(String[] args){

	System.out.println(getResult(3));결과 6
    System.out.println(result(3));//결과 0

}

static int plusResult(int n){

	return n+n;
}

static int minusResult(int n){
	return n-n;
}

함수는 어떠한 동작을 하는지 명확하게 표현이 되여야 한다.

 

이렇듯이 순차적 계산법과 귀납적 계산법이 있다.

순차적 계산법의 예를 들면

public static void main(String[] args){

	System.out.println(getResult(3));결과 9
    System.out.println(result(3));//결과 0

}

static int getResult(int n){

	return n*n;
}

static int result(int n){
	return n-n;
}

이렇게 위와같이 getResult가 먼저 계산이 되는 것이고, 그 이후에는 result가 계산이 된다.

먼저 작성한 순서대로 계산이 이어진다. 이러한 것이 순차적 계산이다.

 

재귀함수란?

자기 자신을 부르는 함수를 재귀함수입니다. 즉 f(x)를 구하기 위해 f(x)를 사용합니다.

이게 무슨 이야기면

3!(팩토리얼)을 구할 때를 이야기 해보면, 

3*2*1 로 계산을 할 수 있습니다.

그러면 5(3)승은 5(2)*5로 계산을 할 수 있습니다.

그러면 5(2)승은 5(1)*5로 계산을 할 수 있으며, 5(1)은 5(0)*5입니다.

그러면 5(0)은 몇 일까요? 1입니다.

5(0)을 구했으니 5(1)승은 5이고요, 5(2)승은 25, 5(3)승은 125입니다.

이렇게 자기 자신을 구하기 위해 자신을 이용하는 것 입니다.

즉, 수만은 가정을 하다가 맨 끝에는 정확한 값이 있기 때문입니다.

그러면 재귀함수를 어떨 때 사용을 할까?

예를 들면 팩토리얼을 구하는 문제가 있다.

그렇다면 입력 받을 값이 n이면, 어떻게 구할 수 있을까?

n의 범위는 1~100이다. 어떻게 구할 수 있을까?

import java.util.Scanner;
public class Main{
    public static void main(String[] args){

       // Please Enter Your Code Here
       Scanner sc = new Scanner(System.in);
       int n = sc.nextInt();
       
       getResult(1,n,1);

    }
    
    private static void getResult(int start, int end, int mySum){
      if(start>end){
        System.out.println(mySum);
        return;
      }else{
        mySum*=start;
        getResult(start+1,end,mySum);
      }  
      
    }
}

start와 end를 정확하게 나누는 것이다. 예를 들면 n이 3이라고 가정하면, start가 3보다 넘을경우 끝내버린다.

이렇듯이 반복된 중첩문이 있을 때 재귀함수를 사용하는 것이다.

 

재귀함수 디자인

- 재귀함수 디자인을 위한 3가지 절차

1. 함수의 역할을 말로 정확하게 정의한다.

2. 기저조건(제일단순한경우)에서 함수가 제대로 동작함을 보인다

3. 함수가 제대로 동작한다고 가정하고 함수를 완성한다.