初学递归算法及常见例题

递归：

就是函数调用自己的编程技巧

人理解迭代，神理解递归。

递归的两个必要条件

1、存在限制条件，当满足这个条件时，递归便不再继续。

2、每次递归调用之后越来越接近这个限制条件。

注：满足这两个条件的递归也不一定就完全正确，但是不满足这两条件一定错误！！！！

例题：1.递归和非递归分别实现求第n个斐波那契数。

(对于求斐波那契数此问来说，递归并不是最好的方法，原因是计算量太大！)

#include<stdio.h>
int fib(int n);
int main()
{
    int n;
    scanf("%d",&n);
    int f = fib(n);
    printf("%d",f);

    return 0;
}

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

下面我们用循环试试

#include<stdio.h>
int fib(int n);
int main()
{
    int n = 0;
    scanf("%d", &n);
    int f = fib(n);
    printf("%d",f);
    return 0;
}
int fib(int n)
{
    int a = 1;
    int b = 1;
    int c = 1;
    while (n > 2)
    {
        c = a + b;
        a = b;
        b = c;
        n--;
    }
    return c;
}      

例题2.编写一个函数实现n^k，使用递归实现

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

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

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

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

#include<stdio.h>
int len(char* a);
int main()
{
    char a[] = "hello";
    int c = len(a);
    printf("%d", c);
    return 0;
}
int len(char* n)//n是指向首元素地址的
{
    if (*n != '\0')
    return 1+len(n+1);//如果首元素不是\0则剥离一个1出来并使指针向后移动一位。
    return 0;
}      

#include<stdio.h>
void print(int n);
int main()
{
    int n;
    scanf("%d",&n);
    print(n);
    return 0;

}
void print(int n)
{
    if (n == 0)
        return;
    print(n / 10);
    printf("%d\n", n % 10);
}