用java如何实现递归算法-问答-最代码

jianboluo LV3 2020年3月4日

6.1斐波那契数列
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波纳契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用，为此，美国数学会从1963年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。

public class FibonacciDemo {

// 全局变量sum1记录第一个方法调用的次数,sum2记录第二个方法调用的次数
static int sum1;
static int sum2;

public static void main(String[] args) {
// n代表数列的长度、 a代表数列的第一项、 b代表数列的第二项
int n = 10;
int a = 1;
int b = 1;
long algResult = fibonacci(n);
// 使用未优化的递归算法得到值
System.out.println("使用未优化的递归算法得到值:" + algResult + "方法调用次数为：" + sum1);
// 使用优化的递归算法，减少冗余的方法调用得到的值
long algEvoResult = fibonacciEvolution(a, b, n);
System.out.println("使用已经优化的递归算法得到值:" + algEvoResult + "方法调用次数为：" + sum2);

}

public static long fibonacci(int n) {
// 记录调用方法次数
sum1++;
if (n < 2) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}

public static long fibonacciEvolution(int a, int b, int n) {
// 记录调用方法次数
sum2++;
if (n > 2) {
return fibonacciEvolution(a + b, a, n - 1);
}
return a;
}
}
6.2阶层
阶乘是基斯顿·卡曼（Christian Kramp，1760～1826）于 1808 年发明的运算符号，是数学术语。一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1。自然数n的阶乘写作n!。1808年，基斯顿·卡曼引进这个表示法。亦即n!=1×2×3×...×n。阶乘亦可以递归方式定义：0!=1，n!=(n-1)!×n。

public class FactorialDemo {
// 全局变量sum，记录方法调用的次数
static int sum;

public static void main(String[] args) {
int n = 10;
int result = factorial(n);
System.out.println("n的阶乘为：" + result + ";调用方法次数为:" + sum);
}

public static int factorial(int n) {
sum++;
// 0 和 1 的阶乘都是1
if (n == 1 || n == 0) {
return 1;
}
int result = n * factorial(n - 1);
return result;
}
}
6.3归并排序
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。用途：（速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列，应用见2011年普及复赛第3题“瑞士轮”的标程）

public class MergingSortDemo {
// private static long sum = 0;

/**
* * <pre>
* * 二路归并
* * 原理：将两个有序表合并和一个有序表
* * </pre>
* *
* * @param a
* * @param s
* * 第一个有序表的起始下标
* * @param m
* * 第二个有序表的起始下标
* * @param t
* * 第二个有序表的结束下标
* *
*/
private static void merge(int[] a, int s, int m, int t) {
int[] tmp = new int[t - s + 1];
int i = s, j = m, k = 0;
while (i < m && j <= t) {
if (a[i] <= a[j]) {
tmp[k] = a[i];
k++;
i++;
} else {
tmp[k] = a[j];
j++;
k++;
}
}
while (i < m) {
tmp[k] = a[i];
i++;
k++;
}
while (j <= t) {
tmp[k] = a[j];
j++;
k++;
}
System.arraycopy(tmp, 0, a, s, tmp.length);
}

/**
* *
* * @param a
* * @param s
* * @param len
* * 每次归并的有序集合的长度
*/
public static void mergeSort(int[] a, int s, int len) {
int size = a.length;
int mid = size / (len << 1);
int c = size & ((len << 1) - 1);
// -------归并到只剩一个有序集合的时候结束算法-------//
if (mid == 0)
return;
// ------进行一趟归并排序-------//
for (int i = 0; i < mid; ++i) {
s = i * 2 * len;
merge(a, s, s + len, (len << 1) + s - 1);
}
// -------将剩下的数和倒数一个有序集合归并-------//
if (c != 0)
merge(a, size - c - 2 * len, size - c, size - 1);
// -------递归执行下一趟归并排序------//
mergeSort(a, 0, 2 * len);
}

public static void main(String[] args) {
int[] a = new int[]{4, 3, 6, 1, 2, 5};
mergeSort(a, 0, 1);
for (int i = 0; i < a.length; ++i) {
System.out.print(a[i] + " ");
}
}
}

6.4快速排序
快速排序（Quicksort）是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

public class QuickSortDemo {

// 分区
private static int partition(int[] arr, int start, int end) {
// 得到数组中第一个元素的值
int key = arr[start];
// 判断数组长度
while (start < end) {
while (arr[end] >= key && end > start)
end--;
arr[start] = arr[end];
while (arr[start] <= key && end > start)
start++;
arr[end] = arr[start];

}
arr[start] = key;
return start;
}

// 快排
public static void quickSort(int arr[], int start, int end) {
if (start < end) {
int index = partition(arr, start, end);
// 递归调用
quickSort(arr, start, index - 1);
quickSort(arr, index + 1, end);
}
}

// 测试
public static void main(String[] args) {
int arr[] = {12, 32, 41, 90, 8, 68, 44, 31, 33, 9};
// start:arr数组第一个元素的下标
// end :arr数组最后一个元素的下标
int start = 0;
int end = arr.length - 1;
quickSort(arr, start, end);
System.err.println("排序后为:" + Arrays.toString(arr));

}
}
6.5二分查找
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

public class BinarySearchDemo {

public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9, 11};
int key = 11;
int index = binarySearch(arr, key);
System.out.println("二分查找元素的下标为:" + index);
int index1 = recursionBinarySearch(arr, key - 2, 0, arr.length - 1);
System.out.println("递归二分查找元素的下标为:" + index1);
}

