Recursion (Think Like a Programmer)

Your comments and suggestions for future videos are welcome.

"Think Like a Programmer" is a book I've written to help programmers with problem solving. If you've found that you are able to read programs and understand programming language syntax but aren't always confident writing programs from scratch, my book may be able to help.

For more information on the book head to one of these:

Connect with me:

[vantonspraul]

If you liked this video, be sure to check out my other videos about recursion:

[ShrestaBS]

Finally someone who can teach recurrence without Fibonacci!! Good video 👍

[vantonspraul]

Thanks, Alek. I agree, problem solving is often the missing ingredient when programming is taught.

[hosamhasan]

simply, you are the best .
because you are the only one that explains me Recursion and i understand it directly .
or may be i am stupid :)

[mamdouhwaleed]

I really wish I had found this earlier, I have already been struggling with Recursion for a while, thanks for making this whole series, my life is way easier now <3

[yoshuadiaz]

Your video it`s amazing, I tried to understand recursion before without results, but, with your approach, I gain confidence and I tried with the Fibonacci and Factorial problems by myself with your approach (and without other guides) and I solved by myself without consulting stack overflow ! Thanks a lot! I bought your book! You are the man (and Batman in the night for sure)!!! Cheers from México!

[ismellpedo]

I think I finally understand recursion..

Normally when recursion is taught they simply say, "first create your base step, this ends the recursion, then create your recursive step here the function calls itself and solves the problem recursively". Most resources I have found don't really elaborate on the thought process rather they elaborate on what is happening at a lower level (stack, etc).

Through this video I have found that recursion can actually be broken down into three steps:
1. The base step (stops recursion)
2. The Minimization step (creates the smallest possible instance of a problem. Example: 500 element array turned into 1 or 2 element array)
3. The Solution step (This handles the solution for the 1 or 2 element array rather then the 500 elements)

Once the function arrives at the Solution step, the array has already been broken down to its smallest possible version. It then solves the smallest problem and works its way up solving and handling the rest of the array.

Thank you so much for making this video!

[parasarora]

finally i get to know the big idea and baby steps to take while learning recursion. all thanks to you sir. 😄

[vantonspraul]

I didn't mean to suggest that recursion should be forced on any situation where it doesn't fit. I just meant that when learning this particular technique of recursive problem solving, I would start with applying it to situations you already can solve with iteration.

[mariusandries]

This is quite nice explanation on recursive function. Thanks Sir.

[azngiant]

OMG, I was watching other recursion videos and still didn't get it until I saw yours. I thought the moment you replaced the dispatcher method to call itself without changing anything was magical! Biggest epiphany I ever experienced. You just got yourself a subscriber. I'll be watching your other videos. THANK YOU!

[muneebzubair]

This is not working for my problem:
find any pair in array whose sum is equal to a key.

bool pairSum(int key, int arr[], int s, int e)
{
for (int i = s; i < e; i++)
{
for (int j = i + 1; j <= e; j++)
{
cout << arr[i] << " " << arr[j] << endl;

if (arr[i] + arr[j] == key)
return true;
}
}
return false;
}

I am not able to convert it to dispatcher. and recursive one. kindly guide me.

[Raging.Geekazoid]

If you want to understand recursion like a programmer, stop thinking about the function you're using and start thinking about the data you're analyzing or the problem you're solving. The important thing to take away from this video is the idea of looking at the whole problem from above (i.e. from the dispatcher's point of view). Getting stuck thinking about what's inside a recursive function is confusing, because then the environment outside the function (i.e. the actual problem itself) becomes a mystery.

Analyzing linear data structures is exactly what you DON'T need recursion for, and doing two of them together doesn't really make the explanation any clearer. What you DO need recursion for is tree-shaped data structures and AI decision trees, because there is no iterative version of those programs. The loops would have to be nested, and in many cases there's no way to know ahead of time what the limits of the loops and the amount of nesting would be. The next step after watching this video is to learn what to do when the dispatcher function needs to call itself more than once from the same call. 😮

If you're trying to deal with tree-shaped data, you'll need to visit every node in the tree, and how are you going to do that? You have to visit the root node first, because that's the only one you have direct access to, so it's the only way to get to the inner nodes. Then you'll need to visit the children of the root, then the children of the children, and so on down to the end nodes of the tree (trees are always pictured upside down 🙄). And the easiest, simplest way to do that is to call a function to deal with each node. If you try to do it all with one call to some kind of mega-dispatcher function, you'll have to create a data structure called a "stack" (i.e. a trail of crumbs that shows you the way back home) to remember which nodes you went through to get to the current node, and now you're re-inventing the wheel. Every program already has a stack that's used for function calls. You might as well use that.

And you might as well use the same function you used on the root node, because why not? You're performing more or less the same operations on each node, except for the leaf nodes, and you don't know ahead of time when you'll run into one. If you're working on an AI algorithm, you don't know ahead of time what steps the AI will have to take, and there will be multiple possibilities at each step. So the space of possible actions for the AI to take is shaped like a tree. Might as well write a function to deal with each step and have it make another call to itself when it's time to deal with the next step. That's recursion. You'll have to put some logic in the function to decide whether it's dealing with a leaf or a branch node, but that's easy.

And remember: You make calls from the top down and return results from the bottom up. (1) The function's parameter list needs to contain whatever information the function needs to analyze the nodes of the tree, (2) the return value needs to contain whatever information you're trying to extract from the tree, and (3) in many cases you'll have to combine the results of the calls to a node's children before returning from that node (the parent of the children). That's all there is to it! 🙂

[chenzoe]

Totally fall in love with the book. Thanks so much. I am now even able to write recursion function on the binary search tree. Before reading the book, I can hardly understand the factor function.

[baburao]

hey man, does it way to do recursion


a = [1, 10, 15, 16, 12]
b = [2, 10, 14, 15, 11]
r = []
t = 0


def A():
for i in range(len(a)):
r.append(a[i] - b[i])
B()


def B():
for q in range(len(r)):
if r[q] < 0:
r[q] = r[q] * (-1)
C()


def C():
global t
for e in range(len(r)):
t = t + r[e]
print(t)


A()

[DavidKing-wkws]

OK thats it I will buy the book but I need it hand written in no.2 pencil, reflecting 2 forms of ID, 4 major credit cards and a note from the publishers mother with proof she signed it. :)

[viveksuman]

I will just write empty iterative functions and assume it solves the problem for my own satisfaction because I still can't trust recursion. lol. This video helped alot. Thanks!

[Towhid-zerw]

Sir, thanks a lot for this. If I am cracking that interview, much credit will be given to you.

[tgiq]

I have been stuck on the topic of recursion for several days, and now it has finally clicked.

[xinfinity]

what is an example of a problem that iteration can't solve or can't solve easily that recursion can solve or can solve easily?