开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 递归也没有那么难 -> 正文阅读

[数据结构与算法]递归也没有那么难

前言：在某平台学习了bobo老师介绍的关于递归的知识，个人认为，bobo老师的讲解深入浅出，初学者也可以很容易理解。学到的知识可以帮助我更有条理的分析、解决递归问题，并写出正确的递归算法或函数。它提供了一种解决递归问题的“方法论”，按照次方法逐步分析就可以解决大部分问题，不至于让你拿到问题之后无从下手。因此，想要记录并分享下这部分内容。一来巩固下所学知识，二来也希望能够帮到大家，如果可以的话。

本篇文章，主要介绍

递归的概念；
递归问题的分析方法（原问题、规模更小的问题、如何利用规模更下的问题构建原问题的解、最基本的问题，这些概念下文会介绍）
递归函数的书写（函数的“宏观语义”）
递归函数的调试方法
经典的递归算法的解答：斐波那契数、汉诺塔等等。
其他递归问题（日后不断补充）

一、什么是递归

先通过一个现实生活中的例子，浅浅感受下递归的含义。读这个故事时，给人一种无限循环的感觉。

从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？“从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？‘从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？……’”

下面给出官方正式的递归定义

递归（Recursion /r??k??r?n/），在数学与计算机科学中，是指在函数的定义中调用函数本身。【中文维基百科-递归】

这个定义，是从函数形式的角度分析的。然而，对于我们解决递归问题并没有提供多少可以利用的信息。

下面给出实用的”民间“的递归定义

本质上，递归就是将原来的问题，转化为规模更小的同一问题

举例：数组求和

原来的问题
【计算数组arr[0, n)中n个元素的和】（注释：‘[’ 表示闭区间，‘)’表示开区间），可以用函数表示sum(arr[0，n)); （注释：伪代码形式）
转化为更小的同一问题，以及用更小的同一问题的解去构建原来问题的解
【计算数组arr[1, n)中n-1个元素的和】。“同一问题“体现在当前所面临的问题仍然是计算数组区间中所有元素的和，”更小“体现在原来的问题是计算n个元素的和，当前的问题是计算n-1个元素的和，用函数表示sum(arr[1, n))。现在假设当前的问题sum(arr[1,n))计算n-1个元素的和解决了，那么，原问题的解就是sum(arr[0, n)) = arr[0] + sum(arr[1, n)；换句话说，数组区间arr[1,n)中n-1个元素的和加上元素arr[0] 就等于数组区间arr[0,n)中n个元素的和。
如此，我们就用更小问题的解构建了原问题的解。然后，要解决当前问题，可以从当前问题出发，转化为规模更更小的同一问题。
最基本的问题
【计算数组arr[n, n) 0个元素的和】。当前问题无法在转化为规模更小的同一问题，我们称为最基本的问题，这样的问题需要我们直接给出解，sum(arr[n, n)) = 0;

上述过程，使用简洁的伪代码表示如下：

sum(arr[0, n) = arr[0] + sum(arr[1, n))  <--更小的同一问题
sum(arr[1, n) = arr[1] + sum(arr[2, n)) 
sum(arr[2, n)) = arr[2] + sum(arr[3, n))
... ...
sum(arr[n-2, n)) = arr[n-2] + sum(arr[n-1, n)) 
sum(arr[n-1, n) = arr[n-1] + sum(arr[n, n)) <-- 最基本的问题

原来的问题最终转化为最基本的问题，而最基本的问题的解会被直接给出，则最基本的问题得到解决，接着它的”上一层“问题得到了解决；在”上一层“问题解决后，上一层的”上一层“问题也得到了解决；就像多米诺骨牌，最终原问题得到了解决。上述问题的解决过程也是程序实际调用的过程，先不断的转化为规模更小的问题，直到最基本的问题。然后用更小规模问题（包括最基本问题）的解去构建比当前问题规模稍大的问题的解，最终求得原问题的解。

二、如何书写递归算法

一般情况下，递归算法主要由两部分组成：

求解最基本问题（或者说给出基本问题的解）
把原问题转化为规模更小的问题，同时用更小问题的解构建原问题的解

举例：数组求和（上文已提及）

在具体写代码之前，我们要明确以下几个问题

原问题是什么？
原问题就是我们当前要解决的问题，在本例中，原问题是数组求和，更具体点说就是求解数组区间arr[0, n) 中n个元素的和
规模更小的同一问题是什么，以及如何用规模更小问题的解去构建原问题的解？
前一个问题相对容易回答，原问题是求解n个元素的和，规模更小的问题就是求解数组区间arr[1, n]中n-1个元素的和。
后一个问题相对比较复杂（在数组求和的案例中，可能比较容易思考构建的逻辑，但是针对复杂问题，这一步是最难的），原问题是计算数组区间arr[0, n)共n个元素的和，规模更小的问题是计算arr[1, n)中n -1 个元素的和。因此，数组区间arr[1, n)中n-1个元素的和加上元素arr[0]就是数组区间arr[0, n)中n个元素的和
基本问题是什么？
在本例中，最基本的问题是计算数组区间arr[n, n)中共0个元素的和。有时候，基本问题并不能一眼看出来，需要我们不断尝试。也许你可能有疑惑，基本问题为什么不是计算数组区间arr[n -1, n)中1个元素的和，原因是用户可能有就算空数组的和的需求，求解一个元素的和就不能作为基本问题了。

以上三个问题，可以说是在我们解决递归问题时首先需要回答的非常重要的问题。也许，目前对上述问题没有很深的理解，没有关系，随着下文经典递归算法的分析和解决，会加深对这部内容的认识。

代码书写时， 明确函数的”宏观语义”，即函数的功能是什么，这一点非常非常重要。

Java实现

public class ArrayAlg {
	
	// 宏观语义：计算数组区间arr[l, n)中所有元素的和
	public static int sum(int[] arr, int l) {
		
		// 求解基本问题
		if (l == arr.length) {
			return 0;
		}
		
		// 把原问题转化为更小的同一问题，同时构建原问题的解
		return arr[l] + sum(arr, l + 1); 
	}
}

代码分析如下

上文中，我们使用伪代码表示了数组求和问题 sum(arr[0,n)，和规模更小的问题sum(arr[1,n)，可以看出数组的上界在不断变化，因此我们使用参数 “l” (全拼left)来表示数组的上界。

sum(int[] arr, int l)函数的“宏观语义”：计算数组arr[l…n)中所有元素的和

求解最基本问题（或者说给出基本问题的解）
当l == arr.length，由于arr.length等于n，因此等价于 l ==n。此时arr[n, n)中不包含任何元素，即空数组，空数组的和可以直接给出为0;
把原问题转化为规模更小的问题，同时用更小问题的解构建原问题的解
要计算数组区间arr[l, n)中所有元素的和，转化成规模更小的问题，计算arr[l + 1, n)中所有元素的和。现在，我想要计算数组区间arr[l + 1, n)中所有元素的和，怎么办？我需要找一个函数可以计算arr[l + 1, n)中所有元素的和，这时我发现sum(arr, l)函数的功能正好可以满足我的需要，于是，就可以像调用其他可以完成某种功能的普通函数一样去调用sum(arr, l)函数就行了，唯一特殊的地方就是所调用的函数的名字比较特别罢了。这就是明确函数的宏观语义的好处，根据你需求和函数的功能来选择调用的函数。在写代码时，一定不要去想底层到底是如何执行的，为什么要调用自己，这样非常容易把自己给绕晕。最后，通过调用sum(arr, l + 1)得到了更小问题的解，在加上元素arr[l]，就是原问题（计算数组区间arr[l, n)中所有元素的和）数组求和的解

针对计算数组arr[0…n-1]共n个元素的和，只需要这样调用函数sum(arr, 0)，就可以解决。

三、如何调试递归算法

1.使用IDE集成开发工具

利用单步跟踪的方式调试代码，每个人使用的开发工具可能不同，这里便不在叙述具体使用方法。网上可以很容易检索到使用方法。

请添加图片描述
这里简单说下IDEA调式工具，我认为比较好的一点：对于递归函数，调试时可以显示当前时第几次进入递归函数，或者更形象的说，当前所在位置为递归的”第几层“。由于，递归函数会导致自己调用自己，所以会在一个函数上不断调用，并且会不断返回同一个函数，有了这个标号，就可以很清楚的指名当前递归的”层数“，不至于把自己绕晕
在这里插入图片描述

2.使用纸笔模拟调用过程

把代码做部分修改

int sum(int[] arr, int l) {
	if (l == arr.length) return 0;
	int x = sum(arr, l + 1);
	return x + arr[l];
}

在这里插入图片描述

3.添加一些打印输出的代码

public class Solution {

	// 生成深度字符串
    private static String generateDepthString(int depth) {
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            res.append("--");
        }
        return res.toString();
    }
	//打印输出带有深度字符串的信息
    private static void print(String msg, int depth) {
        String depthString = generateDepthString(depth);
        System.out.println(depthString + msg);
    }

    public static int sum(int[] arr, int l, int depth) {

        // 本次函数调用的任务目标
        print(String.format("Call: sum arr[%d, %d)", l, arr.length), depth);

        if (l == arr.length) {
            // 基本问题的解
            print("Return: 0", depth);
            return 0;
        }

        int x = sum(arr, l + 1, depth + 1);
        // 更小规模问题的解
        print(String.format("After sum arr[%d, %d)", l , arr.length), depth);;

        int ret = x + arr[l];
        // 当前问题（即任务目标）的解
        print("Return: " + ret, depth);
       return ret;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2};
        int res = Solution.sum(arr, 0, 0);

    }
}

添加的代码

首先给递归函数添加表示递归深度的参数depth，这样方便我们查看在每一层递归函数做了什么事情
函数内部主要包括四部分代码：（1）本次函数调用的目标，即当前需要解决的问题
（2）返回当前问题的解（基本问题）（3）规模更小的问题的解（可能不止一个）（4）返回当前问题的解（通过规模更小的问题的解构建出的当前问题的解
添加生成表示深度字符串的函数，深度字符串的形式可以自定义，比较常用的有用“–”或者数字

main函数中初始的层数我设置为0，当然1也时可以的。
在这里插入图片描述

另外，关于深度字符串，可以如上图所示的”–“表示，比较直观。但是，当递归深度较大时，”–“字符串会很长，我们不容易看出当前的递归深度时多少。于是，可以借鉴IDEA开发工具的方式，通过“【数字】”的方式表示递归深度。

代码修改

private static String generateDepthString(int depth) {
    return "【" + depth + "】";
}

运行效果，这里设置初始层的编号为1 。（个人习惯，用数字表示深度从1开始，用“–”表示深度从0开始，这个比较随意，根据自己的情况设置就好）

在这里插入图片描述

四、经典递归问题的分析

1. 斐波那契数

斐波那契数（意大利语：Successione di Fibonacci）

在数学上，斐波那契数是以递归的方法来定义：

F₀= 0
F₁= 1
F_n= F_n-1 + F_n-1 (n>=2)

用文字来说，就是斐波那契数列由0和1开始，之后的斐波那契数就是由之前的两数相加而得出。前几个斐波那契数是：
1、 1、 2、 3、 5、 8、 13、 21、 34、 55、 89、 144、 233、 377
特别指出：0不是第一项，而是第零项。

问题：求解第n项斐波那契数

【来源：中文维基百科-递归】

在写代码之前，我们依然按部就班的分析以下这几个问题

原问题是什么
求解第n项斐波那契数，可以用一个函数表示fib(n)
规模更小的问题，以及如何用规模更小问题的解去构建原问题的解
规模更小的问题，例如，求解第n-1项、第n-2项斐波那契数，这个比较容易分析。具体如何构建原问题的解呢，根据斐波那契数的定义，第n项斐波那契数等于前两项斐波那契数之和，因此，原问题求解第n项斐波那契数就等于第n-1项斐波那契数加上第n-2项斐波那契数的和。用函数表示就是fib(n) = fib(n - 1) + fib(n-2)。
基本的问题是什么
求解第0项斐波那契数和求解第1项斐波那契数是最基本的问题，因为它们都没有前两项，根据定义，不能再转化为规模更小的同一问题。它们的解需要直接给出，即fib(0) = 0，fib(1) = 1。那么求解第2项斐波那契数是基本问题吗？根据定义，显然不是，因为它可以转化为规模更小的同一问题，即fib(2) = fib(1) + fib(0)。

有了上面的分析，代码的书写水到渠成，就是把上面的文字描述“翻译”为代码语言而已。

但是，这里我依然再次强调，代码书写时， 需要明确函数的”宏观语义”，即函数的功能是什么。

public class Solution {

    // 计算第n项斐波那契数
    public static int fib(int n) {

        // 求解最基本的问题
        if (n == 0) {
            return 0;
        }

        if (n == 1) {
            return 1;
        }

        // 把原问题转化为规模更小是问题，同时构建原问题的解
        return fib (n-1) + fib(n-2);
    }
}

代码分析如下：

fib(n)函数的“宏观语义”：计算第n项斐波那契数

求解最基本问题（或者说给出基本问题的解）
求解第0项斐波那契数，直接给出解为0；求解第1项斐波那契数，直接给出解为1；
把原问题转化为规模更小的问题，同时用更小问题的解构建原问题的解
因为第n项斐波那契数等于前两项斐波那契数之和，所以需要先求解第n-1项和第n-2项斐波那契数。这时我发现，fib(n)函数可以计算第n项斐波那契数，正好满足我的需要，我只需要像调用普通函数那样直接拿来用就行了，fib(n-1)、fib(n-2) 分别解决了上面的两个问题，然后原问题通过fib(n)=fib(n-1) + fib(n-2)前两项的和来解决。

不管是数组求和问题，还是求第n项斐波那契数，相对来说都太简单了，似乎没有必要进行如此复杂的分析。的确如此，我们只是从简单问题入手，介绍下解决递归问题通用的处理方法，不至于在解决复杂问题时无从下手。

有了上面的基础，我们有必要介绍几个相对复杂的使用递归可以解决的问题了。

2. 矩形覆盖（类似斐波那契数问题）

这是一个与斐波那契数类似的问题，构建原问题的解的逻辑相似，建议先尝试按照上面问题的解决方式分析下该问题，看我们的解决方式是否一致。也可以练习下学过的知识。

使用2*1的小矩形横着或者竖着并且无重叠地去覆盖一个2*n的大矩形，总共有多少种方法？

【来源：CSDN博文–递归算法-斐波那契数列】

举个例子，2*n的大矩形，我们令n=2。即使用2*1的小矩形无重叠的覆盖一个2*2的大矩形，如下图所示共有两种方式

为了区分不同的小矩形块，我使用了不同的颜色的小矩形块，表示相同大小2*1的矩形块。

第一种方式，先横着放一块，下一块只能横着放，
第二种方式，先竖着放一块，下一块只能竖着放。

在这里插入图片描述
如果n=1，那么使用2*1的小矩形无重叠的覆盖一个2*1的大矩形，显然只有一种方式，如下图所示

在写代码之前，我们依然按部就班的分析以下这几个问题

原问题
求解使用2*1的矩形（横着或者竖着无重叠的）覆盖2*n的大矩形的所有方式，用函数表示就是f(n)；
规模更小的问题及构建原问题的解
覆盖2*(n-1)、2*(n-2)等等大矩形是规模更小的问题，比起原问题少覆盖一个或者两个2*1的矩形，用函数表示为f(n-1)、f(n-2)；
具体如何用更小规模问题的解去构建原问题的解呢？
(1) 假设在一个2*n的大矩形中先横着放一块，如下图所示

先横着放一块，它下面的空间也只能放一块。剩下的2*(n-2)的大矩形共有f(n-2) = x种覆盖方式，换句话说，以两个横着摆放的矩形开头的2*n的大矩形，共有x种覆盖方式。

(2)假设在一个2*n的大矩形中先竖着放一块，如下图所示

先竖着放一块，剩下的2*(n-1)的大矩形共有f(n-1)=y种覆盖方式。换句话说，以一个竖着摆放的矩形开头的2*n的大矩形，共有y种覆盖方式

综上，一个2*n的大矩形，第一块要么横着放，共有f(n-2)种覆盖方式；第一块要么竖着放，共有f(n-1)种覆盖方式，因此，原问题f(n) = f(n-1) + f(n-2)，发现了吧，这和斐波那契数的构建逻辑相同。
最基本的问题
当n = 1时，f(1) = 1；当n=2时f(2)=2；当n=3时，就不是基本问题了，f(3) = f(2) + f(1) = 3 。

有了上文的分析，代码书写就很简单了。最好，在强调一次，代码书写时， 需要明确函数的”宏观语义”，即函数的功能是什么。

public class Solution {
	// 宏观语义：计算2*n的大矩形的所有覆盖方式
	public static int rectCover(int n) {
		// 求解基本问题
		if (n == 1) {
			return 1;
		}

		if (n == 2) {
			return 2; 
		]
		// 把原问题转化为更小的同一问题，同时构建原问题的解
		return rectCover(n - 1) + rectCover(n - 2);
	}
}

3. 汉诺塔

在经典汉诺塔问题中，有 3 根柱子及 N个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
(1) 每次只能移动一个盘子;
(2) 盘子只能从柱子顶端滑出移到下一根柱子;
(3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

【来源：Leetcode-面试题 08.06. 汉诺塔问题】

请添加图片描述
依旧是按部就班的分析

原问题
把n个圆盘按规则从A柱子移动到C柱子上，用函数f(n, A, B, C)表示。
规模更小的问题及构建原问题的解
第一步，把n-1个圆盘从A移动到B柱子上，用函数表示f(n-1, A, C, B)；
第二步，把1个圆盘从A移动到C柱子上，用函数表示f(1, A, B, C);
第三步，把n-1个圆盘从B移动到C柱子上，用函数表示f(n-1, B, A, C);
以上三个都是规模更小的同一问题。数据规模分别为n-1、1、n-1，同一问题是指把所有圆盘从一根柱子移动到另一个柱子。另外，可以很明显的看出，其构建原问题的解的逻辑不同于斐波那契树f(n) = f(n-1) + f(n-2）和数组求和f(n) = a + f(n -1），它的构建逻辑是将原问题分解为不同的步骤。
最基本的问题
很明显，最基本的问题是把1个圆盘按规则从A柱子移动到C柱子上，f(1, A, B, C)，直接挪动圆盘就解决了这个问题。

代码书写，需要明确明确函数的宏观语义，即函数的功能是什么。

另外，我这里使用栈存储”圆盘“，”圆盘“是Integer类型的值。

import java.util.Stack;

public class Solution {

    // 按规则将n个圆盘从a柱移动到c柱上
    public static void move(int n, 
    Stack<Integer> a, Stack<Integer> b, Stack<Integer> c) {

        // 求解最基本的问题
        if (n == 1) {
            c.push(a.pop());
            return;
        }

        move(n - 1, a, c, b); // a柱上n-1个圆盘移动的b柱上
        move(1, a, b, c);     // a柱子1个圆盘移动到c柱上
        move(n - 1, b, a, c);  // b柱子n-1个圆盘移动到c柱上
    }
}

五、递归问题的类型

本部分是对上文中涉及到的递归问题的分类，依据是通过规模更小的问题构建原问题的逻辑，主要有三类

f(n) = x + f(n-1) ，典型问题数组求和，先把n-1项的问题解决了，再解决某n项的问题。
f(n) = f(n-1) + f(n-2)，典型问题斐波那契树。原问题需要前n-1项、前n-2项的处理结果
按步骤处理，汉诺塔问题

六、不断补充的递归问题

本部分会不间断补充一些递归问题，并给出部分问题的参考解答。另外，这些递归问题可能会涉及链表、树相关的知识。括号中是问题的相对难度分为（简单、中等和困难），可以更具自己的情况选择问题解决。

1. 阶乘问题（简单）

阶乘是基斯顿·卡曼（Christian Kramp，1760～1826）于 1808 年发明的运算符号，是数学术语。

一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1。自然数n的阶乘写作n!。1808年，基斯顿·卡曼引进这个表示法。

亦即n!=1×2×3×…×(n-1)×n。阶乘亦可以递归方式定义：0!=1，n!=(n-1)!×n。
问题：计算n的阶乘

2. 两数相加（中等）

[2022/5/31 添加]

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

解题模板：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

    }
}

来源：力扣（LeetCode）
可以点击链接，查看原题。解答后，还可以提交答案，看算法实现是否正确

问题分析

链表头代表了实际数字的低位，链表尾代表了实际数字的高位。

原来的问题
计算n位数相加的结果，如下图所示。
规模更小的问题
计算后n-1位数相加的结果。假设该问题得到了解决，我们只需要将第1位（同时也是最低位）相加即可，然后判断相加的结果是否大于10，即是否需要进位，如果需要进位，则下一位加1即可。同时也要判断下一位加一后是否需要继续进位，以此类推。

3 最基本的问题
当某位两个相加的数字，其中一个为空时，是最基本的问题。在链表中，当前位一个是null，一个是数字，如下所示。这时，无法分解为规模更小的问题，其解可以直接给出为当前数字的值。

代码书写

 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

      // 最基本的问题
        if (l2 == null) {
            return l1;
        }

        if (l1 == null) {
            return l2;
        }

		// 转化为规模更小的问题
        l1.next = addTwoNumbers(l1.next, l2.next);
        l1.val = l1.val + l2.val;

		// 处理进位
        ListNode cur = l1;
        while (cur.val >= 10) {
            cur.val -= 10;
            if (cur.next == null) {
                cur.next = new ListNode(1);
            }else {
                cur.next.val += 1;
            }
            cur = cur.next;
        }
        return l1;

    }

代码分析，这里我没有新建一个链表用于存放结果，而是直接存放在了l1里（当然l2也可以）。求解后n-1位的和之后，把它挂接到l1第一节点后面，然后只剩下第一位（实际数字的最低位）没有处理，计算两个数字的第一位（最低位）的和，计算出结果后，直接放入l1的第一个节点中。放入值后，从当前位开始扫描，看存储的值是否大于等于10，如果是，则当前值减去10后放回，接着下一位加1，然后从下一位开始是否大于等于10，以此类推。

3. 递归乘法 (中等）

[2022/6/2 添加]

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

提示:
保证乘法范围不会溢出

解题模板

class Solution {
    public int multiply(int A, int B) {

    }
}

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/recursive-mulitply-lcci

问题分析

起初，我阅读完这个题目，觉得它的难度等级不应该设置为中等，应该是简单才对。因为它类似数组求和，直接递归的累加就可以了。

Java 代码如下所示

public int multiply(int A, int B) {

        if (A == 0) {
            return 0;
        }

        return  B + multiply(A - 1, B);
    }

在数学中，A * B，我们称A为被乘数，B为乘数。更小规模的问题A - 1个B的和算出来了，再加上一个B，不就是A*B的结果了。

然而，这个算法，在leetcode上没有通过。出现错误的测试用例是A = 918795921, B = 1，由于递归调用太多，造成了栈溢出。

这时，我发现题目中的移位运算符我还没有用呢？不用想，肯定要在这上面下文章了

令被乘数A = x + y，x 是 2的k次方（形式）小于或者等于A的最大值。 y = A - x

举个例子 A = 7 ，那么x = 4 (即2的2次方)，2的3次方是8，就超过7了。y 就是 7 - 4 = 3；

A = 8, 那么 x = 8, y = 0;

A * B = (x + y) * B

x*B = B * x = B * (2的k次方) = B << k

y* B 就是递归调用了，然后y像A 一样继续分解。

Java代码如下:

 public int multiply(int A, int B) {

        // A = 2k次方 + x 将被乘数A分解为两个更小的数

        if (A == 0) {
            return 0;
        }

        if (A == 1) {
            return B;
        }

        // 把A分解为x和y， x = 2的k次方，x是小于等于A的最大的2的k次方的值
        int x = 2, y, k;
        for ( k = 1 ; x * 2 <= A ; k++) {
            x *=2;
        }

        y = A - x;

        int resY = multiply2(y, B);
        int resX = B << k;

        return resX + resY;

    }