5. Function recursion exercise

Catalog

TEXT 1 Recursively print each bit of an integer

TEXT 2 Print each bit of an integer in reverse order

TEXT 3  Recursive search n（n≥1） The factorial （ Overflow is not considered ）

TEXT 4 strlen The simulation （ Recursive implementation ）

TEXT 5  Reverse string order （ Recursive implementation ）

TEXT 6  Calculate the sum of each of a number （ Recursive implementation ）

TEXT 7  Recursive implementation n Of k Power

TEXT 8  Calculate Fibonacci number

TEXT 9  Take the steps

TEXT 1 Recursively print each bit of an integer

for example ：124, Print in order 1 2 4.

Ideas ：

for example ： Set up a function print, Print 124 Every one of them . take 124 Split into print（12） And print separately 4; then 12 Split into print（1） And print separately 2;print（1） when , Judge 1 It's a single digit , Stop recursion , Print directly 1.

#include<stdio.h>

void print(int x)
{
	if (x / 10 != 0)
	{
		print(x / 10);
	}
	printf("%d ", x % 10);
}


int main()
{
    int a = 124;
	print(a);
	return 0;
}

TEXT 2 Print each bit of an integer in reverse order

for example ：124, Print in reverse order 4 2 1.

Ideas ：

Print before recursion , You can complete the reverse order printing .

#include<stdio.h>

void print(int a)
{
	if (a / 10 != 0)
	{
		printf("%d ", a % 10);
		print(a / 10);
	}
	else
		printf("%d ", a);

}
int main()
{
	int a = 124;
	print(a);
	return 0;
}

TEXT 3  Recursive search n（n≥1） The factorial （ Overflow is not considered ）

Ideas ：

for example ：4！ Split into ： seek 3！ and *4;3！ Split into ：2！ and *3;2！ Split into 1！ and *2; When n=1 when , Stop recursion .

#include<stdio.h>
int fac(unsigned int n)
{
	int sum = 1;
	if (n > 1)
	{
	   sum=fac(n - 1);
	}
	sum *= n;
	return sum ;
}

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

TEXT 4 strlen The simulation （ Recursive implementation ）

strlen You can find the length of the string , The result does not contain a terminator ‘\0’. Create a function , simulation strlen The function of .

Ideas ：

We set up a function simulation strlen when , When the string reads ‘\0’ when , End of the iteration .

for example ： Find string “abc” The length of , It can be divided into ：1+ character string “bc” The length of ; Find string “bc” The length of is divided into ：1+ Find string “c” The length of ; Find string “c” The length of is divided into ：1+‘\0’; encounter ‘\0’ Stop recursion .

#include<stdio.h>

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

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

TEXT 5  Reverse string order （ Recursive implementation ）

Write a function reverse_string(char * string)（ Recursive implementation ）// Only one parameter can be passed

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

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

Ideas ：

Reverse string , It can be understood that the 1 Characters and last 1 Character exchange , The first 2 Exchange with the penultimate ...... When the remaining characters in the middle are 1 when , Stop iterating .

  The specific operation of the exchange process ：

#include<stdio.h>

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

   void  reverse(char* arr)
   {
	   char temp = 0;// Temporary variable , Storage a Value 
	   int left = 0;
	   int right = my_strlen(arr) - 1;
	   temp = *arr;
	   *arr = *(arr + right);// Assign the following value to the front 
	   *(arr + right) = '\0';// Turn the last one into '\0'
	   if (my_strlen(arr + 1) > 1)
	   {
		   reverse(arr + 1);
	   }
	   *(arr + right) = temp;// Set the value in the temporary variable , Assign to the back 
   }

   int main()
   {
	   char arr[] = "abcdef";
	   reverse(arr);
	   printf("%s\n", arr);
   }

  Because the problem requires that the function can only pass one parameter , So you need to create many temporary variables .

TEXT 6  Calculate the sum of each of a number （ Recursive implementation ）

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(153), You should go back to 1 + 5 + 3, Its sum is 9

Input ：153, Output ：9

Ideas ：

153 Split into 15 and +3;15 Split into 1 and +5;1 Is each digit , Stop recursion , return 1.

#include<stdio.h>

int DigitSum(n)
{
	int sum = 0;
	if (n / 10 != 0)
	{
		sum =DigitSum(n / 10);
	}
	return sum += n % 10;
}

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

	return 0;
}

TEXT 7  Recursive implementation n Of k Power

Utilization function pow（n,k） You can ask for n Of k Power ,pow The use of the function needs to include the header file <math.h>.

Now write a function implementation n Of k Power , Use recursion to implement .

Ideas ：

Need to take into account k Value range of

#include<stdio.h>

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


int main()
{
	double n = 0.0;
	int k = 0;
	scanf("%lf%d", &n, &k);
	printf("%g\n", my_pow(n, k));//%g, Omit meaningless when printing floating-point numbers 0

	return 0;
}

TEXT 8  Calculate Fibonacci number

Fibonacci number ：1、1、2、3、5、8、13、21、34、56...... Start with the third item , The value of each term is equal to the sum of the first two terms .

Ideas ：

For example, when n=5 when , The first 5 Fibonacci Numbers = The fourth Fibonacci number （n-1）+ The third Fibonacci number （n-2）

The fourth Fibonacci number = The third Fibonacci number （n-2）+ The second Fibonacci number （n-3）

The third Fibonacci number = The second Fibonacci number 1+ The first Fibonacci number 1.

 

#include<stdio.h>

int fibo(int n)
{
	if (n > 2)
		return fibo(n - 1) + fibo(n - 2);
	else
		return 1;
}


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

TEXT 9  Take the steps

n Steps , You can choose to go one step or two steps at a time , So how many ways to walk ？（1≤n≤30）

Ideas ：

When n=1 when , There must be only one way ; When n=2 when , There are two ways ; And so on , When n>2 when , Then there is （n-1）+（n-2） Seed walking method .

#include<stdio.h>

int sum(int n)
{
	if (n > 2)
		return sum(n - 1) + sum(n - 2);
	else if (n == 2)
		return 2;
	else
		return 1;
}

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