java遞歸算法的實例詳解

更新時間：2020年02月05日 09:48:09 作者：V

在本篇文章里小編給大家整理了關于java遞歸算法的實例內(nèi)容，以及相關知識點總結，需要的朋友們可以學習下。

遞歸三要素：

1、明確遞歸終止條件；

2、給出遞歸終止時的處理辦法；

3、提取重復的邏輯，縮小問題規(guī)模。

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、斐波那契數(shù)列

前兩項均為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 {

  //二叉樹節(jié)點

  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;

  }

 

  //前序遍歷:根節(jié)點，左子樹，右子樹

  public static void preOrderTraveral(TreeNode node) {

    if (node == null) {

      return;

    }

    System.out.println(node.data);

    preOrderTraveral(node.leftChild);

    preOrderTraveral(node.rightChile);

  }

 

  //中序遍歷：左子樹，根節(jié)點，右子樹

  public static void inOrderTraveral(TreeNode node) {

    if(node == null) {

      return;

    }

 

    inOrderTraveral(node.leftChild);

    System.out.println(node);

    inOrderTraveral(node.rightChile);

 

  }

 

  //后序遍歷：左子樹，右子樹，根節(jié)點

  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遞歸算法實例的詳細內(nèi)容，大家如果有任何補充的地方可以聯(lián)系腳本之家小編。

您可能感興趣的文章: