初學遞歸算法及常見例題

遞歸：

就是函數調用自己的程式設計技巧

人了解疊代，神了解遞歸。

遞歸的兩個必要條件

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);
}