达到基本情况时如何返回值

Question

我正在学习一些基本算法然后我遇到了欧几里德算法来找到两个数字的 GCD。

我在纸上理解了该算法。有一个迭代代码可以做同样的事情

int euclid_gcd(int a, int b){
    int dividend = a>=b ? a : b;
    int divisor = a<=b ? a : b;
    while(divisor!=0){
        int remainder = dividend % divisor;
        dividend = divisor;
        divisor = remainder;
        }
    return dividend; 
}

我对上面的迭代代码很满意然后还有两个相同代码的递归版本

int gcd(int a, int b){
    if(a==b) 
        return a;
    if(a>b) 
        return gcd(a-b,b);
    return gcd(a,b-a);
}

而且这是行数最小的一个]

int gcd(int a, int b){ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a);
}

根据我对递归的理解，在递归中，我们尝试使用已知的答案（基本情况）找到复杂问题（一般情况）的答案

随着递归调用的累积，我们基本上将解决更简单的问题，直到满足基本情况。基本情况 returns 一个值，并且由于该值被返回，所有堆叠子问题的答案开始冒泡到原始函数调用，最终我们得到了问题的答案。

我不明白上面的函数调用是如何使用 base case 返回的值的

这是我干运行以上代码的尝试（第三个）。函数调用是

gcd(20,8);

gcd(20,8) -> gcd(8,20) -> gcd(4,8) -> gcd(0,4)

现在我们通过函数调用达到基本情况 gcd(0,4)

返回4

现在上一个函数调用 gcd(4,8) 是如何使用 4

我们不是 'catching' 任何变量中的返回值，那么该值究竟发生了什么，最终答案（在本例中为 4）是如何冒泡并由原始函数调用返回的？

Answer 1

考虑这个例子：

int functionA() {
    return functionB();
}

这段代码会调用functionB，直接return将functionB的结果传递给functionA的调用者，而不对其进行操作。相当于这样写：

int functionA() {
    int toReturn = functionB();
    return toReturn;
}

正如您所说的那样，值 return 由函数 B "is not caught" 由 functionA 中明确定义的变量编辑。

也许递归让您感到困惑，但您的问题实际上与递归无关。它对任何函数调用都有效。

Answer 2

我认为你对递归的理解是正确和完整的。您只需要稍微了解一下 Call Stack 在函数调用中的作用。你可以在网上找到很多帖子来掌握这个概念。在这里，我将尝试为您简要定义 Call Stack 概念。

一个程序的内存被分成了多个段。其中最重要的两个是 Stack 和 Heap。这里我们将重点放在 Stack.

你调用的每个局部变量和每个函数都在那里。这是有关您的程序的相关信息所在的地方——调用了哪些函数、您创建了哪些变量以及更多信息。此内存也由程序而不是开发人员管理。堆栈是一个有序的插入位置。

堆栈是后进先出（Last-In-First-Out）数据结构。您可以将其视为一盒完美契合的书籍——您放置的最后一本书就是您取出的第一本书。通过使用这种结构，程序可以通过两个简单的操作轻松地管理它的所有操作和范围：push 和 pop。

为了跟踪当前内存位置，有一个特殊的处理器寄存器称为堆栈指针。每次你需要保存一些东西——比如一个变量或函数中的 return 地址——它都会向上推动和移动堆栈指针。每次退出函数时，它都会从堆栈指针弹出所有内容，直到函数保存的 return 地址。

我想你现在知道递归调用中会发生什么了。每个函数都有自己的变量存储在堆栈中。当一个函数到达它的 return 语句时，将结果压入堆栈，另一个调用该函数的函数将从堆栈中弹出结果。

现在你知道调用堆栈是如何工作的了。这是理解递归的关键概念。

达到基本情况时如何返回值

How are values returned back when the base case is reached

c++

recursion

greatest-common-divisor