[07] 순환 ( Recursion ) 이란?

Recursion ( 순환 ) 함수 : 자기 자신을 호출하는 함수. 재귀함수라고도 한다.

 

void function(){
  .....
  
  function(); // 이런식으로 !
  ......
  
}

public static void main(String [] args){
	function();  //  결과 : Hello ! 무한 반복 루프
}


void function(){
	System.out.println("Hello !");
    function();
}

 

재귀함수를 위처럼 아무 조건없이 짜면, 무한루프에 빠진다.

 

따라서 우리는 재귀함수가 무한 루프에 빠지지 않도록 조건을 지정해줘야함.

 

public static void main(String [] args){
	function(4);  //  결과 : Hello ! 4번
}


void function(int n){
	if(n==0) return; // 자기 자신을 호출하지 않고 그냥 return ;
    else{
      System.out.println("Hello !");
      function(n-1);
    }
}

 

이때 위에서 if(n==0) return  을 base case 라고 부른다.

base case : 재귀에 빠지지 않는 케이스

 

재귀함수 호출시, 재귀를 반복하다보면 결국에는 base case 로 수렴해야만 무한 루프에 빠지지 않는다.

 

 

문제1. 숫자 입력시 , 1~ 해당하는 숫자까지의 합을 재귀함수를 이용하여 구하라.

import java.util.Scanner;



public class no_1 {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int num = scanner.nextInt();
		
		System.out.println(sum(num));
		

	}
	
	public static int sum(int k) {
		
		if(k==0) return 0;
		else {
			return (k+sum(k-1));
		}
	}

}

 

문제2. 팩토리얼( factorial ) 을 재귀함수로 구현하라.

import java.util.Scanner;

public class no_2 {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int num = scanner.nextInt();
		System.out.println(factorial(num));
	}
	
	static int factorial(int k) {
		if(k==0) return 1;
		else {
			return (k*factorial(k-1));
		}
	}

}

 

문제3. 피보나치( fibonacci Number )

f(0) = 0

f(1) = 1

f(n) = f(n-1) + f(n-2) n>1

import java.util.Scanner;

public class no_3 {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int num = scanner.nextInt();
		System.out.println(fibo(num));
	}

	static int fibo(int k) {
		if(k==0) return 0;
		else if(k==1) return 1;
		else {
			return (fibo(k-1)+fibo(k-2));
		}
		
	}
}