초보자를 위한 재귀 및 스택

여러분, 안녕하세요!

오늘의 주제는 재귀 프로세스와 스택에서 일어나는 일에 관한 것입니다.

재귀를 사용하여 주어진 숫자(x^y)의 거듭제곱을 반환하는 함수 __pow_recursion(float x, float y)를 고려합니다.

float __pow_recursion(float x, float y)
{   
    if (y == 0)
       return (1);
    if (y < 0)
        return (_pow_recursion(x, y + 1) / x);    
    return (_pow_recursion(x, y - 1) * x);
}

재귀함수는 중첩 함수로, 다른 함수를 호출한다는 의미입니다. 그러나 종료 조건(우리 경우의 if 문)에 도달할 때까지 여러 번 자신을 호출하는 것이 특별한 이유는 무엇입니까?

모든 코드를 이해하는 열쇠는 지침을 하나씩 따르는 것입니다. x = 5 및 y = 3을 취하여 __pow_recursion() 함수로 동일한 작업을 수행합니다.

이제 화살표를 따라가자



따라서 __pow_recursion(5, 3)은 [함수 __pow_recursion(5, 2) 배수 5의 반환]을 반환합니다.

그런 다음 프로그램은 함수 __pow_recursion(5,2)의 반환을 얻을 때까지 기다립니다. 즉, 프로그램은 다른 인수(x는 5, y는 2)를 사용하여 동일한 함수를 호출합니다.

그리고 다시 __pow_recursion(5, 2)는 [함수 __pow_recursion(5, 1) 배수 5의 반환]을 반환합니다.

또한 프로그램은 함수 __pow_recursion(5,1)의 반환을 얻을 때까지 기다릴 것입니다. 이제 프로그램은 다른 인수(x는 5, y는 1)로 동일한 함수를 다시 호출할 것이기 때문에 집중력을 잃지 마십시오.

우리는 재귀의 끝에 거의 도달했습니다!
__pow_recursion(5, 1)은 [함수 __pow_recursion(5, 0) 배수 5의 반환]을 반환합니다.

float __pow_recursion(float x, float y) /*__pow_recursion(5, 0)*/
{   
    if (y == 0) /*true*/
       return (1); /*our return is 1*/
    if (y < 0)
        return (_pow_recursion(x, y + 1) / x);
    return (_pow_recursion(x, y - 1) * x);
}

따라서 함수(5, 0)의 반환 값은 1입니다.

더 이상 함수를 호출할 필요가 없습니다! 재귀가 완료되었습니다! 하지만!
우리 기능으로 돌아가자, 그들은 기다리고 있다! 그리고 필요한 반환을 하나씩 제공하십시오!
__pow_recursion(5, 1)은 1 * 5 = 5를 반환합니다.
__pow_recursion(5, 2)는 5 * 5 = 25를 반환합니다.
__pow_recursion(5, 3)은 25 * 5 = 125를 반환합니다.

그리고 실행이 완료되었습니다!

이제 스택에서 어떤 일이 발생합니까? 그리고 처음에는 무엇입니까?

첫째, 스택은 LIFO 속성을 가진 데이터 구조입니다. 즉, 마지막으로 보관된 데이터가 가장 먼저 사용/삭제됩니다.
둘째, 메모리의 일부는 데이터를 유지하기 위해 동일한 속성을 사용하기 때문에 해당 데이터 구조 '스택'의 이름을 사용했습니다!
그러나 어떤 데이터?
프로그램이 실행될 때 변수, 함수 호출, 텍스트 코드… 스택에 보관됩니다!
코드/함수 실행의 모든 ​​명령은 스택에 자리를 잡고 완료/완료되면 영원히 이동합니다. 데이터를 영원히 유지하는 힙인 다른 유형의 메모리와 달리! 이를 위해 관리해야 합니다.
재귀는 LIFO 속성에 스택을 사용하여 함수가 "호출자"함수를 기억하고 출력을 반환할 대상을 알도록 합니다!


즐겁게 읽고 새로운 것을 배웠기를 바랍니다!