欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法很美(基础递归问题)

程序员文章站 2022-04-30 13:59:16
...

递归:简单来说就是自己调用自己
问题1:利用递归求一个数的阶乘
1.找重复:求n!可以转化成n*(n-1)!---->求f(n)即求n*f(n-1)
2.找变化:变化的量应该作为参数
3.找边界(出口)----->终止条件

import java.util.*;
public class 求阶乘 {
public static void main(String[] args) {
	Scanner sc =new Scanner(System.in);
	int N=sc.nextInt();
	System.out.println(N+"的阶乘为:"+f(N));
}
//递归函数
//1.找重复:求n!可以转化成n*(n-1)!---->求f(n)即求n*f(n-1)
//2.找变化:变化的量应该作为参数
//3.找边界(出口)
private static int f(int n) {
	if(n==1)
	{
		return 1;
	}
	return n*f(n-1);
}
}

问题2:利用递归打印从i到j(i<j)
还是三步走:
1.找重复:就是把该问题划分成子问题:要打印从i到j------>先打印i然后再是i+1到j 也就是f(i,j)------>f(i-1,j)
2.找变化:变化在于i不断变大
3.找结束条件(出口):当i>j时,终止程序

import java.util.*;
public class 用递归求从i到j {
public static void main(String[] args) {
	Scanner sc =new Scanner(System.in);
	int i=sc.nextInt();
	int j=sc.nextInt();
	System.out.println("从"+i+"到"+j+"依次打印结果为");
	f(i,j);
}
//1.找重复:分解成子问题
//2.找变化:变量是i,一直往大变
//3.找边界,出口
private static void f(int i, int j) {
	// TODO Auto-generated method stub
	if(i>j)
	{
		return;
	}
	System.out.println(i);
	f(i+1,j);
}
}

问题3:翻转字符串
方法一:循环,倒置输出

import java.util.*;
public class 利用循环来翻转字符串 {
public static void main(String[] args) {
	Scanner sc =new Scanner(System.in);
	String str=sc.next();
	char []c=str.toCharArray();
	for(int i=c.length-1;i>=0;i--)
	{
		System.out.print(c[i]);
	}
}
}

方法二:利用递归思维来求解
1.找重复:每次都移动尾部“指针”,返回该下标所对应的字符
2.找变化:一直变化的量是尾部“指针”end索引,一直在前移
3.找出口(终止条件):当尾部“指针”到达最前面时,返回0处字符,再往下就是end为-1,所以终止了
算法很美(基础递归问题)

import java.util.*;
public class 利用递归翻转字符串 {
public static void main(String[] args) {
	Scanner sc =new Scanner(System.in);
	String s =sc.next();
	System.out.println("将此字符串翻转之后为"+f(s,s.length()-1));
}

private static String f(String s, int end) {
	// TODO Auto-generated method stub
	if(end==0)
	{
		return s.charAt(end)+"";
	}
	return s.charAt(end)+f(s,end-1);
}
}