C++ Recursive Function

Question

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;
}

This is called "tail recursion". The func1(head->next) is roughly equal to head = head->next; goto top_of_function;. — David Schwartz
– David Schwartz, Commented Nov 12, 2021 at 10:41

sayantan ghosh · Accepted Answer · 2021-11-12 10:52:34Z

1

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;
}

answered Nov 12, 2021 at 10:52

sayantan ghosh

915 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

CaesarHo Over a year ago

Thanks man, I understand well now !

Richard · Accepted Answer · 2021-11-12 10:52:51Z

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.

Caleth · Accepted Answer · 2021-11-12 10:55:33Z

0

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;
    }
}

answered Nov 12, 2021 at 10:55

Caleth

66.1k2 gold badges53 silver badges101 bronze badges

Collectives™ on Stack Overflow

C++ Recursive Function

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related