5树的递归

树的递归

尾递归

递归的优化

原理：递归本身会创造一个副本，但原先的副本未被释放，导致堆空间占用过多。

尾递归在递归的尾部调用自己，但原本函数已经结束，无需等待计算。最后一次调用的结果直接返回给初始调用。

即当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分

特点是在回归过程中不用做任何操作。

例子：

int add(int x,int sum)
{
    if(x==1)
    {
        return sum;
    }
    else
    {
        add(x-1,sum+x);
    }
}

注：尾递归是编译器的优化

之前的代码补全

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

typedef struct ChildBro{
    int key;
    struct ChildBro *child;
    struct ChildBro *sibling;
}Node;

Node *root;		//根指针

void Init(int key)
{
    root=(Node*)malloc(sizeof(Node));
    root->key=key;
    root->child=NULL;
    root->silbing=NULL;
    
}

void insert(int key,int parent)
{
    //定位结点
    
    Node* temp=get_node(parent,root);
    
    if(temp==NULL)
    {
        
    }
    else
    {
        Node*node=(Node*)malloc(sizeof(Node));
        node->key=key;
        node->child=NULL;
        node->sibling=NULL;
        if(temp->child==NULL)
        {
            temp->child=node;
        }
        else
        {
            node->sibling=temp->child;
            temp->child=node;
        }
    }
}

//递归核心代码
Node* get_node(Node* node,int key)
{
    Node* temp=NULL;
    if(node->key==key)
    {
        return node;
	}
    if(node->sibling!=NULL)
        get_node(node->sibling,key);
    if(node->child!=NULL)
        gen_node(node->child,key);
    
}

发布于 2024-11-10