// 二分查找 key为目标元素返回查找元素的下标
public static int binarySearch(int arr[], int key) {
int low = 0;
int high = arr.length - 1;
int middle;

while (low <= high) {
middle = (low + high) / 2;
if (arr[middle] > key) {
// 比关键字大则关键字在左区域
high = middle - 1;
} else if (arr[middle] < key) {
// 比关键字小则关键字在右区域
low = middle + 1;
} else {
return middle;
}
}
System.err.println("不存在此元素");
return -1;
}

// 递归实现二分查找
public static int recursionBinarySearch(int[] arr, int key, int low, int high) {

if (key < arr[low] || key > arr[high] || low > high) {
return -1;
}

int middle = (low & high) + ((low ^ high) >> 1); //初始中间位置
if (arr[middle] > key) {
//比关键字大则关键字在左区域
return recursionBinarySearch(arr, key, low, middle - 1);
} else if (arr[middle] < key) {
//比关键字小则关键字在右区域
return recursionBinarySearch(arr, key, middle + 1, high);
} else {
return middle;
}

}
}

6.6树的遍历和许多树的问题：中序遍历、前序遍历、后序遍历
package com.wxt.recursive;

import com.wxt.pojo.Node;

/**
* @description: 使用递归方法演示前序、中序、后续遍历
* @author: Mr.Wang
* @create: 2019-01-04 22:58
**/
public class BinaryTree {
public Node init() {
//注意必须逆序建立，先建立子节点，再逆序往上建立，因为非叶子结点会使用到下面的节点，而初始化是按顺序初始化的，不逆序建立会报错
Node J = new Node(8, null, null);
Node H = new Node(4, null, null);
Node G = new Node(2, null, null);
Node F = new Node(7, null, J);
Node E = new Node(5, H, null);
Node D = new Node(1, null, G);
Node C = new Node(9, F, null);
Node B = new Node(3, D, E);
Node A = new Node(6, B, C);
//返回根节点
return A;
}

// 得到当前节点
public void printNode(Node node) {
int data = node.getData();
String result = String.valueOf(data);
System.out.print(result);
}

// The former sequence traversal - 前序遍历
public void firstTraversal(Node root) {
printNode(root);
// 使用递归算法遍历左节点
if (root.getLeftNode() != null) {
firstTraversal(root.getLeftNode());
}
// 使用递归算法遍历右节点
if (root.getRightNode() != null) {
firstTraversal(root.getRightNode());
}
}

// In the sequence traversal - 中序遍历
public void inOtherTraversal(Node root) {
if (root.getRightNode() != null) {
inOtherTraversal(root.getRightNode());
}

printNode(root);

if (root.getLeftNode() != null) {
inOtherTraversal(root.getLeftNode());
}

}

// The former sequence traversal - 后续遍历
public void postOtherTraversal(Node root) {
if (root.getRightNode() != null) {
postOtherTraversal(root.getRightNode());
}
if (root.getLeftNode() != null) {
postOtherTraversal(root.getLeftNode());
}
printNode(root);
}

public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
// 初始化二叉树
Node root = tree.init();
System.out.println("先序遍历:");
tree.firstTraversal(root);
System.out.println("");
System.out.println("中序遍历:");
tree.inOtherTraversal(root);
System.out.println("");
System.out.println("后序遍历:");
tree.postOtherTraversal(root);
System.out.println("");
}

}

评论(0) 最佳答案

947335690 LV1 2020年3月4日

三角数字

【1，3，6，10，15......】

规律：f(n) = f(n-1) + n;

结束条件：f(1) = 1;

package cn.itcast;

public class Recursion {

public static int getNumber(int n) {

// 结束条件

if (n == 1) {

return 1;

}

// 规律

return getNumber(n - 1) + n;

}

斐波那契数列

【1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89......】

规律：f(n) = f(n-1) + f(n-2);

结束条件：f(1) = 1;f(2) = 1;

package cn.itcast;

public class Recursion {

public static int getNumber(int n) {

// 结束条件

if (n == 1 || n == 2) {

return 1;

}

// 规律

return getNumber(n - 1) + getNumber(n - 2);

}

hbsoft2008 LV16 2020年3月7日

好算法，学习了

startleback LV1 2020年4月1日

看看评论区，学习学习

biubiuchen LV11 2020年4月9日

1.打印n对有效括号"()",来自leetcode算法题目

//打印(n对)有效括号 n为2 则 ()(),(()),n为3 ((())), (()()), (())(), ()(()), ()()()

private static List<String> strings;


public static List<String> bracket(int n) {
    strings = new ArrayList<>();
    _bracket(0, 0, n, "");
    return strings;
}
//left:左括号数,right:右括号数
public static void _bracket(int left, int right, int n, String s) {
//退出条件,左括号数==右括号数==n
    if (left == n && right == n) {
        // TODO: 2020/3/23
        strings.add(s);
    }
//有效括号,必然'('开头,所以先判断左括号数是否小于n,小于则添加一个 '('
    if (left < n) {
        _bracket(left + 1, right, n, s + "(");
    }
//左括号数必然大于等于右括号数
    if (left > right) {
        _bracket(left, right + 1, n, s + ")");
    }
}

2.分治:算x^n,时间复杂度为 log2 N

//思路:算2^10,可以分为2^5*2^5 ->2^2*2^2*2...

private static double result(double x, int n) {
    //判断 n是否小于0
    if (n < 0) {
        x = 1 / x;
        n = -n;
    }
    if (n == 0) {
        return 1.0;
    }
    double temp = result(x, n / 2);
    //判断n的奇偶性,偶数直接 * ,奇数则再乘 x
    return n % 2 == 0 ? temp * temp : temp * temp * x;
}

vogue琪琪 2020年5月27日

学习啦

西瓜啦啦 LV1 2020年8月5日

全局变量sum1记录第一个上海快3方法调用的次数,sum2记录第二个方法调用的次数