Recursion Resources

[Aaron Vienneau]

Hey guys,

Simple question: Just looking for a good book or article on recursion. I know there are hundreds out there, but just want your opinion on an article you read about recursion and were like, "Wow, that makes a lot of sense" and it cleared up any confusion you had about recursion or helped you think recursively.

I understand what recursion is, but have trouble thinking recursively. Any help would be greatly appreciated.

[Disch]

I don't know any articles, but the concept of recursion is easy to grasp when the function in question has a clear objective.

For an example... let's say we have a sorted binary tree that has nodes which look like this:

struct Node
{
    int value;
    Node* left;
    Node* right;
};

And let's say we want to make a function which recursively searches through the tree to find the specific node. So that we can do this:

Node* desiredNode = findNode( tree_top, 5 );  // find the node that has a value of '5'
    // start the search at the top of the tree (our tree_top node) 

This function can be recursive, and has a very clear objective: Return the node with the matching value.

So here's a commented example of how the function might look:

Node* findNode( Node* node, int target )  // look for 'target' in the given 'node'
{
    if(!node)  // if this node is null, then we can't find the target, so return null to indicate failure
        return nullptr;

    // otherwise... is this the correct node?
    if(target == node->value)
        return node;  // if yes, then we found our target, so return this node.

    // At this point... this is not the correct node.. so we need to search other nodes.
    // But how can we do that?
    // Well... we're ALREADY doing it... that's what this 'findNode' function is.  So let's just
    // use recursion to call it again!
    // The only difference is... rather than searching the top of the tree, we're searching this
    // node's children.

    // if the target is less than this value, then the target must be in a left node
    if(target < node->value)
        return findNode(node->left, target); // search left node for the target
    else
        return findNode(node->right, target); // otherwise, search the right node
}

[Aaron Vienneau]

Hey Disch,

Could you give me clues on how to solve this problem recursively? I really don't want someone to solve it for me, but maybe give me a hint on how to think to solve this problem...

Write a recursive function that finds and returns the minimum element in an array, where the array and its size are given as parameters.

//return the minimum element in a[]
int findmin(int a[], int n)

Right now, I have this basic skeleton.

#include <iostream>
using namespace std;

int findmin(int ar[], int size);

int main()
{
	int myArray[5] = { 5, 2, 4, 3, 6 };

	cout << findmin(myArray, 5);

	return 0;
}

int findmin(int ar[], int size)
{
	if(size <=0)
            return ar[size]; // I'm assuming this is the only thing you can do at this point.

        // Maybe do some sort of relational expression here?
        if(findmin(ar, size-1) > something)
            // do something.

        // I'm really just guessing at this point, intuition is just compelling me to think this way; any tips would be appreciated.

}

[Disch]

Here are some things to think about:


- The recursive approach is to have a function which does 1 thing... then calls itself if it needs to do that thing multiple times.
- If you have an array with one value... then that value is the smallest value in the array.
- If you have more than one value, then you compare values with the < operator to see which is smaller.


The recursive mindset for this problem:

Which is smaller? The value I'm currently looking at? Or the smallest value in the rest of the array?

EDIT:

Also... just FYI, this is wrong:

    if(size <=0)
            return ar[size]; // wrong wrong 

If you have an array with a size of 0... then it has no elements. So ar[0] is going to be out of bounds.



EDIT 2:

I also hate how recursion is taught so early on. It's scarcely useful and is very difficult for beginners to wrap their head around. It should be taught way way later... if at all.

[z05DSL3A]

I was trying to think how to guide you to a solution but it basically gives you the code in a more confusing way...so here is some code that does what you want. Hope it helps you get you hear around recession.



______________________________________________________
edit:
this may be of interest:
What on Earth is Recursion? - Computerphile
https://www.youtube.com/watch?v=Mv9NEXX1VHc

[Disch]

He specifically said he didn't want a solution, Grey Wolf... >_>

[z05DSL3A]

Sorry Disch, missed that.

[Aaron Vienneau]

Thank you both for your contributions.

I will process what you've said and let you know if I can come up with something.

Disch, your post was particularly helpful; thank you for telling me how to think through the problem instead of do the problem.

Grey Wolf, thanks for your Youtube vid; I'll give it a watch! :)

I will keep this open to post my solution to see if I'm on the right track. . .


EDIT:

Disch,

If you have an array with a size of 0... then it has no elements. So ar[0] is going to be out of bounds.

Wouldn't ar[0] be the first element in the array?

[z05DSL3A]

Wouldn't ar[0] be the first element in the array?

Normally yes but if the size on the array is zero then there is no element to be the first, in this case it would be out off bounds.

index   0  1  2
size 2 [x][x]
size 1 [x]
size 0 |

remember that the index for the last element in an array is the size - 1,

[Aaron Vienneau]

So, I should check for:

if(size <= 1) { return ar[size-1]; }

Saying, if the size of the array is 1 element, return the first element in the array. . in other words ar[0].

??

[Aaron Vienneau]

Got it.

#include <iostream>
using namespace std;

int findmin(int ar[], int size);

int main()
{
	int myArray[6] = { 5, 2, 10, 3, 7, 1  };

	int tiny = findmin(myArray, 6);

	cout << tiny << endl;

	return 0;
}

int findmin(int ar[], int size)
{
	if (size <= 1)
		return ar[size - 1];
	else
	{
		if (ar[size - 1] < findmin(ar, size - 1))
			return ar[size - 1];
	}
}

Is this right?

[Disch]

You're very, very close.

The only problem is that you are not returning anything if the condition on line 23 is false.

[Aaron Vienneau]

I'm not sure what you would return there. . . ar[0]?

[Disch]

You are comparing two values to see which one is less. So logically you'd want to return whichever is less.

You are currently doing this:
==============
- If ar[size-1] is less... then you return it.
- Otherwise you are returning nothing/garbage.

[Aaron Vienneau]

You're right, I am

comparing two values to see which one is less

here:

if (ar[size - 1] < findmin(ar, size - 1))
			return ar[size - 1];

But, one of the operands to < operator is a value ar[size-1] and one of them is a recursive function call findmin(ar, size-1). So logically, if the ar[size-1] is less than whatever is returned from the recursive function call, you're going to want to return ar[size-1]. But what if the recursive function call returns something smaller than ar[size-1]? How do I return a recursive function call?

I understand what you're trying to get at, but don't understand how to syntactically do it. Unless I'm storing the return value of the recursive function call in a variable and comparing it to ar[size-1] and then just returning the variable?

[Disch]

Unless I'm storing the return value of the recursive function call in a variable and comparing it to ar[size-1] and then just returning the variable?

Yes, that's one way to do it.