Ç遞歸函數

Question

我有這樣的代碼：

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


int func(int n0, int n); 

int main() 
{ 
    int n0, n, nFinal=0; 
    printf ("Enter constant (n0): "); 
    scanf ("%d", &n0); 
    printf ("Enter the number of iteractions (n): "); 
    scanf ("%d", &n); 
    nFinal = func(n0, n); 
    printf ("nFinal after %d iteractions is %d: \n", n, nFinal); 
    return 0; 
} 

int func(int n0, int n){ 
    int i,nFinal=0; 

    for (i = 0; i < n; i++){ 
     nFinal = (nFinal*nFinal) + n0; 
    } 

    return nFinal; 
} 

的nFinal被內計算環路。我想達到相同的結果，但做一個遞歸函數。

從我看到的，我不能改變函數調用，因爲我總是需要開始數和迭代次數。因此，在第一次迭代之後，程序將不得不再次調用nFinal = func (n0, n);，但正如我在nFinal的計算值的每次迭代中所需要的那樣，我將不得不改變這一點。

是否可以做一個遞歸函數，但保持nFinal = func (n0, n);的功能？

有人能指點我嗎？

Answer 1

看你的功能

int func(int n0, int n){ 
    int i,nFinal=0; 

    for (i = 0; i < n; i++){ 
     nFinal = (nFinal*nFinal) + n0; 
    } 

    return nFinal; 
} 

如果n（小於）0，你的結果是0。然後nFinal的新值nFinal的舊值^ 2 + N0，讓您得到：

int func(int n0, int n){ 
    if (n <= 0) return 0; 

    int f = func(n0, n-1); 
    return f*f + n0; 
} 

Answer 2

我認爲你正在尋找這樣的：

int func(int n0, int n){ 
    if (n > 1){ 
     int nFinal = func(n0, --n); 
     return (nFinal*nFinal) + n0; 
    } 
    return n0; // (0*0) + n0 
} 

注意if (n == 1)返回n0，否則它會調用func，在nFinal保存它的返回值，並返回(nFinal*nFinal) + n0。

對於n == 0，此功能的等效版本也可以自行調用n == 1和return 0。

Answer 3

在每次迭代中，您對原始值（和參數）進行一些數學計算，然後存儲它。你有兩個關於如何遞歸的廣泛選擇。

1. 是否所有的迭代n-1，然後再返回之前做一些關於它的更多的數學。這似乎是使它遞歸的更自然的第一步。

2. 先執行此迭代的數學計算，然後將結果傳遞給遞歸調用以完成剩餘的計算。這是尾遞歸（除非n會變得非常大，並且您知道您的編譯器會優化它以節省堆棧空間，否則這不太重要）;-)。

遞歸就像數學歸納。你需要考慮你的基本情況和你的歸納步驟。在你的功能，你的基本情況是這樣的：

• 如果n = 0，然後func(n0, n)回報0。

而且你的步驟是：

• func(n0, n)回報func(n0,n-1) * func(n0,n-1) + n0。 （您可以調用該函數一次並將其保存到本地變量。）

這轉換爲標準的if-else結構。看看你是否能夠理解這一點，如果你卡住讓我知道。

Answer 4

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

int func_r(int n0, int n, int acc); 

int main(){ 
    int n0, n, nFinal; 
    printf ("Enter constant (n0): "); 
    scanf ("%d", &n0); 
    printf ("Enter the number of iteractions (n): "); 
    scanf ("%d", &n); 
    nFinal = func_r(n0, n, 0); 
    printf ("nFinal after %d iteractions is %d: \n", n, nFinal); 
    return 0; 
} 

int func_r(int n0, int n, int acc){ 
    if(n == 0) 
     return acc; 
    return func_r(n0, n-1, acc*acc + n0); 
}