java递归算法实例

Java  /  管理员 发布于 8年前   169

递归三要素：

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

（推荐学习：java视频教程）

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);    }}

相关文章教程分享：java入门教程

以上就是java递归算法实例的详细内容，更多请关注其它相关文章！