以前在面试的时候偶尔遇到递归方面的程序题,最近有个朋友找工作也遇到了,看来递归在面试过程中也经常用到。递归最有名的就是斐波那契(Fibonacci)数列和汉诺塔,概念就不说了,简单的说就是自己调用自己。直接看程序,
在网上找了几个题:
1.求数组中的最大数
package com.wayne.recursion;
/**
* 采用递归(recursion)求数组中的最大数
*
* @author Administrator
*/
public class RecursionArrayMaxValue {
public static int getMaxValue(int arr[], int i) {
if (i == 1) {
return arr[i];
} else {
if (arr[i - 1] >= arr[i - 2]) {
arr[i - 2] = arr[i - 1];
return getMaxValue(arr, i - 1);
}
return getMaxValue(arr, i - 1);
}
}
}
package com.wayne.recursion;
import static org.junit.Assert.*;
import org.junit.AfterClass;
import org.junit.BeforeClass;
import org.junit.Test;
public class RecursionArrayMaxValueTest {
@BeforeClass
public static void setUpBeforeClass() throws Exception {
}
@AfterClass
public static void tearDownAfterClass() throws Exception {
}
@Test
public void testGetMaxValue() {
int arr[] = { 3, 23, 43, 23, 12, 23, 23, 43, 23, 1, 3, 54, 54 };
int max = RecursionArrayMaxValue.getMaxValue(arr, arr.length);
assertEquals(54, max);
}
}
2.1+2+3+...+n
package com.wayne.recursion;
/**
* 采用递归(recursion)求1+2+3+...+n值
*
* @author Administrator
*
*/
public class RecursionSum {
public static int getSum(int n) {
if (n == 1) {
return 1;
}
return n + getSum(n - 1);
}
}
package com.wayne.recursion;
import static org.junit.Assert.*;
import org.junit.AfterClass;
import org.junit.BeforeClass;
import org.junit.Test;
public class RecursionSumTest {
@BeforeClass
public static void setUpBeforeClass() throws Exception {
}
@AfterClass
public static void tearDownAfterClass() throws Exception {
}
@Test
public void testGetSum() {
int sum = RecursionSum.getSum(5);
assertEquals(15, sum);
}
}
3.求n个整数的积
package com.wayne.recursion;
/**
* 采用递归(recursion)求n个整数的积
*
* @author Administrator
*/
public class RecursionProduct {
public static int getProduct(int arr[], int i) {
if (i == 2) {
return arr[1] * arr[0];
}
if (i == 1) {
return arr[0];
}
arr[i - 2] = arr[i - 1] * arr[i - 2];
return getProduct(arr, i - 1);
}
}
package com.wayne.recursion;
import static org.junit.Assert.*;
import org.junit.AfterClass;
import org.junit.BeforeClass;
import org.junit.Test;
public class RecusionProductTest {
@BeforeClass
public static void setUpBeforeClass() throws Exception {
}
@AfterClass
public static void tearDownAfterClass() throws Exception {
}
@Test
public void testGetProduct() {
int arr[] = { 3, 4, 5, 3, 2 };
assertEquals(360, RecursionProduct.getProduct(arr, arr.length));
}
}
当做完几个递归后就会发现用程序实现递归找到几个入口就好写了:
1.寻找特定规律
2.确定边界(终了)条件
3.注意返回结果的控制
不过对于很多复杂的问题将其简单化用递归来设计还是挺有难度的。对于我这样的菜鸟级的就只能慢慢爬了。
分享到:
相关推荐
算法:递归入门 递归入门教程
程序设计-C and C++的实现:第6章 函数和递归入门.pdf
数据结构的递归入门,c语言版,有经典问题
函数 递归 入门 代码如下: #include using namespace std; #define qfor(n) for(i=0;i;i++) #define qw(tc) while(tc--) #define pb push_back int akm(int m,int n){ if(!(m)){ return n+1; } if(m&&!(n)){...
计算二叉树深度算法(递归、非递归)入门详解
计算二叉树深度算法(递归、非递归)入门详解 C语言实现
第4章 递归入门 4.1 一个简单的递归示例 4.2 阶乘函数 4.3 费波那契函数 4.4 其他递归示例 4.5 以递归的方式思考 4.6 小结 4.7 复习题 4.8 编程练习 第5章 递归过程 5.1 汉诺塔 5.2 产生...
C++递归课件 简单的递归思想 递归思想入门
多任务编程超入门-(8) 递归互斥量 示例工程,代码
基于VC++用递归的思想,按照经典的分形理论中的Koch曲线编写的算法,是很不错的分形程序设计的入门资料。
“递归函数”入门[归类].pdf
c#入门简单代码,适合新手,简单的递归求和实现。 主函数 static void Main(string[] args) { Class1 aa = new Class1(); Console.WriteLine("请输入待求阶乘的数:"); int n = Convert.ToInt32(Console....
大一级别简单编程之递归算法例题解答*2,适合入门级新人
java初学者
Python基础教程、Python入门教程之递归算法.doc
结构清晰地介绍了二叉树的遍历方法,附带详细的注释,希望像能对和我一样入门级的朋友们有所帮助
零基础入门深度学习(7) - 递归神经网络 - 作业部落 Cmd Markdown 编辑阅读器.pdf
递归函数论入门,罗莎培特著,莫绍揆译。内容涵盖全面,论证详细
算法竞赛入门经典授课教案第4章 函数和递归.doc