递归疑难问题解答

1.计算一个数的每位之和（递归实现）

写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和

例如，调用DigitSum(1729)，则应该返回1+7+2+9，它的和是19

输入：1729，输出：19

#include <stdio.h>
int fac(int n)
{
	if (n < 10)
	{
		return n;
	}
	else
	{
		return fac(n / 10) + n % 10;
	}
}
int main()
{
	int n;
	scanf("%d", &n);
	printf("%d", fac(n));
	return 0;
}

1729
9 = 1729 % 10;
2 = 172 % 10;
7 = 17 % 10;
1 = 1 % 10;
n < 10  --->n
n >= 10 --->fac(n / 10) + n % 10; 

n=123时的分析

2.递归和非递归分别实现求n的阶乘（不考虑溢出的问题） 

递归

#include <stdio.h>
int fac(int n)
{
	if (n == 1)
	{
		return 1;
	}
	else
	{
		return n*fac(n-1);
	}
}
int main()
{
	int n;
	scanf("%d", &n);
	printf("%d", fac(n));
	return 0;
}

 n!=n*(n-1)!
n==1,1

循环

#include <stdio.h>
int fac(int n)
{
	int i, ret = 1;
	for (i = 1; i <= n; i++)
	{
		ret *= i;
	}
	return ret;
}
int main()
{
	int n;
	scanf("%d", &n);
	printf("%d", fac(n));
	return 0;
}

n = 1 * 2 * 3 * 4....*n;

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

#include <stdio.h>
void Print(int n)
{
	if (n < 10)
	{
		printf("%d ",n);
	}
	else
	{
		Print(n / 10);
		printf("%d ", n % 10);
	}
}
int main()
{
	int n;
	scanf("%d", &n);
	Print(n);
	return 0;
}