递归实现链表：全局变量temp的递归赋值存储位置疑问

递归相关疑问 #

我不擅长递归，尝试用递归实现链表，现存在递归相关疑问：
假设有全局变量node* temp（地址为0x1）执行= rec_function();（调用1），若后续递归调用中temp的地址变为0x2，请问调用1的返回值会存储在0x1还是0x2？

相关代码 #

递归实现链表代码 #

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

typedef struct node{
    char* data ;
    struct node* ptr ;
}node;
node* list = NULL ;
node* temp = NULL ;

node* create_stacked_list(int argc ,char* argv[]){
    int i = 0;
    if(argc == 2 ){
        temp = malloc(sizeof(node));
        list = temp ;
        (*list).ptr = NULL ;
        (*list).data = argv[1] ;
        return list ;
     }
     else{
         temp = malloc(sizeof(node)) ;
         (*temp).data = argv[argc -1 ] ;
         argv[argc - 1 ] = NULL ;
         argc-- ;
         if(i==0) {list = temp ;}

         temp -> ptr = create_stacked_list(argc ,argv);
         printf("line28");
         //list = temp ;
         return list ;
    }
    i++;
};

int main(int argc , char * argv[]){
    //format :elements in list as a stack ;
    //create the list ;

    list = create_stacked_list(argc,argv) ;
    node* ptr = (*list).ptr ;
    while ( ptr != NULL ) {
        printf("%s\n" , (*(ptr)).data);
        printf("%p \n" , ptr );
        ptr = (*ptr).ptr;
    }
}

双向链表代码 #

#include<stdio.h>
#include<stddef.h>
#include<stdlib.h>
//define a node
typedef struct dllnode{
    int val ;
    struct dllnode* prev ;
    struct dllnode* next ;

}node;
//globally declare head of list
node* list = NULL ;


//create the first node
node* first_node(int val){
    list = malloc(sizeof(node));
    (*list).prev = NULL ;
    (*list).next = NULL ;
    (*list).val = val ;
    return list ;

}

//keep adding the other nodes
node* add_node(int val){
    node* temp = malloc(sizeof(node));
    (*temp).next = list ;
    (*list).prev = temp ;
    (*temp).val = val ;
    (*temp).prev = NULL ;
    list = temp ;
  
    return list ;
}

//function to print out the list
void print_out(node* node){
    while((*node).next != NULL){
        printf("%i \n" , (*node).val) ;
        node = (*node).next ;
    }
    printf("%i \n", (*node).val);
}

//function to delete an element from the list 
void delete( node* node  , int val ){
    while(node->val != val){
        node = node->next ;
    }
    
    if(node->val == val){
        (*(node->next)).prev = node->prev ;
        (*(node->prev)).next = node->next ;
        node->prev = NULL ;
        node->next = NULL ;
    }
}


//main function
int main(void) {

    int i = 1;
    printf("Enter element number %i : " , i) ;
    int val = 0 ;
    scanf("%i" , &val) ;
    first_node(val);
    i++;
    while(val != 314){
        printf("Enter element number %i : " , i) ;
        scanf("%i" , &val) ;
        if(val == 314){
            break;
        }
        add_node(val);
        i++;
    }
    
    print_out(list);
    int del ;
    printf("delete the middle number : ");
    scanf("%i" ,&del);
    delete(list ,del);
    print_out(list);
}

问题解答 #

首先要理清一个关键概念：全局变量temp自身的内存地址是固定的（你说的0x1就是它在内存中的位置），所谓“后续递归调用中temp的地址变为0x2”，实际上是temp这个指针变量存储的指向地址变成了0x2——也就是temp的值（指针指向的内存地址）改变了，而temp自己的存储地址始终不变。

针对你的问题：

• 如果调用1是temp = rec_function();，那么rec_function()的返回值会被赋值给temp变量，也就是存储在temp自身的固定地址0x1里。
• 但你的create_stacked_list函数返回的是全局变量list，所以调用1的返回值是list当前指向的地址。由于list和temp都是全局变量，递归调用中对它们的修改会直接覆盖全局状态，所有递归层级共享这些变量的值。

另外补充：我知晓上述代码仍存在诸多局限，但完成后感觉不错。

内容的提问来源于stack exchange，提问作者sa ket