[알고리즘] 재귀

코드스테이즈 41기 교육 내용을 정리하고 있습니다.
틀린 부분이 있으면 댓글로 알려주시면 감사하겠습니다

 

재귀는 사전적 의미로는 원래의 자리로 돌아온다는 뜻이 있습니다.

코딩에서는 함수에서 자기 자신을 호출하는 꼴로 많이 사용합니다.

 

가장 쉽게 이해 가능한 예시는 팩토리얼입니다.

팩토리얼은 자신을 포함한 이하의 자연수를 전부 곱하는 형태입니다

예를 들어 5 팩토리얼은 5*4*3*2*1입니다. ( 5! = 5*4*3*2*1 ) 

 

5!은 5*4!입니다.

4!은 4*3!입니다.

. . .

 

이렇게 팩토리얼이라는 함수가 있다면 자기 자신을 리턴에 호출하는 형태일 것입니다.

코드로 나타내 보면 다음과 같습니다.

function factorial(num){
    console.log(num)
    if(num===1){
        console.log("number1 return start")
        return 1
    }
    return num * factorial(num-1)
}

function factorial(num){ //num=5
    if(num===1){ //num=5, false
        return 1
    }
    return num * factorial(num-1){//num=4
            if(num===1){ //num=4, false
            return 1
        }
        return num * factorial(num-1){//num=3
            if(num===1){ //num=3, false
                return 1
            }
            return num * factorial(num-1){//num=2
                if(num===1){ //num=2, false
                    return 1
                }
                return num * factorial(num-1){//num=1
                    if(num===1){ //num=1, true
                        return 1	//return 1
                    }
                    return num * factorial(num-1) //X
                    }}
                    }
                }
            }
        }
    }
}