力扣面试题 43 - 递归乘法 C语言解法

题目：

递归乘法。 写一个递归函数，不使用 * 运算符， 实现两个正整数的相乘。可以使用加号、减号、位移，但要吝啬一些。

示例1:

 输入：A = 1, B = 10
 输出：10

示例2:

 输入：A = 3, B = 4
 输出：12

提示:

1. 保证乘法范围不会溢出

思路：

• A与B相乘，本质上是A个B相加，或者是B个A相加
• 递归加法即得解

C代码：

int multiply(int A, int B) {if (A == 0 || B == 0) return 0;if(B == 1) return A;// 递归关系：A * B 等于 A 加上 (A * (B - 1))return A + multiply(A, B - 1);
}

下面分享评论区的一个很巧妙的代码（作者：0x7FFFFFFF）

class Solution {
public:int multiply(int A, int B) {return sizeof(char[A][B]);}
};

char[A][B] 是一个类型表达式，用于描述一个二维数组的类型，而不需要具体的数组名字。这样的写法是合法的，sizeof(char[A][B]) 能正确计算出这个类型所需的内存大小。

如果 A 和 B 是有效的正整数，sizeof(char[A][B]) 会返回 A * B，因为每个 char 占用 1 字节，二维数组的总大小就是 A * B 字节。