备战蓝桥杯——递归(9个经典练习题)

红目香薰

发布于 2024-11-13 08:25:04

1.4K0

文章被收录于专栏：CSDNToQQCodeCSDNToQQCode

递归概述

递归是指在函数的定义中使用函数自身的方法。一个函数直接或间接调用自身，这样的函数被称为递归函数。

例如，用数学语言来表示一个简单的递归关系：斐波那契数列。斐波那契数列的定义是

F(n)=F(n-1)+F(n-2)(n>1)，且F(0)=0，F(1)=1

从这个定义可以看出，计算第个斐波那契数，依赖于第n-1和n-2个斐波那契数的计算，这是一个典型的递归定义。

递归与函数的区别

递归：你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门，你继续打开它。若干次之后，你打开面前的门后，发现只有一间屋子，没有门了。然后，你开始原路返回，每走回一间屋子，你数一次，走到入口的时候，你可以回答出你到底用这你把钥匙打开了几扇门。

循环：你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门（若前面两扇门都一样，那么这扇门和前两扇门也一样；如果第二扇门比第一扇门小，那么这扇门也比第二扇门小，你继续打开这扇门，一直这样继续下去直到打开所有的门。但是，入口处的人始终等不到你回去告诉他答案。

基础示例

每次输出的时候再调用函数自身函数，传入自身参数-1，在输出的时候会看到形成递减的效果。

package temp01;

public class Test {

	public static void main(String[] args) {
		printNum(10);
	}

	private static int printNum(int i) {
		System.out.println(i);
		if(i==0) {
			return 0;
		}else {
			return printNum(i-1);
		}
	}
}

递归的精髓是什么

在数学与计算机科学中，递归(Recursion)是指在函数的定义中使用函数自身的方法。实际上，递归，顾名思义，其包含了两个意思：递和归，这正是递归思想的精华所在。

递归就是有去（递去）有回（归来），如下图所示。“有去”是指：递归问题必须可以分解为若干个规模较小，与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决，就像上面例子中的钥匙可以打开后面所有门上的锁一样；“有回”是指 : 这些问题的演化过程是一个从大到小，由近及远的过程，并且会有一个明确的终点(临界点)，一旦到达了这个临界点，就不用再往更小、更远的地方走下去。最后，从这个临界点开始，原路返回到原点，原问题解决。

更直接地说，递归的基本思想就是把规模大的问题转化为规模小的相似的子问题来解决。特别地，在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况，这也正是递归的定义所在。格外重要的是，这个解决问题的函数必须有明确的结束条件，否则就会导致无限递归的情况。

递归的三要素

　　在我们了解了递归的基本思想及其数学模型之后，我们如何才能写出一个漂亮的递归程序呢？笔者认为主要是把握好如下三个方面：

1、明确递归终止条件；

2、给出递归终止时的处理办法；

3、提取重复的逻辑，缩小问题规模。

1). 明确递归终止条件

　　我们知道，递归就是有去有回，既然这样，那么必然应该有一个明确的临界点，程序一旦到达了这个临界点，就不用继续往下递去而是开始实实在在的归来。换句话说，该临界点就是一种简单情境，可以防止无限递归。

2). 给出递归终止时的处理办法

　　我们刚刚说到，在递归的临界点存在一种简单情境，在这种简单情境下，我们应该直接给出问题的解决方案。一般地，在这种情境下，问题的解决方案是直观的、容易的。

3). 提取重复的逻辑，缩小问题规模

　　我们在阐述递归思想内涵时谈到，递归问题必须可以分解为若干个规模较小、与原问题形式相同的子问题，这些子问题可以用相同的解题思路来解决。从程序实现的角度而言，我们需要抽象出一个干净利落的重复的逻辑，以便使用相同的方式解决子问题。

1、阶乘递归示例

package temp01;

public class Main {

	public static void main(String[] args) {
		System.out.println(f(10));;
	}
 
	public static long f(int n) {
		if (n == 1) { // 递归终止条件
			return 1; // 简单情景
		}
		return n * f(n - 1); // 相同重复逻辑，缩小问题的规模
	}
}

2、斐波那契数列

