蓝桥杯学习-12递归

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();}
}