C language exercises (recursion)

Catalog

1. Accept an integer value （ Unsigned ）, Print each bit of it in order .

2. Writing functions does not allow the creation of temporary variables , Find the length of the string .

3. seek n The factorial .（ Don't think about spillovers ）

4. Please n Fibonacci Numbers .（ Don't think about spillovers ）

5. Write a function reverse_string(char * str)（ Recursive implementation ）

6. Write a recursive function DigitSum(n), Enter a non negative integer , Returns the sum of the numbers that make up it

7. Write a function to implement n Of k Power , Use recursion to implement .

---

1. Accept an integer value （ Unsigned ）, Print each bit of it in order .

for example ：
Input ：1234, Output 1 2 3 4

Ideas ： What we should think about is print Function can type each bit . In this way, there will be the following series of thoughts .
print（1234）
print（123）4
print（12）3 4
print（1）2 3 4

#include <stdio.h>

void print(int n)
{
	if (n > 9)
	{
		print(n/10);
	}
	printf("%d ", n % 10);


}

int main()
{
	unsigned int num = 0;
	scanf("%d", &num);//1234
	print(num);
	return 0;
}

2. Writing functions does not allow the creation of temporary variables , Find the length of the string .

Our function requires string length every time , The parameter passed in is only the first address of the character array , Then we will calculate the length of the first character , Then recurse one by one . 

my_strlen("abcd")
1 + my_strlen("bcd")
1+1+my_strlen("cd")
1+1+1+my_strlen("d")
1+1+1+1+my_strlen("")

int my_strlen(char* str)
{
	if (*str != '\0')
	{
		return 1 + my_strlen(str+1);
	}
	else
		return 0;
}

int main()
{
	char arr[] = "abcd";
	int len = my_strlen(arr);
	//len = strlen(arr);
	printf("%d\n", len);
	
	return 0;
}

3. seek n The factorial .（ Don't think about spillovers ）

Ideas ：n The factorial = n*(n-1)*(n-2)........*1; And what we define fac Functions are factorial , So as long as you n Pass in the value of .

int fac(int n)
{
	if (n <= 1)
		return 1;
	else
		return n * fac(n - 1);
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = fac(n);
	printf("%d ",ret);
	
	return 0;
}

4. Please n Fibonacci Numbers .（ Don't think about spillovers ）

Ideas ： Fibonacci sequence ：1 1 2 3 5 8 13 21 34 55...... And we can use this feature , Write a mathematical expression . Then write the code .

int fib(int n)
{
	if (n <= 2)
		return 1;
	else
		return fib(n - 1) + fib(n - 2);
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = fib(n);
	printf("%d ", ret);
	return 0;
}

5. Write a function reverse_string(char * str)（ Recursive implementation ）

Realization ： Invert the characters in the parameter string , Not in reverse order .

requirement ： Out of commission C String manipulation functions in the function library .

such as : "abcdef"   become "fedcba"

Ideas ： Every time you call  reverse_string Function , First, exchange the first and last two characters of the string , But note that the characters at the end need to be filled with characters ‘\0’, Because you want to get the end position of the new string .

#include <stdio.h>
#include <string.h>

void reverse_string(char* str)
{
	int len = strlen(str);
	char tmp = *str;
	*str = *(str + len - 1);
	*(str + len - 1) = '\0';

	if (strlen(str + 1) >= 2)
		reverse_string(str + 1);

	*(str + len - 1) = tmp;
}

int main()
{
	char arr[] = "abcdef";
	reverse_string(arr);

	printf("%s\n", arr);
	return 0;
}

6. Write a recursive function DigitSum(n), Enter a non negative integer , Returns the sum of the numbers that make up it

for example , call DigitSum(1729), You should go back to 1+7+2+9, Its sum is 19

Input ：1729, Output ：19

Ideas ： The idea is roughly the same as the first question .

#include <stdio.h>

int DigitSum(int n)
{
	if (n > 9)
    	return (n % 10) + DigitSum(n / 10);
	else
		return n;
}

int main()
{
	int num = 0;
	scanf("%d", &num);
	int ret = DigitSum(num);
	printf("%d\n", ret);
	return 0;
}

7. Write a function to implement n Of k Power , Use recursion to implement .

Ideas ： Be careful k The value of . 

double power(int n, int k)
{
	if (k > 0)
		return n * power(n,k - 1);
	else if(k == 0)
		return 1;
	else
		return 1.0 / power(n, -k);
}

int main()
{
	int n = 0;
	int k = 0;
	scanf("%d %d", &n,&k);
	double ret = power(n, k);
	printf("%.1f\n", ret);
	return 0;
}