递归算法
一个直接调用自己或通过一系列的调用语句间接地调用自己的函数,称为递归函数。递归算法是把问题转化为规模缩小了的同类问题的子问题。然后递归调用函数（或过程）来表示问题的解。（说明：递归算法往往效率低下，所以能不使用时就尽量不要用，以下所论递归程序只是为了说明问题，以便于理解递归的原理。对于这些问题，其实可以使用更高效的方法来解决的）（ 对于今天自己写的这篇文章，一点都不满意，因为递归算法效率往往是低下的，在花时间分析递归好像是在浪费时间。但是这么说也有点片面，因为毕竟在很多条件下，利用递归法会使用问题的分析变得简单得多。而且从递归程序到非递归程序的转换，已有成熟的形式化方法。这也许是能够安慰我的唯一理由吧 ）
递归算法的特点
(1) 递归就是在过程或函数里调用自身。
(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。
(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。
(4) 在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以使用递归时要小心。
递归算法要求
要使用递归算法来解决的问题应该满足以下三个条件：
(1)每次调用在规模上都有所缩小(通常是减半)；
(2)相邻两次重复调用之间有紧密的联系，前一次要为后一次做准备(通常前一次的输出就作为后一次的输入)；
(3)在问题的规模很小时必须直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的(以规模未达到直接解答的大小为条件)，无条件递归调用将会成为死循环而不能正常结束。
栈的作用：
当一个运行中的函数调用另一个函数时，在运行被调函数前，系统要完成3件事：
（1）将所有的实在参数、返回地址等信息传递给被调用函数保存；
（2）为被调用函数的局部变量分配存储区；
（3）将控制转移到被调函数的入口。
同样地从被调函数返回调用函数之前，系统也要先完成3件事：
（1）保存被调用函数的计算结果；
（2）释放被调函数的数据区；
（3）按照被调函数保存的返回地址将控制转移到调用函数。
当有多个函数构成嵌套调用时，按照后调用先返回的原则，函数之间的信息传递和控制转移必须通过栈来实现。系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区，每当从一个函数退出时，就释放它的存储区，当前正在运行的函数的数据区必须在栈顶。递归函数的运行过程类似于多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数。
递归算法应用实例：
1. 十进制转换成二进制的递归实现
C语言实现:
#include<stdio.h>
void conversion(int num)//十进制转换成二进制的函数,递归函数
{
if(num/2 > 0)
{
conversion(num/2);
printf("%d", num%2);
}
else
{
printf("%d", num);
}
}
void main()
{
int num, temp;
printf("请输入一个十进制数:");
scanf("%d", &num);
if(num < 0)
{
temp = -num;
printf("\n%d 转换成二进制数后的值为: -", num);
}
else
{
temp = num;
printf("\n%d 转换成二进制数后的值为: ", num);
}
conversion(temp);
printf("\n\n");
}
下面对这个程序的功能进行简单的扩充，使它能够将十进制数转换成16进制以内的数：
#include<stdio.h>
void conversion(int num, int n)
{
int pt;
if(num/n > 0)
{
conversion(num/n, n);
pt = num%n;
switch(pt)
{
case 15:printf("F");break;
case 14:printf("E");break;
case 13:printf("D");break;
case 12:printf("C");break;
case 11:printf("B");break;
case 10:printf("A");break;
default:printf("%d", pt);
}
}
else
{
printf("%d", num);
}
}
void main()
{
int num, n, temp;
printf("请输入一个十进制数:");
scanf("%d", &num);
printf("\n您想把它转换成几进制数(最高为16进制),输入:");
scanf("%d", &n);
if(num < 0)
{
temp = -num;
printf("\n%d 转换成 %d 进制数后的值为: -", num, n);
}
else
{
temp = num;
printf("\n%d 转换成 %d 进制数后的值为: ", num, n);
}
conversion(temp, n);
printf("\n\n");
}
十进制转换成二进制的递归实现(Java版)
import java.util.Scanner;
public class Conversion {
public static void main(String[] args){
int temp;
Scanner input = new Scanner(System.in);
System.out.print("请输入一个十进制数:");
int num = input.nextInt();
System.out.print("\n您想把它转换成几进制数(最高为16进制),输入:");
int n = input.nextInt();
if(num < 0){
temp = -num;
System.out.print("\n" + num + "转换成 " + n + "进制数后的值为: -");
}else{
temp = num;
System.out.print("\n" + num + "转换成 " + n + "进制数后的值为: ");
}
conversion(temp, n);
System.out.println("\n");
}
static void conversion(int num, int n){
if(num/n > 0){
conversion(num/n, n);
int pt = num % n;
switch(pt){
case 15:System.out.print("F");break;
case 14:System.out.print("E");break;
case 13:System.out.print("D");break;
case 12:System.out.print("C");break;
case 11:System.out.print("B");break;
case 10:System.out.print("A");break;
default:System.out.print(pt);
}
}else{
System.out.print(num);
}
}
}
2. 最大公约数(Greatest common divisor)
(1)最大公约数的非递归实现(C语言版)
#include<stdio.h>
void main()//求整数m,n的最大公约数
{
int m, n, temp;
printf("请输入两个整数:");
scanf("%d,%d", &m, &n);
if(m < n)
{
temp = m;
m = n;
n = temp;
}
while((temp = m % n) != 0)//利用辗转相除法求m,n的最大公约数
{
m = n;
n = temp;
}
printf("\n所求两数的最大公约数为: %d\n\n", n);
}
(2)下面让我们来利用递归的方法再来求整数m,n的最大公约数,体验一下递归算法在此的应用
C语言版
#include<stdio.h>
int gcd(int m, int n)//递归函数,用于求整数m,n的最大公约数
{
int temp = m % n;
if(temp != 0)
{
return gcd(n, temp);
}
else//当求到最大公约数,才返回n
{
return n;
}
}
void main()
{
int m, n, temp;
printf("请输入两个整数:");
scanf("%d,%d", &m, &n);
if(m < n)
{
temp = m;
m = n;
n = temp;
}
temp = gcd(m, n);
printf("\n所求两数的最大公约数为: %d\n\n", temp);
}
求最大公约数(Java版)
import java.util.Scanner;
public class Gcd{
public static void main(String[] args){
Scanner input = new Scanner(System.in);
System.out.print("请输入第一个整数:");
int m = input.nextInt();
System.out.print("请输入第二个整数:");
int n = input.nextInt();
if(m < n){
int temp = m;
m = n;
n = temp;
}
System.out.println("所求最大公约数为: " + gcd(m, n));
}
static int gcd(int m, int n){
int temp = m % n;
if(temp != 0){
return gcd(n, temp);
}
else
{
return n;
}
}
}
3. 在n个元素中找出最大元素和最小元素
(1)采用直接比较法找出最大最小数(C语言版)
#include<stdio.h>
void maxminNum(int arr[], int n, int &max, int &min)//采用直接比较法找出最大最小数
{
int i;
max = min = arr[0];
for(i = 2; i < n; i++)
{
if(arr[i] > max)
{
max = arr[i];
}
if(arr[i] < min)
{
min = arr[i];
}
}
}
void main()
{
int max, min;
int arr[12] = {10, 12, 32, 8, 45, 15, 36, 24, 42, 28, 81, 56};
maxminNum(arr, 12, max, min);
printf("最大数为: %d 最小数为: %d\n\n", max, min);
}
对于长度为 n 的序列, 此种算法的时间复杂度为O(n)
(2)采用分治的思想, 如果数组大小为 1 则可以直接给出结果，如果大小为 2则一次比较即可得出结果，于是得出到求解该问题的子问题即: 数组大小 <= 2。到此我们就可以进行分治运算了，只要求解的问题数组长度比 2 大就继续分治，否则求解子问题的解并更新全局解。(当然，对于此题用递归来实现，效率低下，但是本人只是为了说明如何使用递归的问题)
#include<stdio.h>
void maxminNum(int s, int e, int *pt, int &max, int &min)
{
/*
* s 当前递归(分治)段的开始下标，e 当前递归(分治)段的结束下标，pt 数组的地址，
* max 存储当前搜索到的最大值，min 存储当前搜索到的最小值
*/
int i;
if(e - s <= 1)//
{
if(pt[s] > pt[e])
{
if(pt[s] > max)max = pt[s];
if(pt[e] < min)min = pt[e];
}
else
{
if(pt[e] > max)max = pt[e];
if(pt[s] < min)min = pt[s];
}
return;
}
else/* 不是子问题继续分治 */
{
i = s + (e - s)/2;
maxminNum(s, i, pt, max, min);
maxminNum(i + 1, e, pt, max, min);
}
}
void main()
{
int max, min;
int arr[12] = {88, 12, 32, 8, 45, 15, -21, 24, 42, 28, 81, -99};
max = min = arr[0];
maxminNum(0, 12, arr, max, min);/* 递归(分治)法获取最值 */
printf("最大数为: %d 最小数为: %d\n\n", max, min);
}