c - 计算C中两个数字的GCD

Question

计算两个数的 GCD 的程序。

#include<stdio.h>
#include<conio.h>

int findgcd(int x,int y)
{
 while(x!=y)
 {
  if(x>y)
  {
   return findgcd(x-y,y);
  }
  else
  {
   return findgcd(x,y-x);
  }
 }
 return x;
}

void main()
{
 int n1,n2,gcd;
 clrscr();
 printf("\n GCD Calculator [ Please Enter Positive Integer number. ]\n");
 printf("\nEnter 1st numbers: ");
 scanf("%d",&n1);
 printf("\nEnter 2nd numbers: ");
 scanf("%d",&n2);
 if(n1>0 && n2>0)
 {
  gcd=findgcd(n1,n2);
  printf("\nGCD of %d and %d is: %d ",n1,n2,gcd);
 }
 else
 {
  printf("\n Sorry, Wrong Input.");
 }
 getch();
}

是否有另一种方法可以在 C 中使用递归计算两个数字的 GCD。

或者，如果没有递归，我怎么能以简单的方式编写这个程序？

score 2 · Accepted Answer

返回机制在这个程序中工作得非常正常。要了解多个 return 语句如何从函数解析为单个返回点，您需要了解如何while和if...else工作。

我建议你试着把这两个想法分开

函数的单个实例的执行。
函数调用自身的递归性质。

该声明

return anyfunc();

在代码路径中遇到时是单个返回点。它调用另一个函数，然后返回该函数返回的任何内容。由于if ... else ...只执行两个从属语句之一，因此只会调用两个返回之一。最后一个捕获循环的初始条件为假的情况，因此从未进入循环。

递归问题是一个不同的蠕虫罐头，但你需要清楚以上内容，否则递归会让你陷入绝望的困惑。:(

score 0 · Accepted Answer

也许更清楚一点：

int findgcd(int x,int y)
{
 if(x!=y)
 {
  if(x>y)
  {
   return findgcd(x-y,y);
  }
  else
  {
   return findgcd(x,y-x);
  }
 }
 return x;
}

score 0 · Accepted Answer

return findgcd(x, y-x);

与以下内容相同：

int t = findgcd(x, y-x);
return t;

我希望这可以帮助您看到它只返回一个值。

score 0 · Accepted Answer

return findgcd(var1,var2)是递归的。findgcd()一直调用自己，直到条件语句while不再为真——这实际上并不正确，它应该是一个if. 一旦它不是真的，它返回输入的参数x。一旦x返回，堆栈就会解开，直到gcd=findgcd(n1,n2);被击中。

c - 计算C中两个数字的GCD

4 回答 4

Related

Reference