算法设计思想

递归就是一个过程或函数在其定义中直接或间接调用自身的一种方法。它通常把一个大型的复杂问题层层转化为一个与原问题相似的规模较小的问题来求解，递归方法只需要少量的程序就可以描述出多次重复计算的解题过程，大大减少了代码量。

递归的两个基本要素：
    1、递归关系式：确定关系式，即原问题是如何分解为子问题的
    2、递归出口：确定递归到什么时候终止。

典型例题

一、母牛繁殖问题

有一头母牛，它每年年初生一头小母牛，每头小母牛从第四年开始，每年也生一头小母牛，求到n年的时候，一共有多少母牛（不计死亡）

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int cowNum = cow(n);
		System.out.println(cowNum);

	}

	private static int cow(int n) {
		if (n < 4)
			return n;
		else
			return cow(n - 1) + cow(n - 3);
	}

}

二、输出各位的数字

任给一个十进制数字，从低位到高位输出每位数字。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		digit(n);

	}

	private static void digit(int n) {
		List<Integer> list = new ArrayList<Integer>();
		while (n>0) {
			int a=n%10;
			list.add(a);
			n=n/10;
		}
		for (int i = 0; i < list.size(); i++) {
			System.out.print(list.get(i)+" ");
		}
	}
}

算法优化：利用递归方法。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Math_reverse {
	
	private static List<Integer> list = new ArrayList<Integer>();

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		List<Integer> digit = digit(n);
		Collections.reverse(digit);
		digit.forEach(System.out::print);
	}

	private static List<Integer> digit(int n) {
		if (n < 10)
			list.add(n);
		else {
			digit(n / 10);
			list.add((n % 10));
		}
		return list;
	}
}

三、汉若塔问题

汉若塔问题：设A，B，C是三个塔座，在塔A上叠有n个圆盘，这些圆盘自上而下，由大到小的叠在一起。各圆盘从小到大编号为1,2，3···，n，现要求将塔座A上的这一叠圆盘移到塔座B上，每次移动一个，不能将大的放小的圆盘上。

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		char A, B, C;
		hanoi(n, 'A', 'B', 'C');

	}

	private static void hanoi(int n, char A, char B, char C) {
		if (n == 1) {
			System.out.printf("Move disk %d from %c to %c\n", n, A, C);
		} else {
			hanoi(n - 1, A, C, B);
			System.out.printf("Move disk %d from %c to %c\n", n, A, C);
			hanoi(n - 1, B, A, C);
		}
	}

}

C语言 递归法求阶乘

利用一个函数进行递归求阶乘，但该数不能小于0，且若为0或1，得到的结果都为1，其他情况，对该数不断递归

#include <stdio.h>
#include <stdlib.h>
int main()
{
	int fac(int n);              // 函数声明
	int n;             //声明要阶乘的数为int型
	int y;             //声明结果为int型
	printf("Please input an integer numbers:");
	scanf("%d",&n);              // 输入要阶乘的数
	y=fac(n);
	printf("%d!=%d\n",n,y);
	system("pause");
	return 0;
}

int fac(int n)                // 定义fac函数
{
	int f;
	if(n<0)                     // n不能小于0
		printf("n<0,data error!");
	else if( n==0 || n==1)         // n=0 or n=1 ，阶乘都为1
		f=1;
	else f=fac(n-1)*n;           // n>1时，n!=n*(n-1)
	return(f);
}
//递归法求阶乘

递归法判断素数

#include <stdio.h>
int fun(int n,int i){
	//相当于for循环的那一环节 
	if(i == n-1){
		return 1;
	}
	if(n%i == 0){
		return 0;
	}
	fun(n,i+1);
}
int isprim(int n){ 
	if(n<2){
		return 0;
	}
	if(n==2 || n==3){
		return 1;
	}
	return fun(n,2);
} 

int main(){
	printf("%d",isprim(8));
	return 0;
}