如何使用递归将两个正整数相乘？

Question

我正在设计一个递归算法，以创建一个计算两个正整数乘积的函数。我对伪代码有疑问。基本思路：

函数定义必须是“int Product(int a, int b)”,
执行递归调用，直到达到基本情况，
每一步都将“a”添加到局部变量“result”。

迭代的方法有效，而且很容易实现（暂时忽略正整数的限制，所以就认为它们是整数。稍后我会添加那个条件）：

int Product(int a, int b) {
    int result = 0;
     for (int i = 0; i < b; i++) {
         result += a;
    }   return result; 
}

int main(void) {
    int c = Product(3, 2); // 6

    return 0; 
}

现在，我读到如果我想从递归算法中的迭代算法转换，我所要做的就是用另一种方式重写 for 循环：

for 循环的检查条件（即 i < b）是基本情况，
for 循环体（即 result += a）是递归步骤。

但问题是我不知道如何在不使用循环的情况下编写递归算法（因为如果我使用循环，我就没有使用递归方法）。而且没有循环，创建局部变量“i”作为计数器是没有意义的，因为我不能使用goto命令向后跳转。

Answer 1

由于函数中的 for-loop，您在这里所做的不是递归函数。您需要按如下方式实现它：

#include <stdio.h>

int product(int prod, int amount) {
    if (amount == 0)
        return 0;

    return prod + product(prod, amount - 1);
}

int main() {

    int c = product(2, 3);

    return 0;
}

Answer 2

for-loop 架构为：

func() {
    for (int i=0; i<N; i++) {
       body
    }
}

可以重写为以下递归模式：

for_func(int i) {
    if (i<N) { body; for_func(i+1); }
    return;
}

然后你可以重写：

int Product(int a, int b) {
    int result = 0;
     for (int i = 0; i < b; i++) {
         result += a;
    }
    return result; 
}

如：

int rec_Product(int result, int i, int a, int b) {
    if (i<b) {
        return Product(result+a,i+1,a,b);
    } else {
        return result;
    }
}

int Product(int a, int b) {
    return rec_Product(0,0,a,b);
}

Answer 3

您所描述的是将迭代函数转换为递归函数的一般方法。

但是递归函数可以有自己的特殊性。

例如，希望减少递归调用的次数以避免堆栈溢出。

引入中间变量可能是多余的。

至于你的函数，它的参数应该是无符号整数类型unsigned int。否则函数可能有未定义的行为。

函数的return类型应该是unsigned long long以避免bigs numbers产生的溢出。例如，如果您将在第一个参数等于 INT_MAX 且第二个参数等于 2 时调用您的函数，那么您的函数将 return 无效结果。

考虑到所有这些，可以按以下方式定义函数

#include <stdio.h>

unsigned long long int product( unsigned int a, unsigned int b )
{
    return b == 0 ? 0 : a + product( a, ( b - 1 ) / 2 ) + product( a, b - 1 - ( b - 1 ) / 2 );
}

int main( void )
{
    unsigned int a = 2;
    for (unsigned int b = 0; b < 11; b++)
    {
        printf( "%llu ", product( a, b ) );
    }
    putchar( '\n' );
}

程序输出为

0 2 4 6 8 10 12 14 16 18 20

该函数的思想基于以下关系：如果 b 等于 n1 + n2，则 a * b 等于 a * ( n1 + n2 ) 即等于 a *n1 + a * n2。那就是你可以减少函数递归调用的层数。

函数的return语句也可以这样写

return b == 0 ? 0 : ( --b, a + product( a, b / 2 ) + product( a, b - b / 2 ) );

如何使用递归将两个正整数相乘？

how to multiply two positive integers using recursion?

c

iteration

recursion