Recursion

Loading...

From the course by University of Colorado System

Data Structures and Design Patterns for Game Developers

30 ratings

University of Colorado System

Data Structures and Design Patterns for Game Developers

30 ratings

Course 4 of 5 in the Specialization C# Programming for Unity Game Development

This course is the fourth course in the specialization about learning how to develop video games using the C# programming language and the Unity game engine on Windows or Mac. Why use C# and Unity instead of some other language and game engine? Well, C# is a really good language for learning how to program and then programming professionally. Also, the Unity game engine is very popular with indie game developers; Unity games were downloaded 16,000,000,000 times in 2016! Finally, C# is one of the programming languages you can use in the Unity environment. This course assumes you have the prerequisite knowledge from the previous three courses in the specialization. You should make sure you have that knowledge, either by taking those previous courses or from personal experience, before tackling this course. The required prerequisite knowledge is listed in the "Who this class is for" section below. Throughout this course you'll build on your foundational C# and Unity knowledge by developing more robust games with better object-oriented designs using various data structures and design patterns. Data structures and design patterns are both general programming and software architecture topics that span all software, not just games. Although we'll discuss these ideas in the game domain, they also apply if you're writing a web app in ASP.NET, building a tool using WinForms, or any other software you decide to build. Module 1: Explore a Dynamic Array data structure and learn the basics of algorithm analysis Module 2: Learn about and use the common Linked List and Graph data structures Module 3: Learn about and use several additional data structures: Stacks, Queues, and Trees Module 4: Learn why design patterns are so useful and discover a number of design patterns useful in game development Module 5: Complete final peer review “Unity” is a trademark or registered trademark of Unity Technologies or its affiliates in the U.S. and elsewhere. This course is an independent work and is not sponsored by, authorized by, or affiliated with Unity Technologies or its affiliates

From the lesson

Stacks, Queues, and Trees

Lesson Introduction1:37

Recursive Binary Search6:17

Tree Implementation11:07

Tree Analysis7:56

Tree Traversal9:02

Minimax Search9:03

Minimax Implementation9:57

Meet the Instructors

Dr. Tim "Dr. T" Chamillard
Associate Professor
Computer Science

In this lecture, we'll learn about something called recursion.

So what is recursion?

It's a technique that we use to solve a problem,

by solving smaller versions of the same problem.

The other characteristic of problems that are well-suited to be solved

using recursion, is we need to have a base case, or

a termination condition to stop the recursion.

In other words, a version of the problem that's small enough that we know

the answer, without trying to solve even smaller versions of the problem.

How do we do recursion in C#?

Well, we have a method call itself

with a smaller version of the problem that we're trying to solve.

And we also have the method recognize the base case,

so it can stop recursing, and return the answer back up.

So we can finally build the final solution out of the solutions to

the smaller versions of the problem.

Why do we care about recursion?

Well, recursion is really useful when we traverse trees.

So we'll see ourselves using recursion both in our implementation of the tree

class, and as we learn about traversing and searching trees.

I'm using Visual Studio for this lecture because I can use

the debugger in a console app to show you what's happening with the call stack.

I can't do that with MonoDevelop, because the MonoDevelop that

ships as part of Unity, the debugger doesn't work in the console apps.

So just for this lecture, I'm using Visual Studio.

So let's look at our factorial method that works recursively.

Here it is, it's a very short method.

What we do, is we pass in an n, the number for

which we want to calculate the factorial.

And if n is equal to 0, then we're going to return 1

because the mathematicians have told us that 0 factorial is 1.

And if it's not, then we're going to return n times factorial of n minus 1.

So, if in fact we're calculating 5 factorial, and

we call this method with 5, then we will return 5 times 4 factorial.

And then it will be 4 times 3 factorial and so on, until we get all the way

down to n equals 0, and that's our base case, or our termination condition.

So let's watch how this works.

I'm going to set a break point here.

And up here in the main method, we're going to just provide an n,

and then it will calculate to the factorial for us.

So, I'm going to run the code using F5, not Control-F5, so I'm using the debugger.

And I'm going to enter 5 factorial.

So as you can see, we hit this break point and n is 5 here.

And down here in the call stack,

we have just added this call to the factorial method.

Now, I'm going to F5 again, and

as you can see, n is now 4.

And our call stack includes the first call to the factorial method, and

the second call.

And I'm going to F5 so n is 3, and F5 and n is 2,

and F5 and n is 1, and F5 and n is 0.

So here you can see n is 0.

And here in the call stack, you can see all these calls to factorial.

So an interesting tidbit, is if in fact we end up with infinite recursion,

we will just keep calling this method again, and again, and

again, never reaching the base case.

And so, eventually, our call stack will get filled up, and

the stack will overflow.

And that's why the StackOverflow website is named StackOverflow,

because you go there when you have programming problems.

And overflowing the call stack with infinite recursion

would be a programming problem.

Okay so now we have reached our base case.

So I'm going to step instead of F5, I'm going to step,

And as you can see I'm going to return 1.

So if I F10 here, I get to the end of the method,

and I've just removed one of those calls from the call stack.

I just returned 1, and returned back here, so n is 1.

And I've just returned 1 from the call to factorial with n of 0.

So as you can see, once I come out of all of those recursive calls,

I get the answer, 120, which is, in fact, 5 factorial.

So I'll exit out of here by entering a negative 1.

So the big ideas here in this recursive method are,

I can keep breaking the problem into smaller versions of the problem to try to

solve it, as long as there is a base case, or

a termination condition that I get to to stop the recursion.

To recap,

in this lecture we saw how we can do factorial calculation using recursion,

and we also learned that recursion will be useful as we work with trees.

And you didn't necessarily learn that, I just told you that.

But trust me, it's true.

And we'll see that it's true in a few lectures.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play