제 1-1강 Recursion의 개념과 기본 예제들

nahye·2021년 5월 1일
0

What is Recursion?

순환이란?



Recursion : 자기 자신을 호출하는 함수(재귀함수)

java식) 자기 자신을 호출하는 method

> void func(...)
	{
    		...
        	func(...);
        	...
   	 }

what will happen?
public class Code01 {
	public static void main(String [] args) {
    	func();
       }
public static void func() {
	System.out.println("Hello");
    func(); #자기자신을 다시 호출
    }
   }

무한루프에 빠짐

그럼 Recursion은 항상 무한루프에 빠질까?

public class Code02 {
	public static void main(String [] args){
    	int n =4;
        func(n);
    }
    
    public static void func(int k) {
    	if(k<=0)
        	return;
        else {
        	System.out.println("Hello");
            func(k-1);
        }
      }
    }

recursion이 항상 무한루프에 빠지는 것은 아님

return하면 control이 항상 자기 자신을 호출했던 다음 문장으로 넘어가는데 func(k-1)로 이동 func(0)가 호출되었다가 아무일도 일어나지 않고 종료되었으니까

이 다음 문장을 실행해야하는데 func(k-1) 다음엔 아무 문장이 없기 때문에 다시 호출된 함수 func(k-2)로 넘어가는데 역시 종료 되고 또 종료되어서

마지막으로 func(n)까지 return이 되어서 func(n)이 종료

적절한 구조를 가지고 있다면 무조건 recursion이라고 무한 루프에 빠지는 게 아니다.

무한루프에 빠지지 않으려면?

public class Code02 {
	public static void main(String [] args) {
    int n = 4; 
    func(n); 
    //Base case: 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야한다.
  }
  
    public static void func(int k) {
    	if(k<=0)
        	return;
        else {
        	System.out.println("Hello");
            func(k-1);
            // Recursive case: recursion을 반복하다보면 결국 base case로 수렴해야 한다.
        }
      }
    }

8분 53초

profile
Slow and steady wins the race

0개의 댓글