High School Programming. Study Help

[igotsnomoney]

In our school on every comp sci test we have a massive tracing question, where students have to visualize the code and predict the output. Usually I have no problem with this

but this unit being tested is recursion, I am having a very hard time trying to picture what is actually happening in programs. I have a vague idea of the method calling itself, but i can't picture it in my head. any tips of analogies for me to trace recursion better?

[GoodBytes]

Write on a paper as you follow the code.

[VolkovBrad67]

You can picture the call stack, which is convenient because it's both easy to visualize and it's also what's really happening. For example let's assume you have a recursive function that traverse a directory (note this is not a particular language, the following is kind of pseudo-code) :

function traverseDirectory(path){
files[] = listFilesInDir(path);
for each file in files[]
{
if isFolder(file)
{
traverseDirectory(file);
}
}
}

You could draw a stack pile, and for every call to traverseDirectory, you put the parameter value in the box of the stack. For example it could look like this :

	[c:\folder1        ]
	[c:\folder1\folder2]
	[c:\folder1\folder2\folder3]

And then once you are at the end (no more call to the function), you strikeout the items from the stack, one by one, and you add them again if you get back into the function :

[c:\folder1        ]
[c:\folder1\folder2]
[------------------]

[c:\folder1        ]
[c:\folder1\folder2]
[c:\folder1\folder4]

[c:\folder1        ]
[c:\folder1\folder2]
[c:\folder1\folder4]
[c:\folder1\folder5]

[c:\folder1        ]
[c:\folder1\folder2]
[c:\folder1\folder4]
[------------------]

[c:\folder1        ]
[c:\folder1\folder2]
[------------------]
[------------------]

And so on...

[Abhinav]

I agree that understanding recursive functions can be difficult. So lets take a simple problem.

Lets make a function which prints the following numbers on the screen:

54321

Using a normal function will definitely make the task easier

Pseudo code:

void printnum(){    let i = 5;    loop till i > 0    {         print on new line 'i'         i--    }        }

But we have to transform this into a recursive function. To understand the concept of recursive function we need to understand the concept of a stack. In a nut shell, stack is something like saucers kept on one another. So to remove saucer number 5, saucers 1 to 4 have to be replaced somewhere else.

In computers stack is like an array which can be accessed from only one side. This kind of access structure is call LIFO (Last in first out). Let me explain it to you diagrammatically.

| |

| 2 | <--- Top of stack

| 7 |

| 3 |

| 5 |

----------

As you can see here a stack has only one opening and the only accessible element here is the top element ' 2 ' .

Functions related to stacks:

1) PUSH:- This adds an element to the stack.

eg PUSH 78

| 78 | <--- Top of stack

| 2 |

| 7 |

| 3 |

| 5 |

---------

2) POP:- Removes the element from the stack

eg POP

| |

| 2 | <--- Top of stack

| 7 |

| 3 |

| 5 |

---------

So lets get back to the recursive function

Pseudo code:

let x = 1
void printnum(x){      if i <=5 then     {         printnum(x+1)          print on new line ' i '     }}

The above code will generate the output.

This is what happens in recursive function.

[TABLE]

[TR]

[TD]

S.No.[/TD]

[TD]

What the compiler does[/TD]

[TD]

What happens in the stack[/TD]

[/TR]

[TR]

[TD]

1[/TD]

[TD]

The compiler calls printnum(1)[/TD]

[TD]

PUSH printnum(1)[/TD]

[/TR]

[TR]

[TD]

2[/TD]

[TD]

The compiler checks if 1 <= 5[/TD]

[TD]

[/TD]

[/TR]

[TR]

[TD]

3[/TD]

[TD]

The condition is true so the compiler calls printnum(2)[/TD]

[TD]

PUSH printnum(2)[/TD]

[/TR]

[TR]

[TD]

4[/TD]

[TD]

Checks if 2 <= 5[/TD]

[TD]

[/TD]

[/TR]

[TR]

[TD]

5[/TD]

[TD]

The condition is true so the compiler calls printnum(3)[/TD]

[TD]

PUSH printnum(3)[/TD]

[/TR]

[TR]

[TD]

6[/TD]

[TD]

Checks if 3 <= 5[/TD]

[TD]

[/TD]

[/TR]

[TR]

[TD]

7[/TD]

[TD]

The condition is true so the compiler calls printnum(4)[/TD]

[TD]

PUSH printnum(4)[/TD]

[/TR]

[TR]

[TD]

8[/TD]

