链表递归函数

Question

给你一个链表1->2->3->4->5->6->NULL。为什么输出为1 3 5 5 3 1。我很困惑，请解释一下逻辑。

void fun(struct node *start){
    if(start==NULL){
        return;
    }
    printf("%d",start->data);
    if(start->next!=NULL)
        fun(start->next->next);
    print("%d",start->data);
}

Answer 1

如果您“在脑海中”执行它，您可以在伪代码中看到它。

fun([1,2,3,4,5,6,NULL])=> //Call fun with list
print(1) //Print 1
fun([3,4,5,6,NULL])=>
print(3)
fun([5,6,NULL])=>
print(5)
fun([NULL])=>
<Do nothing as its next element is equals NULL>
return from fun
print(5)
return from fun
print(3)
return from fun
print(1)

Answer 2

对于初学者来说，函数不正确。当节点数不是偶数时，它可以调用未定义的行为。因为在这个表达式中

start->next->next

子表达式

start->next

可以已经等于NULL。

函数可以这样定义

void fun( const struct node *start )
{
    if ( start )
    {
        printf( "%d ",start->data );
        
        if ( start->next && start->next->next ) 
        {
            fun( start->next->next );    
        }
        
        printf( "%d ",start->data );
    }
}

或以下方式

void fun( const struct node *start )
{
    if ( start )
    {
        printf( "%d ",start->data );
        
        if ( start->next ) 
        {
            fun( start->next->next );    
        }
        
        printf( "%d ",start->data );
    }
}

If 注释 if 语句然后函数两次调用同一节点的函数 printf

void fun( const struct node *start )
{
    if ( start )
    {
        printf( "%d ",start->data );

        /*            
        if ( start->next && start->next->next ) 
        {
            fun(start->next->next);    
        }
        */

        printf( "%d ",start->data );
    }
}

所以在第一次调用时输出

1 1

但是如果要取消对 if 语句的注释，那么在 printf 的第一次和第二次调用之间，该函数会使用指向 next->next 节点的指针调用自身。

所以你可以这样写

1 3 3 1

以此类推

1 3 5 5 3 1
     ^
     |

在值为 5 的节点之后，指向下一个节点的指针等于 NULL。所以在这两次调用 printf

之间

printf( "%d ",start->data );
//...
printf( "%d ",start->data );

在函数中，当 start->data 等于 5 时，不会输出任何内容。

链表递归函数

Linked List Recursive Function

c

recursion

linked-list

singly-linked-list

function-definition