Recursion example

[bsmith]

I am new to the idea of recursion in functions. For example, I'm building a program, but I want to try changing one of the functions to use recursion (so I can learn how it really works). Below is one of my functions, which I thought may be easiest to change to recursion.

I've tried to write it as recursion, but keep getting weird results when I do.

*note:
length, views, likes, title and such things are initialized in the .h file

void songs::SongsAddNewSong(char *newTitle, double newLength, int newViews, int newLikes)
{
    songs *current = head;
    songs *newNode = new songs();
    if (current == nullptr) //if list is empty
    {
        head = newNode;
        current = newNode;
        strcpy(newNode->title,newTitle);
        newNode->length = newLength;
        newNode->views = newViews;
        newNode->likes = newLikes;
        current->next = nullptr;
    }
    else
    {
        while (current->next != nullptr) //get to end of list
        {
            current = current->next;
        }
        //reset pointers to include newNode / set newNode data
        current->next = newNode;
        newNode->next = nullptr;
        strcpy(newNode->title,newTitle);
        newNode->length = newLength;
        newNode->views = newViews;
        newNode->likes = newLikes;
    }
}

Any help in showing how this can be recursive would be great!! Thank you

[zapshe]

It's a bit difficult to make the recursive equivalent, here's what you should expect it to roughly look like:

void songs::SongsAddNewSong(char *newTitle, double newLength, int newViews, int newLikes)
{
	songs *current = head;
	songs *newNode = new songs();

	if (current != nullptr)
	{
		current->next->songs::SongsAddNewSong(newTitle, newLength, newViews, newLikes);
	}

	if (current == nullptr) //if list is empty
	{
		//head = newNode; Is this needed? current is already equal to head
		current = newNode;
		strcpy(newNode->title, newTitle);
		newNode->length = newLength;
		newNode->views = newViews;
		newNode->likes = newLikes;
		current->next = nullptr;
	}
}

The else statements messes around with current->next and newNode->next which will never happen in what I sent. Not all functions can/should be turned recursive. I'm not sure that this function is a good candidate to turn recursive. Without knowing the entire context of your code, can't know for certain. What I sent should work if the implementations you did are what I think they are.

[dutch]

That function is not a good candidate for recursion.
You could write a recursive function to find the end of the list:

Song* find_end(Song* node) // precond: node != nullptr
{
    return node->next ? find_end(node->next) : node;
}

However, there's not much point.

I'm wondering about the structure of your list, though. You should have a class for the SongList and a separate struct for the nodes. The way you have it, either head is a global variable (NOOOOOO!!!!) or perhaps a static member variable (or even worse a non-static member variable) in the node class.

An example of a better design is something like this:

#include <iostream>
using namespace std;

struct Song
{
    string title;
    int    length;
    Song*  next;
    
    Song(const string& title, int length)
      : title(title), length(length) {}
};

class SongList
{
    Song* head;
    Song* tail;   // may as well maintain a tail pointer
public:
    SongList() : head(), tail() {}
    void append(string title, int length)
    {
        Song* newSong = new Song(title, length);
        if (tail)
            tail->next = newSong;
        else
            head = newSong;
        tail = newSong;
    }
    void print() const
    {
        for (Song* s = head; s; s = s->next)
            cout << s->title << ": " << s->length << '\n';
    }
};

int main()
{
    SongList songs;
    
    songs.append("one", 123);
    songs.append("two", 456);
    songs.append("three", 789);

    songs.print();
}