12遞歸

1.概述

2.幾個遞歸模板

(1)求階乘

int f(int n){
if(n == 1) return 1;
return f(n-1) * n;
}

(2)斐波拉契序列

int f(int n){
if(n == 1 || n == 2) return n;
return f(n - 1) + f(n - 2);
}

例題一-藍橋5194

int f(int n){if(n == 0) return 1;if(n % 2 == 0) return f(n / 2)；return f(n - 1) + 1;
}

例題二-藍橋19880-組合數模板

模板

int C(int n, int m){if(n == m || m == 0) return 1;return C(n-1,m-1) + C(n-1,m);
}

import java.util.Scanner;
// 1:無需package
// 2: 類名必須Main, 不可修改public class Main {static int t,n,m;public static void main(String[] args) {solve();}public static int C(int n, int m){if(n == m || m == 0) return 1;return C(n-1,m-1) + C(n-1,m);}public static void solve(){Scanner sc = new Scanner(System.in);//輸入tt = sc.nextInt();for(int i = 0; i < t; i++){n = sc.nextInt();m = sc.nextInt();System.out.println(C(n,m));}sc.close();}
}