[TD]

Checks if 4 <= 5[/TD]

[TD]

[/TD]

[/TR]

[TR]

[TD]

9[/TD]

[TD]

The condition is true so the compiler calls printnum(5)[/TD]

[TD]

PUSH printnum(5)[/TD]

[/TR]

[TR]

[TD]

10[/TD]

[TD]

Checks if 5 <= 5[/TD]

[TD]

[/TD]

[/TR]

[TR]

[TD]

11[/TD]

[TD]

The condition is true so the compiler calls printnum(6)[/TD]

[TD]

PUSH printnum(6)[/TD]

[/TR]

[TR]

[TD]

12[/TD]

[TD]

Checks if 6 <= 5[/TD]

[TD]

[/TD]

[/TR]

[TR]

[TD]

13[/TD]

[TD]

The condition fails the compiler

completes executing printnum(6)[/TD]

[TD]

POP and execute rest of the commands[/TD]

[/TR]

[TR]

[TD]

14[/TD]

[TD]

At the top of the stack is printnum(5)

so it prints ' 5 ' as the next line of code is print after calling printnum(6).[/TD]

[TD]

POP and execute rest of the commands[/TD]

[/TR]

[TR]

[TD]

15[/TD]

[TD]

At the top of the stack is printnum(4)

so it prints ' 4 '[/TD]

[TD]

POP and execute rest of the commands[/TD]

[/TR]

[TR]

[TD]

16[/TD]

[TD]

At the top of the stack is printnum(3)

so it prints ' 3 '[/TD]

[TD]

POP and execute rest of the commands[/TD]

[/TR]

[TR]

[TD]

17[/TD]

[TD]

At the top of the stack is printnum(2)

so it prints ' 2 '[/TD]

[TD]

POP and execute rest of the commands[/TD]

[/TR]

[TR]

[TD]

18[/TD]

[TD]

At the top of the stack is printnum(1)

so it prints ' 1 '[/TD]

[TD]

POP and execute rest of the commands[/TD]

[/TR]

[TR]

[TD]

19[/TD]

[TD]

It has finished executing printnum(1) which was called first.[/TD]

[TD]

STACK UNDERFLOW!

which means that the stack is empty[/TD]

[/TR]

[/TABLE]

This is how recursive functions work. It is kinda confusing. But if you practice this concept you will succeed in understanding it.

I Hope this was helpful. :)

[igotsnomoney]

Thanks for your help everyone. Really Helped me with the concept. I am within the top 3 of my class now and currently attempting towers of Hanoi.

[jetbuster]

goddamn hanoi, still its amazing they are teaching that level of programming at a highschool level, here in NZ got taught recusion as a 5XX course, highschool ends at 3XX equivilents

[igotsnomoney]

goddamn hanoi, still its amazing they are teaching that level of programming at a highschool level, here in NZ got taught recusion as a 5XX course, highschool ends at 3XX equivilents

lol, ya the programming course here in Markham ontario, is pretty intense. in grade 10 we leaned all the basics (Conditionals, variables, methods) on a learner language (Turing). Grade 11 we move onto to Java. We spend about half the semester on the basics again (Its an open course with no prerequisites). The second half of the semester is intro to OOP, and we start working on our final projects (program a game in java).

in grade 12 you learn:

Unit 1: Recursion

Unit 2: Data structures (Multidimensional arrays, Stacks, Queues)

Unit 3: Sorting Algorithms (Insert, Quick, bubble, and as a challenge depth first )

Unit 4: I think its UI but i'm not entirely sure.

[jetbuster]

goddamn hanoi, still its amazing they are teaching that level of programming at a highschool level, here in NZ got taught recusion as a 5XX course, highschool ends at 3XX equivilents

lol' date=' ya the programming course here in Markham ontario, is pretty intense. in grade 10 we leaned all the basics (Conditionals, variables, methods) on a learner language (Turing). Grade 11 we move onto to Java. We spend about half the semester on the basics again (Its an open course with no prerequisites). The second half of the semester is intro to OOP, and we start working on our final projects (program a game in java). in grade 12 you learn: Unit 1: Recursion Unit 2: Data structures (Multidimensional arrays, Stacks, Queues) Unit 3: Sorting Algorithms (Insert, Quick, bubble, and as a challenge depth first ) Unit 4: I think its UI but i'm not entirely sure.[/quote']

Guess where im sending my kids for schooling zomg

[P3rad0X]

Practice, Practice, Practice Makes Perfect