Ç递归函数

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