递归10小题

注：操作数字的数组均为int [ ]型，操作字符串均为char [ ]型
下面的10个问题很常见，在这里都是用递归解决的。涉及到数组的问题，需要有指针的知识。

1.求1到n的和

int getSum(int n)//求1到n的和
{if(n==1){return 1;}return n+getSum(n-1);	
}

2.遍历数组

void traverseArray(int * array,int length)
{if(length==1)//length是数组的长度,用来控制递归的深度以及结束递归{cout<<*array<<endl;//用length==1结束递归，只是为了遍历数组尾元素时不带逗号，美观一点return;}cout<<*array<<",";//依次遍历数组中的每个元素traverseArray(array+1,length-1);//
}

3.为数组的每个元素赋值

void inputForArray(int * array,int length)//给出数组首地址和数组长度
{if(length==0){return;}cin>>*array;inputForArray(array+1,length-1);
}

4.逆序遍历数组

例：数组[10,3,9,26,93,94]
输出:94,93,26,9,3,10

void traverseReversely(int * array,int length)
{if(length==1){cout<<array[length-1]<<endl;;return;}cout<<array[length-1]<<",";traverseReversely(array,length-1);		
}

5.颠倒数组中的元素

例：
原数组 [10,3,9,26,93,94]
颠倒后的数组 [94,93,26,9,3,10]

void reverse(int * array,int length)
{if(length==0 || length==1){return;}int temporary=array[0];array[0]=array[length-1];array[length-1]=temporary;reverse(array+1,length-2);
}

也可以是这样的递归

void reverse(int * array,int length)
{if(length==0 || length==1){return;}reverse(array+1,length-2);int temporary=array[0];array[0]=array[length-1];array[length-1]=temporary;
}

6.求出数组中的最大值

int getMaximum(int * array,int length)
{if(length==1){return *array;}int maximum;//避免二次调用getMaximum函数maximum=*array>(maximum=getMaximum(array+1,length-1))?*array:maximum;return maximum;
}

7.输入一个整数n(n>0)，将其逆序输出

例：n=12345，输出为54321

void reveal(long number)
{if(number<=9)//当number变成一位数时，即刻输出number，结束递归{cout<<number<<endl;return;}cout<<number%10;//不断对10取余，输出个位数reveal(number/10);
}

8.字符串翻转

例：
输入 “IAmIronMan”
输出 “naMnorImAI”

void traverseStringReversely0(char * source)
{if(!*source)//if(!*source)、if(*source=='\0')、if(*source==0)三者意思相同{return;}traverseStringReversely0(source+1);cout<<*source;
}void traverseStringReversely(char * source)//在主程序中调用它
{traverseStringReversely0(source);//递归函数中缺少换行cout<<endl;//在这个函数中单独加上
}

9.任意输入一个整数n(n>0),将其输出为二进制形式

输入：6
输出：110

void transform(int number)
{if(number==0){return;}transform(number/2);cout<<number%2;
}

10.求100到999之间的水仙花数

int isDaffodilNumber(int number)	//number>=100 且 number<1000 判断number是不是水仙花数
{if(number>9){int one=number%10;one=one*one*one+isDaffodilNumber(number/10);return one;//返回各个位立方之后的和,若和与number相等，则为水仙花数，否则非水仙花数}else{return number*number*number;}}//主函数中调用getDaffodilNumber
void getDaffodilNumber(int begin,int end) //begin>=100,end>=100,begin>end
{										//给定三位数的范围，begin最小为100，end最大为1000if(begin>end){return;			}if(isDaffodilNumber(begin)==begin){cout<<begin<<endl;}getDaffodilNumber(begin+1,end);
}