1. 递归非递归实现求斐波那契数列第n项

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

// 1 1 2 3 ...

int fib_re(int n, int last1, int last2) {
    if (n == 1 || n == 2)
        return last2;

    return fib_re(n - 1, last2, last1 + last2);
}

int fib(int n) {
    if (n == 1 || n == 2)
        return 1;

    int num1 = 1, num2 = 1;
    for (int i = 3; i <= n; i++) {
        num2 = num1 + num2;
        num1 = num2 - num1;
    }
    return num2;
}

int main() {
    printf("%d\n", fib(40));

    system("pause");
    return 0;
}

2. 递归实现n ^ k

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// n ^ k

int power(int n, int k) {
    if (k == 1)
        return n;

    return n * power(n, k - 1);
}

int main() {
    int n, k;
    printf("n ^ k 请输入n和k(n k):");
    scanf("%d %d", &n, &k);
    printf("%d\n", power(n, k));

    system("pause");
    return 0;
}

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

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int DigitSum(int num) {
    if (num < 10)
        return num;

    return num % 10 + DigitSum(num / 10);
}

int main() {
    printf("%d\n", DigitSum(1729));

    system("pause");
    return 0;
}

4. 编写一个函数 reverse_string(char * string)(递归实现)实现:将参数字符串中的字符反向排列。要求:不能使用C函数库中的字符串操作函数。

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void reverse_string(char* string) {
    if (*string == '\0')
        return;
    if (*(string + 1) == '\0')
        return;

    char* ptr = string;

    // 找到\0前的第一个元素
    while (*(ptr+1))
        ptr++;

    // 交换最后一个元素和第一个元素
    char tmp = *string;
    *string = *ptr;
    *ptr = tmp;

    // 记录下\0前一个元素,然后将它置为\0
    tmp = *ptr;
    *ptr = '\0';

    reverse_string(&string[1]);

    // \0前最后一个元素恢复原值
    *ptr = tmp;
}

int main() {
    char str[] = "Hello World";
    reverse_string(str);
    printf("%s\n", str);

    system("pause");
    return 0;
}

5. 递归非递归实现strlen

int Strlen_re(char* str) {
    if (*str == '\0')
        return 0;

    return 1 + Strlen_re(str + 1);
}

int Strlen(char* str) {
    int length = 0;

    while (*str) {
        length++;
        str++;
    }

    return length;
}

6. 递归非递归实现求n的阶乘

int factorial_re(int n) {
    if (n == 1)
        return 1;

    return n * factorial_re(n - 1);
}

int factorial(int n) {
    int res = 1;

    for (int i = 1; i <= n; i++)
        res *= i;

    return res;
}

7. 递归打印数的每一位

void print(int num) {
    if (num >= 10)
        print(num / 10);
    printf("%d\n", num % 10);
}
Last modification:November 10th, 2019 at 10:22 am