재귀함수에 대한 생각

1. 재귀 함수는 while문과 같다.

2. 인간이 이해하기 쉽다고 한다.

 카더라 통신으로 들은 내용이지만 프로그래밍 언어를 배우는 당사자인 난... 재귀가 어렵다

 왜 재귀가 어렵다고  느껴졌을까? 코드가 어떻게 흘러가는지 상상하기가 힘들었다. 반복문의 경우 변수를 통해서 값이 어떻게 흘러가는지 보이기 때문에 상상하기가 수월했고 익숙했다. 하지만 재귀는...

 재귀 함수에 대해 익숙해지려면 함수형 프로그래밍 패러다임에서 살아봐야한다고 생각한다. 요즘 날 함수형 프로그래밍 패러다임 하나만 채용하여 사용하는 고급 언어를 쉽게 찾아볼 수 없기 때문에(C,C++,파이썬 등) LISP란 언어를 추천하고 싶지만, 다중 패러다임에서도 함수형 프로그래밍은 가능하니 일단 함수만 사용해보려고 노력해보자!!

 재귀를 쓰다보면 자연스럽게 이런 생각이 든다. 반환해주는 값이 변수처럼 이용된다. 무슨 말인가? 싶지만, 함수형 프로그래밍 개념에서는 변수나 상태를 갖지 않기 때문에 변수를 사용하지 못 한다. 그럼으로 우리가 자주 쓰는 변수를 반환하지 못하고, 이를 대신해서 Return으로 값만 내보내거나, 함수를 넣어준다.

 다시 적어보면 재귀 함수는 변수가 없다고 생각해보고, 반환하는 값으로 값이나 함수를 보내줘야한다. 재귀 함수니까 함수를 넣어줘야한다. 또한 함수에서 함수로 계속 진행되니까 이를 멈출 수 있도록, 함수의 파라미터 값으로 값을 감소하거나, 증가하여 if문을 통해 멈추도록 해야한다.

int func(int n){
    if( n == 0)
    	return 0;
    else
    	return n + func(n-1);
}

위 예제에서 n + fun(n-1) 같은 경우 꼬리 재귀 함수로 바꿀 수 있다.

 꼬리 재귀 함수로 변경하려면 현재 n +의 정보는 필수 정보임으로 우리가 가져가야 하는 정보이다. 그럼으로 함수의 매개변수에 저장하는 값을 데려가야한다.

int func(int n, int result){
	if( n == 0)
    	return 0;
    else
    	return func(n-1, result+n);
}

재귀함수

다음 글에서는 하노이의 탑으로 재귀함수를 설명해볼 생각이다.