【JAVA】再帰経典例題

n番目のフィボナッチの数列を求めます

public class Recursion {
	static int Fibonacci(int n) {
		if (n == 0)
			return 0;
		if (n == 1)
			return 1;
		return Fibonacci(n - 1) + Fibonacci(n - 2);
	}
	public static void main(String[] args) {
	int n = new Scanner(System.in).nextInt();
	System.out.println(Fibonacci(n));
	}
 }

ハノータ

public class Recursion {
	static void Hanoi(int n, String source, String temp, String target) {
		if (n == 1) {
			System.out.println("  " + 1 + "   " + source + "   " + target);
		} else {
			Hanoi(n - 1, source, target, temp);
			System.out.println("  " + n + "   " + source + "   " + target);
			Hanoi(n - 1, temp, source, target);
		}
	}
	public static void main(String[] args) {
	int n = new Scanner(System.in).nextInt();
	Hanoi(3, "A", "B", "C");
	}
 }

nの階乗

public class Recursion {
	static int Factorial(int n) {
		if (n == 1)
			return 1;
		return n * Factorial(n - 1);
	}
	public static void main(String[] args) {
	int n = new Scanner(System.in).nextInt();
	System.out.println(Factorial(n));
	}
 }

カエルのステップ分析:n=1の場合、n=2のステップがあり、1回に1回に2回、1回に2回、合計2つのステップがn>=2の場合、nのステップがあります.F(n)種類の飛び方(1)初めて1段を選択すると、残りのn-1段にはF(n-1)種類の飛び方(2)があり、初めて2段を選択すると、残りのn-2段にはF(n-2)種類の飛び方があるので、n段がある場合はF(n)=F(n-1)+F(n-2)種類の飛び方がある.この問題はフィボナッチ数列問題に帰結できる(注意すべきはフィボナッチ数列の第2項が1であり、この問題はn=2の場合2である)

import java.util.Scanner;

public class          {
	public static int Skip_step(int target) {

		if (target == 1 || target == 2) {
			return target;
		} else {
			return Skip_step(target - 1) + Skip_step(target - 2);
		}
	}

	public static void main(String[] args) {
		System.out.println("      :");
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		double startTime = System.currentTimeMillis();
		System.out.println("   " + (Skip_step(n)) + "   ");
		double endTime = System.currentTimeMillis();
		System.out.println("    :" + (endTime - startTime) + "ms");
	}
}