递归类型

例题1

根据下面递归函数：调用函数Fun(2)，返回值是多少（       ）

int Fun(int n)
{if (n == 5)return 2;elsereturn 2 * Fun(n + 1);
}
A.2 B.4 C.8 D.16

【答案】 D
【分析】
1：递归解题思路就是要注意递归的限制条件，满足限制条件时递归就不再继续，且每次递归调用之后都会接近这个限制条件
2：由题目我们可以知道限制条件为n==5，当我们输入比5小的数时，n是以每次增加1的趋势接近限制条件
流程如下（第一次用画图软件，画的不是很好看）

例题2

通过用递归的方式实现求第n个斐波那契数
例如
输入：5  输出：5
输入：10， 输出：55
输入：2， 输出：1

【分析】
1：斐波那契数定义为：jack（0）=0，jack（1）=1，jack(n)=jack(n-1）+jack（n-2）（n>=2）,总之就是第n个数为n的前两个数相加的和
2：我们根据斐波那契数的定义知jack（1）=1，jack（2）=1，因为jack（0）=0所以不管，因此我们设定条件n=1和n=2时返回1（限制条件），而当n>=2是返回jack(n-1）+jack（n-2）实现递归（趋近于限制条件）
【代码】

int jack(int n)
{if (1 == n || 2 == n){return 1;}else{return jack(n - 1) + jack(n - 2);}
}
int main()
{int n = 0;scanf("%d", &n);printf("%d", jack(n));return 0;
}

例题3

编写一个函数实现n的k次方，使用递归实现

【分析】
1：根据递归我们需要限制条件，因为n在输入之后就无法改变，因此我们需要对k进行设置，即0==k时我们返回1。
2：当k大于0时我们为了让其趋近于限制条件，因此k每次递推后就需要减1
【代码】

int jack(int n, int k)
{int sum = 0;if (0 == k){sum = 1;return sum;}else if (k > 0){k = k--;sum = n * jack(n, k);return sum;}elsereturn 0;
}
int main()
{int n, k;scanf("%d %d", &n, &k);printf("%d ",jack(n, k));return 0;
}

例题4

写一个递归函数DigitSum(n)，输入一个非负整数
返回组成它的数字之和
例如，调用DigitSum(1729)，则应该返回1+7+2+9
它的和是19
输入：1729，输出：19

【分析】
1：在看到返回值为个位 十位 百位…数字时，我们一般都会用到求余（%），这样就可以将每位数单独提出来
2：因为是要用到递归，因此我们需要限制条件，即当n<10时直接返回n（个位数），而要有使递推趋近限制条件就需要用/号，这样就会把最后一位数消去
【代码】

int jack(int n)
{if (n < 10)return n;else{int sum = n % 10 + jack(n / 10);return sum;}
}
int main()
{int n = 0;scanf("%d", &n);printf("%d", jack(n));return 0;
}

例题5

递归实现求n的阶乘（不考虑溢出的问题）

【分析】
我们以n==1返回1作为限制条件，然后每次n减1
【代码】

int jack(int n)
{int sum = 0;if (n > 1){sum = n * jack(n - 1);return sum;}if (1 == n){sum = 1;return sum;}
}
int main()
{int n = 0;scanf("%d", &n);printf("%d", jack(n));return 0;
}

我们对前面的代码进行一些优化如下
【代码】

int jack(int n)
{
if(n==1)
return 1;
return n*jack(n-1);
}
int main()
{int n = 0;scanf("%d", &n);printf("%d", jack(n));return 0;
}

例题6

递归方式实现打印一个整数的每一位

【分析】
这道题和例题4几乎一样，所以就不进行分析了
【代码】

void jack(int n)
{if (n >= 0){if (n <= 9){printf("%d ", n);}else{int sum = 0;sum= n % 10;jack(n / 10);printf("%d " ,sum);}}
}
int main() 
{int n = 0;scanf("%d", &n);jack(n);return 0;
}