java递归算法的实例详解

递归三要素：

1、明确递归终止条件；

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

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

1、1+2+3+…+n

import java.util.Scanner;

public class Recursion {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

System.out.println(sum(n));

}

public static int sum(int n) {

if(n == 1) {

return n;

}

else {

return n + sum(n-1);

}

}

}

2、1 * 2 * 3 * … * n

import java.util.Scanner;

public class Recursion {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

System.out.println(multiply(n));

}

public static int multiply(int n) {

if(n == 1) {

return n;

}

else {

return n*multiply(n-1);

}

}

}

3、斐波那契数列

前两项均为1，第三项开始，每一项都等于前两项之和。即：1，1，2，3，5，8，…

import java.util.Scanner;

public class Recursion {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

System.out.println(fun(n));

}

public static int fun(int n) {

if (n <= 2) {

return 1;

}

else {

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

}

}

}

4、二叉树的遍历（前、中、后）

import java.util.Arrays;

import java.util.LinkedList;

public class MyBinaryTree {

//二叉树节点

private static class TreeNode{

int data;

TreeNode leftChild;

TreeNode rightChile;

public TreeNode(int data) {

this.data = data;

}

}

//构建二叉树

public static TreeNode createBinaryTree(LinkedList<Integer> inputList) {

TreeNode node = null;

if(inputList == null || inputList.isEmpty()) {

return null;

}

Integer data = inputList.removeFirst();

//如果元素为空，则不再递归

if(data != null){

node = new TreeNode(data);

node.leftChild = createBinaryTree(inputList);

node.rightChile = createBinaryTree(inputList);

}

return node;

}

//前序遍历:根节点，左子树，右子树

public static void preOrderTraveral(TreeNode node) {

if (node == null) {

return;

}

System.out.println(node.data);

preOrderTraveral(node.leftChild);

preOrderTraveral(node.rightChile);

}

//中序遍历：左子树，根节点，右子树

public static void inOrderTraveral(TreeNode node) {

if(node == null) {

return;

}

inOrderTraveral(node.leftChild);

System.out.println(node);

inOrderTraveral(node.rightChile);

}

//后序遍历：左子树，右子树，根节点

public static void postOrderTraveral(TreeNode node) {

if (node == null) {

return;

}

postOrderTraveral(node.leftChild);

postOrderTraveral(node.rightChile);

System.out.println(node.data);

}

public static void main(String[] args) {

LinkedList<Integer> inputList = new LinkedList<Integer>(Arrays.asList(new Integer[]{3,2,9,null,null,10,null,null,8,null,4}));

TreeNode treeNode = createBinaryTree(inputList);

System.out.println("前序遍历：");

preOrderTraveral(treeNode);

System.out.println("中序遍历：");

inOrderTraveral(treeNode);

System.out.println("后序遍历：");

postOrderTraveral(treeNode);

}

}

来源：https://www.php.cn/java/guide/442072.html