재귀 함수 쉽게 이해하기 및 예시

재귀 함수의 구조

int f() {
  if (베이스 조건) {
  	return 베이스
  }
  else { // 베이스 조건이 아닐때,
    [재귀식 연산에 대한 고려]
    return 재귀식;
  }
}

 

재귀함수 쉽게 이해하는 방법

1. 특정 리턴값을, 함수식으로 표현해본다

2. 그리고, 거기서, 베이스 조건과 재귀식을 도출한다.

(예) 피보나치 배열의 수학적 함수식 표현

f(x) = (x > 2일 경우) f(x-2) + f(x-1) 

        (x <= 2일 경우) f(x) = 1

 

베이스 조건과 재귀식 도출하기

                 f(x) = (x > 2일 경우)    f(x-2) + f(x-1)  <--  재귀식

 베이스조건 --->   (x <= 2일 경우)  f(x) = 1    <----  베이스

 

3. 1과 2를 이해한 것을 바탕으로, 위의 재귀 함수의 구조에 따라, 구현한다.

 

 

예제. (JAVA) 피보나치 배열 구하기

	public static int fibonacci(int n) {
		// 재귀함수는 반드시 베이스 조건을 명시해야한다.
		// 입력값이 1이거나 2일때
	    if (n == 1 || n == 2) {
	    	// 재귀함수는 베이스 조건에 대한, 가장 기초가되는
	    	// 기초값(베이스)을 명시해야한다. 기초값은 여기서 1
	    	return 1;
	    }
	    else {
	    	// 재귀적으로 자기를 호출하여, n번째 피보나치 배열을 구한다.
	    	// 재귀함수는 반드시 재귀식을 갖는다.
	    	// 재귀식 f(n) = f(n-1) + f(n-2) (n!=1 이고, n!=2일때만)
	    	return fibonacci(n - 1) + fibonacci(n - 2);
	    }
	}
	public static void main(String[] args) throws IOException {
		System.out.println(fibonacci(10));
	}

 

결과화면

55

 

예시. (JAVA) 재귀함수로 문자열에서 특정 문자 변경하기.

import java.io.IOException;
import java.util.Scanner;

public class test {
	public static String replaceAll(String s, char from, char to) {
	    if (s.length() < 1) {
	        return s;
        }
	    else {
	        char first = (from == s.charAt(0)) ? to : s.charAt(0);
	        return first + replaceAll(s.substring(1), from, to);
	    }
	}

	public static void main(String[] args) throws IOException {
		System.out.println(replaceAll("apple",'a','b'));
	}
}

결과화면

baaple

 

 

예시. (JAVA) 특정 숫자 오름차순인지 확인하기

	public static boolean checkAsc(int num) {
		if (num < 0) num *= -1;
		if (num < 10) {
        	// 탈출 조건
			return true;
		}
		else {
			//앞 뒤 비교하고 넘기고
			return (((num / 10) % 10) <= (num % 10)) && checkAsc(num / 10);
		}
	}
	
	public static void main(String[] args) {
		System.out.println(checkAsc(12345));
		System.out.println(checkAsc(-12345));
		System.out.println(checkAsc(13579));
		System.out.println(checkAsc(-53579));
		System.out.println(checkAsc(13079));
	}

 

결과화면

true
true
true
false

false