C Recursive Function-CodePudding

I am student who just learned c not long ago. I have a doubt in mind, for the linked list code below, I don't quite understand the logics behind it, why does the function when it reaches return, it will continue to execute the func1() and cout command ? Isn't it whenever a the programs reaches return it will automatically exits the function and ignore the rest of the blocks below ?

#include <iostream>
using namespace std;

// Creating a node
class Node {
public:
    string value;
    Node* next;
};

void func1(Node* head) {
    if (head == NULL)
    {
        return;
    }
    cout << " " << head->value;
    func1(head->next);


}

int main() {
    Node* head;
    Node* one = NULL;
    Node* two = NULL;
    Node* three = NULL;

    // allocate 3 nodes in the heap
    one = new Node();
    two = new Node();
    three = new Node();

    // Assign value values
    one->value = "A";
    two->value = "B";
    three->value = "C";

    // Connect nodes
    one->next = two;
    two->next = three;
    three->next = NULL;

    func1(one);
    return 0;
}

CodePudding user response：

Let's see what is happening behind the scenes. Example; Linked List: head -> A -> B -> C -> NULL;

void func1(Node* head) {
    if (head == NULL)
    {
        return;
    }
    cout << " " << head->value;
    func1(head->next);
}

Iteration 1: Head is Not NULL, So it its prints A, now it called func1(head->next) recursively.

Iteration 2: Head is Not NULL, So it its prints B, now it called func1(head->next) recursively.

Iteration 3: Head is Not NULL, So it its prints C, now it called func1(head->next) recursively.

Iteration 4: Head is NULL, So it it returned from the function and you got the output as A B C.

Scenario 2: Suppose you first write the recursive call and then the print statement head will first reach the end and from then it will print. So the output will be C B A

void func1(Node* head) {
    if (head == NULL)
    {
        return;
    }
    
    func1(head->next);
    cout << " " << head->value;
}

CodePudding user response：

why does the function when it reaches return, it will continue to execute the func1() and cout command ?

Only if the if condition is not satisfied, the commands func1() and cout will be executed. On the other hand if the if condition is satisfied, return will be executed and func1() and cout will not be executed.

Look at the below example for more clarification:

#include <iostream>
void func()
{
    std::cout<<5<<std::endl;
    if(1> 0)
    {
        return ;
    }
    std::cout<<6<<std::endl;
}
int main()
{
    func();
}

Because 1 is greater than 0, the if condition is satisfied and the return will be executed but cout<<6; will not be executed.

Now in your example code, you have

if (head == NULL)

this means only if the head pointer is NULL the if will be satisfied and the return will be executed but func1() and cout will not be executed. On the other hand, if the head pointer is not NULL then the if is not satisfied and so the return will not be executed but the func1() and cout will be executed.

CodePudding user response：

At a certain point in your program, there are 4 invocations of func1 that are "in progress", with different values for the head parameter in each.

The explicit return is reached only in the last invocation. Then previous invocation continues, and it reaches the end }, which is an implicit return.

Because nothing happens after the recursive call, we call that tail recursion. That kind of recursion is equivalent to a loop.

void func1(Node* head) {
    while (head != NULL)
    {
        std::cout << " " << head->value;
        head = head->next;
    }
}