C中的递归使非递归函数成为递归函数
gcd应该是一个递归函数。 它应该返回无效。 它应该采用两个正整数并将GCD放在第三个参数中。
这是我的编码gcdfunction。 但是,我意识到它不是一个递归函数。 我如何更改此代码以使其成为递归函数?
void gcd(int *x, int *y) { int i; getValuesForGCD(x, y); for (i = *x; i >= 1; i--) { if (*x % i == 0 && *y % i == 0) { printf("The GCD of %d and %d is %d", *x, *y, i); break; } } }
GCD自然被定义为复发公式。 它直接转换为递归函数:
gcd(a, 0) = a gcd(a, b) = gcd(b, a % b)
用C
格式写这个,就是这样。
int gcd(int a, int b) { if (b == 0) then return a else return gcd(b, a % b); }
您应该注意到a和b必须是非负数。
好的是,这是一个尾递归,因此它的运行速度与非递归方法一样快。
通常,人们会努力去除递归,而不是介绍它。
如果您希望迭代算法的文字转换为递归,它将如下所示:
void gcdrecursive(int *x, int *y, int i) { if (i >= 1) { if (*x % i == 0 && *y % i == 0) { printf("The GCD of %d and %d is %d", *x, *y, i); } else { gcdrecursive(x, y, i - 1); } } } void gcd(int *x, int *y) { getValuesForGCD(x, y); gcdrecursive(x, y, *x); }
要将迭代解决方案转换为递归,可以将每个循环转换为递归函数,该函数执行循环的一次迭代,然后递归调用自身以进行下一次迭代。 打破循环对应于停止递归。 在您的示例中,循环中断有两个原因:找到GCD或者i
达到零。
请注意,这不是gcd的最佳算法,但它会根据您的要求提供您提供的function并将其转换为递归。