Dsa Using Java 简明教程

DSA using Java - Recursion

Overview

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

Characteristics

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

  1. Base Case(s)

  2. 导致在缩小情况后得出基本情况的规则集。

Recursive Factorial

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

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

例如，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

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

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

例如，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));
      }
   }
}

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

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