使用递归来解决一些问题

题目如下
任何一个正整数都可以用2的幂次方表示。例如：
　　　　137=2⁷⁺²3+2^0　　　　
同时约定幂次方用括号来表示，即ab 可表示为a（b）。
　　 由此可知，137可表示为：
　　　　 2（7）+2（3）+2（0）
进一步：7= 2²⁺²⁺²0 （21用2表示）
　　　　 3=2+2^0
所以最后137可表示为：
　　　　 2（2（2）+2+2（0））+2（2+2（0））+2（0）
　　 又如：
　　　　 1315=2^10 +2^8 +2^5 +2+2^0
所以1315最后可表示为：
　　 2（2（2+2（0））+2）+2（2（2+2（0）））+2（2（2）+2（0））+2+2（0）
　　输入：正整数（n≤20000）
输出：符合约定的n的0，2表示（在表示中不能有空格）
输入格式 Input Format
一个正整数
输出格式 Output Format
符合约定的n的0，2表示（在表示中不能有空格）

使用递归可以很简单的解决这个问题，如果不使用递归的话，非常难以解决。因为这个问题的内在逻辑就是递归的。
代码如下：

（当然，还附赠了另外一个问题的代码实现）

package com.edu.xust;

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

public class First {
	public static void main(String[] args) {
		ArrayList<Integer> list=new ArrayList<>();
		Scanner scan=new Scanner(System.in);
		System.out.println("输入一个非负数");
		int input=scan.nextInt();
		System.out.println("输入进制");
		int output=scan.nextInt();
		System.out.println("输入一个数");
		int flag=scan.nextInt();
		transform_feidigui(input,output,list);
		show(list);
		System.out.println();
		System.out.println("_____________________________________n"+
				"_____________________________________n");
		transform_primary(flag,0);
	}
	static void transform_feidigui(int a, int b, ArrayList<Integer> c){
		int i=0;
		while(true){
			c.add(a%b);
			a=a/b;
			if(a==0)
				break;
		}
	}
	static void show(ArrayList<Integer> c){
		for(int i=c.size()-1;i>=0;i--){
			if(c.get(i)>9)
				System.out.print((char) (c.get(i) + 55)+" ");
			else
				System.out.print(c.get(i)+" ");
		}
	}
	static void transform_digui(int a,int b,ArrayList<Integer> c){
		if(a==0)
			return;
		else{
			c.add(a%b);
			a=a/b;
			transform_digui(a,b,c);
		}
	}
	static void transform_primary(int a,int b){
		if(a==0) {
			System.out.print("0");
			return;
		}
		else{
			if(b==1)
				System.out.print("+2(");
			else
				System.out.print("2(");
			int i=0;
			while(true){
				if(a<Math.pow(2,i))
					break;
				else
					i++;
			}
			transform_primary(i-1,0);
			System.out.print(")");
			if(a-(int)Math.pow(2,i-1)>0)
				transform_primary(a - (int)Math.pow(2, i - 1),1);
		}
		System.out.print("");
	}
}

2019.6.4更新
非递归解决该问题
原算法

static void transform_primary(int a,int b){
		if(a==0) {
			System.out.print("0");
			return;
		}
		else{
			if(b==1)
				System.out.print("+2(");
			else
				System.out.print("2(");
			int i=0;
			while(true){
				if(a<Math.pow(2,i))
					break;
				else
					i++;
			}
			transform_primary(i-1,0);
			System.out.print(")");
			if(a-(int)Math.pow(2,i-1)>0)
				transform_primary(a - (int)Math.pow(2, i - 1),1);
		}
	}

非递归算法

static void transform_primary_feidigui(int a,int b){
		Stack<mynode> node=new Stack<>();
		int state=0;
		while(true){
			//System.out.println("------"+state);
			if(a==0){//返回上一级
				System.out.print("0");
				if(node.empty())
					break;
				else{//如果不是空
					a=node.peek().a;
					state=node.peek().state;
					b=node.peek().b;
					node.pop();
				}
			}
			else{
				int i=0;
				while(true){
					if(a<Math.pow(2,i))
						break;
					else
						i++;
				}
				if(state==0) {
					if (b == 1)
						System.out.print("+2(");
					else
						System.out.print("2(");
						node.push(new mynode(a, 1, b));
						a = i - 1;
						state = 0;
						b = 0;
				}
				else if(state==1){
					System.out.print(")");
					//node.push(new mynode(a, 2, b));
					if(a-(int)Math.pow(2,i-1)>0){
						node.push(new mynode(a, 2, b));
						a=a-(int)Math.pow(2,i-1);
						state=0;
						b=1;
						continue;
					}
						if(node.empty())
							break;
						else{
							a=node.peek().a;
							state=node.peek().state;
							b=node.peek().b;
							node.pop();
						}
				}
				else if(state==2){
					if(node.empty())
						break;
					else{
						a=node.peek().a;
						state=node.peek().state;
						b=node.peek().b;
						node.pop();
					}
				}
			}
		}
	}

使用到的类

class mynode{
	int a=0;
	int state=0;
	int b=0;
	public mynode(int a,int state,int b){
		this.a=a;
		this.b=b;
		this.state=state;
	}
	public mynode(){}
}

感想：没事不要瞎搞非递归，没事找事

最后

以上就是超级网络为你收集整理的使用递归来解决一些问题的全部内容，希望文章能够帮你解决使用递归来解决一些问题所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。