java recursive algorithm example

Three elements of recursion:

1. Clarify the recursion termination conditions;

2. Give the handling method when the recursion terminates;

3. Extract repeated logic and reduce the size of the problem.

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

(Recommended learning:java video tutorial)

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. Fibonacci Sequence

The first two items are both 1. Starting from the third term, each term is equal to the sum of the previous two terms. That is: 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. Binary tree traversal (before, during and after)

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 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 inputList = new LinkedList(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); } }

Related article tutorials Share:java introductory tutorial

The above is the detailed content of java recursive algorithm example. For more information, please follow other related articles on the PHP Chinese website!