Dsa Using Java 简明教程

DSA using Java - Recursion

Overview

递归是指编程语言中的一个技术，一个函数在其中调用它自身。调用自身的那个函数称为递归方法。

Recursion refers to a technique in a programming language where a function calls itself. The function which calls itself is called a recursive method.

Characteristics

一个递归函数必须具有以下两个特性：

A recursive function must posses the following two characteristics

  1. Base Case(s)

  2. Set of rules which leads to base case after reducing the cases.

Recursive Factorial

阶乘是递归的一个经典示例。阶乘是一个满足以下条件的非负数。

Factorial is one of the classical example of recursion. Factorial is a non-negative number satisfying following conditions.

阶乘表示为“！”。此处规则 1 和规则 2 是基本情况，而规则 3 是阶乘规则。

Factorial is represented by "!". Here Rule 1 and Rule 2 are base cases and Rule 3 are factorial rules.

例如，3! = 3 x 2 x 1 = 6

As an example, 3! = 3 x 2 x 1 = 6

private int factorial(int n){
   //base case
   if(n == 0){
      return 1;
   }else{
      return n * factorial(n-1);
   }
}

Recursive Fibonacci Series

斐波那契数列是递归的另一个经典示例。斐波那契数列是一个满足以下条件的整数数列。

Fibonacci Series is another classical example of recursion. Fibonacci series a series of integers satisfying following conditions.

斐波那契表示为“F”。此处规则 1 和规则 2 是基本情况，而规则 3 是斐波那契规则。

Fibonacci is represented by "F". Here Rule 1 and Rule 2 are base cases and Rule 3 are fibonnacci rules.

例如，F5 = 0 1 1 2 3

As an example, F5 = 0 1 1 2 3

Demo Program

RecursionDemo.java

package com.tutorialspoint.algorithm;

public class RecursionDemo {
   public static void main(String[] args){
      RecursionDemo recursionDemo = new RecursionDemo();
      int n = 5;
      System.out.println("Factorial of " + n + ": "
         + recursionDemo.factorial(n));
      System.out.print("Fibbonacci of " + n + ": ");
      for(int i=0;i<n;i++){
         System.out.print(recursionDemo.fibbonacci(i) +" ");
      }
   }

   private int factorial(int n){
      //base case
      if(n == 0){
         return 1;
      }else{
         return n * factorial(n-1);
      }
   }

   private int fibbonacci(int n){
      if(n ==0){
         return 0;
      }
      else if(n==1){
         return 1;
      }
      else {
         return (fibbonacci(n-1) + fibbonacci(n-2));
      }
   }
}

如果我们编译并运行上述程序，它将生成以下结果 -

If we compile and run the above program then it would produce following result −

Factorial of 5: 120
Fibbonacci of 5: 0 1 1 2 3