/** * Title: 斐波那契数列 * * Description: 斐波纳契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、…… * 在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）。 * * 两种递归解法：经典解法和优化解法 * 两种非递归解法：递推法和数组法 * /

package temp01;

public class Main {

	public static void main(String[] args) {
		System.out.println(f(10));
	}
 
	public static int f(int n) {
		if (n == 1 || n == 2) { // 递归终止条件
			return 1; // 简单情景
		}
		return f(n - 1) + f(n - 2); // 相同重复逻辑，缩小问题的规模
	}
}

这里有两个递归基例，分别是n == 0时返回 0 和n == 1时返回 1，对应斐波那契数列的起始两项定义。递归步骤return f(n - 1) + f(n - 2);体现了斐波那契数列从第三项起每一项等于前两项之和的规则，通过不断调用自身来获取第n - 1项和第n - 2项的值并相加，以此来计算第n项的值。

3、字符串反转

反向输出字符串

package temp01;

public class Main {

    public static String f(String s) {
        if (s.length() == 0) {
            return s;
        }
        return f(s.substring(1)) + s.charAt(0);
    }

    public static void main(String[] args) {
        System.out.println(f("abcdef"));
    }
}

当字符串长度为 0 时，直接返回该字符串，这就是递归基例。递归步骤中，f(s.substring(1))是对原字符串去掉第一个字符后的子字符串进行反转，然后再加上原字符串的第一个字符s.charAt(0)，不断重复这个操作，逐步实现整个字符串的反转。

4、爬楼梯问题

有一个楼梯，你每次可以爬 1 步或者 2 步。问有多少种不同的方法可以爬到第 n 阶楼梯。

递归基例：当n = 1时，只有 1 种爬法（一步直接到顶）；当n = 2时，有 2 种爬法（一次爬 1 步，分两次爬完；或者一次爬 2 步直接到顶）。递归步骤：对于第n阶楼梯，最后一步可能是从第n - 1阶爬 1 步上来的，也可能是从第n - 2阶爬 2 步上来的。所以爬到第n阶楼梯的方法数等于爬到第n - 1阶楼梯的方法数加上爬到第n - 2阶楼梯的方法数。

package temp01;

public class Test {
	public static int f(int n) {
		if (n == 1) {
			return 1;
		}
		if(n == 2) {
			return 2;
		}
		return f(n - 1) + f(n - 2);
	}

	public static void main(String[] args) {
		System.out.println(f(15));
	}
}

5、计算一个整数的各位数字之和

package temp01;

public class Main {

    public static int f(int n) {
        if (n < 10) {
            return n;
        }
        return n % 10 + f(n / 10);
    }

    public static void main(String[] args) {
        System.out.println(f(12345));
    }
}

递归基例是当n小于 10 时，直接返回n，因为此时它本身就是各位数字之和了。递归步骤里，n % 10获取当前整数n的个位数字，f(n / 10)是对去掉个位数字后的剩余部分（即n除以 10 后的整数部分）继续计算各位数字之和，然后将这两部分相加，不断缩小数字规模，直至达到递归基例。

6、回文字符串的判断

回文字符串就是正读倒读都一样的字符串。如”98789”, “abccba”都是回文字符串

package temp01;

public class Main {

	public static void main(String[] args) {
		System.out.println(f("952757259"));
	}
 
	public static boolean f(String s){
        int start = 0;
        int end = s.length()-1;
        if(end > start){   // 递归终止条件:两个指针相向移动，当start超过end时，完成判断
            if(s.charAt(start) != s.charAt(end)){
                return false;
            }else{
                // 递归调用，缩小问题的规模
                return f(s.substring(start+1).substring(0, end-1));
            }
        }
        return true;
    }
}

7、字符串全排列

从字符串数组中每次选取一个元素，作为结果中的第一个元素；然后，对剩余的元素全排列。

package temp01;

public class Main {

	public static void main(String[] args) {
		String s="abc";
		f(s.toCharArray(),0,s.length()-1);
	}
 
	public static void f(char[] s, int from, int to) {
		if (s != null && to >= from && to < s.length && from >= 0) { // 边界条件检查
			if (from == to) { // 递归终止条件
				System.out.println(s); // 打印结果
			} else {
				for (int i = from; i <= to; i++) {
					swap(s, i, from); // 交换前缀,作为结果中的第一个元素，然后对剩余的元素全排列
					f(s, from + 1, to); // 递归调用，缩小问题的规模
					swap(s, from, i); // 换回前缀，复原字符数组
				}
			}
		}
	}
 
	public static void swap(char[] s, int from, int to) {
		char temp = s[from];
		s[from] = s[to];
		s[to] = temp;
	}
}

8、二分查找

package temp01;

public class Test {

	/**
	 * @search 返回被查找的数的位置下标
     * @param arr    要查找的数组
     * @param target 目标元素
     * @param index  当前查找的起始下标，初始调用时一般设为0
     * @return 找到目标元素返回其下标，若未找到返回 -1
	 * @return
	 */
	public static int f(int[] arr, int target, int index) {
		// 递归基例1：如果索引超出了数组的范围，说明已经遍历完整个数组都没找到，返回 -1
		if (index >= arr.length) {
			return -1;
		}
		// 递归基例2：如果当前下标对应的元素等于目标元素，说明找到了，返回当前下标
		if (arr[index] == target) {
			return index;
		}
		// 递归步骤：继续在下一个下标位置进行查找，将索引加1后递归调用search方法
		return f(arr, target, index + 1);
	}
	public static void main(String[] args) {
		int [] arr={7,2,8,22,56,45,64,5645,64,5,64,56,45,9};
		System.out.println(f(arr,2,0));
		System.out.println(f(arr,5,0));
	}
}

9、汉诺塔问题

古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上。有一个和尚想把这64个盘子从A座移到C座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。在移动过程中可以利用B座。要求输入层数，运算后输出每步是如何移动的。

package temp01;

public class Main {


	  /**     
   * @description 在程序中，我们把最上面的盘子称为第一个盘子，把最下面的盘子称为第N个盘子
   * @param level：盘子的个数
   * @param from 盘子的初始地址
   * @param inter 转移盘子时用于中转
   * @param to 盘子的目的地址
   */
  public static void moveDish(int level, char from, char inter, char to) {

      if (level == 1) { // 递归终止条件
          System.out.println("从" + from + " 移动盘子" + level + " 号到" + to);
          return;
      } else {
          // 递归调用：将level-1个盘子从from移到inter(不是一次性移动，每次只能移动一个盘子,其中to用于周转)
          moveDish(level - 1, from, to, inter); // 递归调用，缩小问题的规模
          // 将第level个盘子从A座移到C座
          System.out.println("从" + from + " 移动盘子" + level + " 号到" + to); 
          // 递归调用：将level-1个盘子从inter移到to,from 用于周转
          moveDish(level - 1, inter, from, to); // 递归调用，缩小问题的规模
      }
  }

  public static void main(String[] args) {
      int nDisks = 10;
      moveDish(nDisks, 'A', 'B', 'C');
	}
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-11-12，如有侵权请联系 cloudcommunity@tencent.com 删除

public