使用递归函数求解字符串的逆置问题

一、递归函数概述

　　在使用面向过程的编程语言进行程序编写的过程中，一般是按照结构化的编程思想、模块化的程序设计方法来进行程序的编写和代码的组织的。我们熟悉的C语言就是这样一类程序设计语言，它通常以函数为单位进行程序的模块化组织，C源程序就是由一个主函数和若干非主函数构成的。计算机在执行C程序时，是按照顺序从主函数main()开始执行，如果遇到调用其他函数的情况，则主函数暂停执行，转而执行相应的函数，该函数执行完毕之后，返回主函数，主函数继续执行，这称为函数的调用。不仅主函数可以调用其他函数，各个函数之间也是可以相互调用的，如果一个函数自己调用自己，我们称之为函数的递归调用。在某些特殊问题的求解中，使用递归函数有时候会有非常高的效率。

　　递归（Recursion）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法，其核心思想是分治策略。递归算法适合解决以下三类问题：

数据的定义是按递归定义的。如Fibonacci函数。

问题解法按递归算法实现。如Hanoi问题。

数据的结构形式是按递归定义的。如二叉树、广义表等。

二、字符串逆置例题求解

2.1 题目描述

　　编写一个函数把字符串逆置（如字符串”abcde”变成”edcba”）。

2.2 分析求解

　　将字符串逆置，可以将第一个字符串和最后一个字符串交换，再将剩下的字符串逆置，剩下的字符串长度就在原来的长度上减2，规模以此缩小，剩下的字符串逆置方法和第一次一样，如果字符串长度≤1,则递归条件结束。程序如下：

#include<stdio.h>
//start，end为字符串开始和结束的下标
void convert_str(char *str, int start, int end){
	char ch;
	if((end - start) < 1){  // <1说明字符串 只有一个字符，无无需交换，递归结束条件
		return ;  
	}else{
	
		ch = str[start];
		str[start] = str[end];
		str[end] = ch;
        convert_str(str,start+1,end-1); //递归调用该函数，将剩下的字符串进行交换
	}
}
int main(){

		char x[] = "abcdefgh";
		convert_str(x,0,7);

		printf("字符串逆置后为: %s \n", x);

		return 0;
}

三、总结

　　1）递归的精髓在于如何把规模大的、较难解决的问题变成规模较小的、易解决的同一问题，规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。此外，还得要注意递归的终止条件，也就是递归的出口，出口条件设置错误的话，程序会无法终止，从而导致程序的崩溃。
　　2）递归的实现得益于栈这种数据结构，函数的每一次调用，都会使用栈来保存函数的参数、局部变量、返回地址等数据，因此，在使用递归的时候，一定要考虑递归的深度问题，如果过深，会容易造成栈溢出，导致问题求解失败。