Exercises of function recursion

// According to the following recursive function ： Call function Fun(2), What is the return value （ ）
int Fun(int n)      
{ 
  if(n==5)   
    return 2;     
  else     
    return 2*Fun(n+1);      
}






Fun(2)---> return 16
 return 2*Fun(3)  2*8=16
      |__Fun(3):8
         return 2*Fun(4)  2*4=8
              |__Fun(4):4
                 return 2*Fun(5) 2*2=4
                      |__Fun(5):2  
                         return 2

// Recursively print each bit of an integer 
#include<stdio.h>
void print(int n)

{

    if (n > 9)

    {

        print(n / 10);

    }

    printf("%d ", n % 10);

}

int main()

{

    int num = 0;

    scanf("%d", &num);

    print(num);

    return 0;

}


 

// Recursion and non recursion are used to calculate respectively n The factorial （ Overflow is not considered ）
#include<stdio.h>
int func(int i)
{
	if (i < 2)
	{

		return 1;
	}
	else
	{
		return i * func(i - 1);
	}
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = func(n);
	printf("%d", ret);
	return 0;
}

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

// Recursive and non recursive are implemented respectively strlen
#include<stdio.h>
//strlen The simulation （ Recursive implementation ）
int func(char* arr)
{
	if (*arr != '\0')
	{
		return 1 + func(arr + 1);
	}
	else
	{
		return 0;
	}
}
int main()
{
	char arr[] = "abcde";
	int ret=func(arr);
	printf("%d", ret);
	return 0;
}

 

#include<stdio.h>
#include<string.h>
int main()
{
	char arr[] = "abcde";
	int ret = strlen(arr);
	printf("%d", ret);
	return 0;
}

 strlen The meaning is ： Find the length of valid characters in the string , barring \0

Cycle to achieve ：

1. Give a count , Used to count the number of valid characters

2. Traversal string , As long as you don't meet \0, When a character is encountered, add... To the count 1, Until I met \0

// Write a function  reverse_string(char * string)（ 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 .
#include<stdio.h>
void reverse_string(char* arr)
{
	int len = strlen(arr);
	char tmp = *arr;
	*arr = *(arr + len - 1);

	*(arr + len - 1) = '\0';
	if (strlen(arr + 1) >= 2)
		reverse_string(arr + 1);

	*(arr + len - 1) = tmp;
}
int main()
{
	char arr[] = "abcde";
	reverse_string(arr);
	printf("%s", arr);
	return 0;
}

 

Ideas ：

Inverse string , The implementation of the loop is very simple

1. Give two pointers ,left Put to the left of the string ,right Put in the last valid character position

2. Swap characters at two pointer positions

3. left The pointer goes back ,right The pointer goes forward , As long as the two pointers don't meet , continue 2, After the two pointers meet , Reverse end

*/

void reverse_string(char* arr)

{

char *left = arr;

char *right = arr+strlen(arr)-1;

while(left<right)

{

char tmp = *left;

*left = *right;

*right = tmp;

left++;

right--;

}

}

/*

recursively ：

For strings “abcdefg”, The general principle of recursive implementation ：

1. In exchange for a and g,

2. Recursively inverts the rest of the source string , The rest can be treated as a valid string , And reverse it in a similar way

*/

void reverse_string(char* arr)

{

intlen = strlen(arr);

char tmp = *arr;

*arr = *(arr+len-1);

*(arr+len-1) = '\0';

if(strlen(arr+1)>=2)

reverse_string(arr+1);

*(arr+len-1) = tmp;

}

// 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
#include<stdio.h>
int func(int a)
{
	if (a > 9)
	{

		return a%10+func(a / 10);
	}
	else
	{
		return a;
	}
}
int main()
{
	unsigned int a = 0;
	scanf("%d", &a);
	int ret = func(a);
	printf("%d", ret);
	return 0;
}

// Write a function to implement n Of k Power , Use recursion to implement .
#include<stdio.h>
int func(int a, int b)
{
	if (b == 0)
		return 1;
	else if (b >= 1)
	{
		return a * func(a, b - 1);
	}
}
int main()
{
	int a = 0;
	int b = 0;
	scanf("%d %d", &a, &b);
	int ret = func(a, b);
	printf("%d", ret);
	return 0;
}

 

 

// Recursion and non recursion are implemented respectively n Fibonacci Numbers 
#include<stdio.h>
int func(int n)
{
	if (n <= 2)
	{
		return 1;
	}
	else 
	{
		return func(n-1) + func(n - 2);
	}
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int ret = func(n);
	printf("%d", ret);
	return 0;
}

#include<stdio.h>
int fib(int n)

{

    int result;

    int pre_result;

    int next_older_result;     

        result = pre_result = 1;

    while (n > 2)

    {
        n -= 1;

        next_older_result = pre_result;

        pre_result = result;

        result = pre_result + next_older_result;

    }

    return result;

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