回 帖 发 新 帖 刷新版面

主题:递归问题求解

#include<iostream.h>
#include<string.h>

int count=1;

void rev(char *str,int n)        //递归算法;    

{    
    cout<<"递归执行第"<<count++<<"次"<<endl;
    cout<<"now n= "<<n<<endl;

    if(n<=1) return;   //判断调用函数字符串长度及如果输入的字符串为0,则返回;

    char temp=str[n-1];         //字符串翻转算法;

    str[n-1]=str[0];

    cout<<"the n= "<<n<<endl;
    
    str[0]=temp;
    
    cout<<"then n= "<<n<<endl;

    rev(str+1,n-2);    //递归调用;
}

int main()
{
    char str[100];      //定义字符串;

    cout<<"please enter string "<<endl;

    cin.get(str,100);   //调用方法输入字符串;

    rev(str,strlen(str));    //递归函数调用;
    
    cout<<"now the string is : "<<str<<endl;    //结果输出;

    return 0;    
}




问题是,为什么以上的递归函数里的n变量会每次都减少2?按常理来说n-2它是一个表达式,n的值不应该会改变。
请各位指教一下。谢谢。

回复列表 (共4个回复)

沙发

若弄清函数调用的过程,则递归调用并不难理解。
函数的参数和局部变量类似,都是有作用域的。它们在进入函数之时被创建,在离开函数之时被销毁。如果m次调用同一个函数,则同一个参数将被创建m次,并且被销毁m次。


以楼主的例子来说,n是rev这个函数的一个参数,每次rev被调用,都会创建一个参数n。并且直到这次调用完成时,这个参数n才会被销毁。
在main函数中调用了rev,此时创建了一个参数n,它的值是strlen(str)。
在rev函数中又调用了rev。为了方便,我们称呼被递归调用的这个rev为“第二个rev”,称被main调用的那个rev为“第一个rev”。此时,第一个rev的调用还没有完成(因为函数没有返回),所以它的参数还没有被销毁,一直存在着。但由于第二个rev被调用了,于是会再产生出一个n。注意这时候因为存在两个rev函数,因此也就有两个n了。
一直递归下去,就会有许许多多个n。
接下来就比较好理解,第一个rev的n减去2就是第二个rev的n。因此,输出的结果每次都少2。因此,不是“变量n每次都减少2”,而是“有许多个变量n,每一个变量n都比前一个变量n少2”。

板凳


关于递归的原理和n的值算是有点明白了,单从此递归函数来看,第一次调用时n-1是由于数组中是从0开始的那好理解,但为什么第二次递归调用的参数n要n-2,而不是n-1呢?

3 楼

这个rev函数中,n表示字符串的长度。每次递归,字符串开头和结尾各减少一个字符,所以合起来就是减2了。

4 楼

[size=3][size=2]str+1是地址指针指向前一个地址单元,而且str的下标是str+ 1,从str[0]开始,其实每次调用递归函数时都是交换剩下的没有被交换的地址单元,而且都是从str[0](剩下的没有被调换字符的都看作是str[0]开始)开始所以函数里的str[n-1]是没问题的,而n-2是因为每次丢弃两个已经交换了的字符地址的缘故,所以剩下的n是n-2?[/size][/size]

我来回复

您尚未登录,请登录后再回复。点此登录或注册