Tips for learning recursion?

[chopnhack]

The course is moving right along and makes me wish I had more time to keep up with it!! Currently I am having difficulty following recrusions. The idea sounds wonderful, just like when you took an interating loop and bundled it up into a function. In practice, it almost looks like a self calling loop that shouldn't work. Amazingly, it abstracts out another variable, computes and returns values....

def recurPowerNew(base, exp):
'''
       base: int or float.
       exp: int >= 0

       returns: int or float; base^exp
'''
# Base case is when exp = 0
        if exp <= 0:
            return 1

# Recursive case 1: exp > 0 and even
        elif exp % 2 == 0:
            return recurPowerNew(base*base, exp/2)

# Otherwise, exp must be > 0 and odd, so use the second
# recursive case.
        return base * recurPowerNew(base, exp - 1)

My guess is that the exp is decremented by the last statement (exp-1) - so if exp == 3, the function returns the sum of base * recurPowerNew(base, 3-1) <exp now 2> and in the next go around it will stop at the even recursion statement. This will return recurPowerNew(base*base, exp/2)
So now exponent is 2/2 or 1 - what happened to the function for just number two? It seems it was skipped. The answer was marked as correct, but I don't under recursion very well...

Any light you could shed would be greatly appreciated!
Thank you.

 

[Gryd3]

The course is moving right along and makes me wish I had more time to keep up with it!! Currently I am having difficulty following recrusions. The idea sounds wonderful, just like when you took an interating loop and bundled it up into a function. In practice, it almost looks like a self calling loop that shouldn't work. Amazingly, it abstracts out another variable, computes and returns values....

def recurPowerNew(base, exp):
'''
       base: int or float.
       exp: int >= 0

       returns: int or float; base^exp
'''
# Base case is when exp = 0
        if exp <= 0:
            return 1

# Recursive case 1: exp > 0 and even
        elif exp % 2 == 0:
            return recurPowerNew(base*base, exp/2)

# Otherwise, exp must be > 0 and odd, so use the second
# recursive case.
        return base * recurPowerNew(base, exp - 1)

My guess is that the exp is decremented by the last statement (exp-1) - so if exp == 3, the function returns the sum of base * recurPowerNew(base, 3-1) <exp now 2> and in the next go around it will stop at the even recursion statement. This will return recurPowerNew(base*base, exp/2)
So now exponent is 2/2 or 1 - what happened to the function for just number two? It seems it was skipped. The answer was marked as correct, but I don't under recursion very well...

Any light you could shed would be greatly appreciated!
Thank you.

"What happened to the function for just number two?"
Take a look here : https://docs.python.org/2/reference/expressions.html
Look at the Modulo Operator.
"elif exp % 2 == 0:"
Will match if exp is an exact multiple of 2.

Recursion is an interesting topic. Perhaps someone can put it into better words than I. I typically come across it when dealing with subdirectories.. the search function will typically run inside one directory, then run again inside each subdirectory to search the entire tree. Kind of like nested loops, but recursion will run until it can no longer go any deeper. (Into a mathematical equation or directory tree)

 

[chopnhack]

"What happened to the function for just number two?"
Take a look here : https://docs.python.org/2/reference/expressions.html
Look at the Modulo Operator.
"elif exp % 2 == 0:"
Will match if exp is an exact multiple of 2.

Right, so when exp was 2, the next statement triggered which was "return recurPowerNew(base*base, exp/2)" in which the exp becomes 2/2

ah!!! and thus decrements to 1 and the series terminates! Got it, thanks @Gryd3 !!

 

[Merlin3189]

Recursion is (I think) quite a simple idea, but the logic of any particular function is sometimes a bit obscure.

The crucial point is that there must always be a case which returns a non-recursive result to end the process. Here it is "the base case" which just returns 1. And the other cases must ensure you end up here. In your eg. the other cases keep reducing the exponent, so it must end up <=0.

Incidentally, "and thus decrements to 1 and the series terminates! " is not quite correct. It always terminates when exp<=0. Exp=1 is just another odd number, so you multiply by the base, decrement the exp (in this case to 0) and make another call.

The other question is the depth of recursion - how many times it calls itself before reaching that end case. Each time a function is called, data is saved on the stack so that the program can resume correctly when the function returns. On PCs this may not be very significant with the vast amounts of RAM that a program can be allotted, but for eg. on a micro controller memory is very limited and you could easily overflow the stack if you were not careful. (But I've seen cases where even a PC has complained about stack overflow.)

If you have trouble understanding a recursive function, try working a simple example through by hand.

eg. take 2^11
base....exp....case......mult.............new base....new exp
2..........11.......odd........2........................2...........10......(mult*base, exp -1)
2..........10......even.......2........................4.............5......(base*base, exp /2)
4...........5.......odd........4*2.....................4.............4......(mult*base, exp -1)
4...........4.......even......4*2....................16............2......(base*base, exp /2)
16.........2.......even......4*2..................256............1......(base*base, exp /2)
256.......1........odd.......256*4*2...........256............0.....(mult*base, exp -1)
256.......0......'base'.....1*256*4*2.........Return.............(mult*1, return)

In my opinion, recursion is indeed "an interesting topic". It is however one of those programming ideas that may look simple when you write the code, but can hide a lot of work going on when the program runs. You need to think a bit about how deep it could get. Sometimes it may be longer to code, but quicker to run, if you use an alternative method. For PCs memory and processor speed are rarely an issue any more, but small controllers trying to run real time processes may have to think about them.

 

[chopnhack]

Thank you @Merlin3189 - the topic is wonderfully interesting, but I am still having difficulty. I agree with you with respect to memory allocation and use and I appreciate you bringing that up since my current focus will be using a μcu. Establishing the base case and then coding the recursive call is not clear (yes, I do realize that is the entire matter at hand!)

I found this example to make it quite clear:

def factorial(n):
       if n == 1:
            return 1
       else:
            return n * factorial(n-1)

The final line of code takes n and multiplies it by the function itself while decrementing the variable. When n becomes 1 the program returns 1 to the stack and then sums up the intermediary values.

I find it much harder to visualize the other examples they have asked us to do. The tip was to find the base case first and that it would enable us to write the equation more easily. Perhaps I need more time with writing these, shame the course moves so fast!!

 

[Merlin3189]

Even when you understand the concept of recursion and the basic coding principles, it is not always easy to see how to implement it in a particular problem.

The factorial is a particularly simple example, having only the base case and a case for all the other numbers. Your exp function had only one more case, but it took me a while to understand how it was working and to be sure that it would always reach the base case. My first thought was to do it like the factorial.
If (exp <= 0) return 1 else return base * recurPowerNew( base, exp -1)
but when I worked the example, I could see that your method was much more efficient. I don't know whether I would have thought of that algorithm myself though. I can't think of any way of making a similar improvement in the factorial function.

So it probably needs mathematical understanding of the function to see different ways of implementing it. I think this is where the difficulty lies - not in coding the recursive function, but in understanding the underlying problem well enough to recognise the required cases. (Though I think sometimes the coding can be difficult as well.)

 

[KrisBlueNZ]

Good points there in post #4, Merlin3189. Recursion doesn't scale down well.

Here's a general overview of stacks and recursion - stuff that Merlin3189 already knows, and chopnhack may also know most of this as well.

In order to implement recursion, some kind of stack is needed.

A stack is simply a block of storage (almost always an area of memory) that is used for automatic, dynamic memory allocation, to keep track of information which accumulates over time and is then dismantled in reverse order, in such a way that, usually, only the "top" information is in use.

The classic use for a stack is for storing return addresses and local variables for functions. When one piece of code calls another piece of code, for example when some code in function1() invokes function2(), the current execution point (code address) in funtion1() needs to be kept somewhere while control is transferred to function2(), so that when function2() returns, execution can continue from the next statement in function1().

Since function2() could also call function3(), and so on, a generalised solution is needed, and a stack is used to keep track of these return addresses. This stack is usually also used for local variables - variables that are used within each function, rather than being global - and for parameters passed to functions, because this is a simple and convenient way to allocate storage for data that is associated with a particular invocation of a function.

The stack is just an allocation system that uses a block of storage. Allocation and use of this storage starts at one end (called the bottom of the stack, although it may actually be the highest memory address in the block) and is tracked by a stack pointer (SP), which identifies the current top-of-stack location.

When new information is added to the stack, it is stored at the "top" of the stack, and the stack pointer is advanced to the next piece of storage to be used. This is called pushing data onto the stack. When the information at the top of the stack is no longer needed, and the previously pushed data needs to be accessed, data is popped off the stack by adjusting the stack pointer.

The actual data does not move; only the stack pointer changes. (And often, one or more other pointer registers in the CPU that also allow the stack memory to be addressed.)

The stack is used dynamically, according to the program flow. Every time a function is called, data is pushed onto the stack. Every time a function returns, data is popped off the stack. Therefore the stack is constantly growing and shrinking during program execution.

Since there is a limited amount of memory available for the stack, if the program runs in such a way that the nesting of function calls is too deep, the stack pointer will reach or pass the end of the memory area reserved for the stack, and you will have a stack overflow. Since recursion deliberately uses significant amounts of stack space, you could say that using it is kind of tempting fate!

The effect of a stack overflow depends on the environment - the programming language, the way it's executed (interpreted vs. compiled), and the complexity of the CPU or MCU (microcontroller unit) that's executing it.

Stack overflows cannot reliably be predicted by analysing the source code, because the exact execution path the program takes is often determined by real-time stimuli which can't be predicted - at least, not in their complex combinations over a period of time. Some limits can be calculated - for example, a factorial function that uses recursion can be written so it checks the number being factorialised, and aborts if it's so large that the estimated stack requirement is more than the runtime environment supports. If that amount is known at coding time!


The Python language is interpreted, or partly compiled using a JIT (just in time) compiler, I think. In either case, executing the program requires a properly designed runtime environment, which takes care of the allocation of all resources, including memory, and is able to abort the program with a tidy explanatory error message if the program tries to exceed the available stack memory. The Python runtime environment is too large and complicated to run on very resource-constrained microcontrollers, so it has plenty of memory available. So recursion can be done pretty safely in Python.

Java programs are compiled into bytecode which is then executed by the Java Runtime Environment (JRE). The JRE can run on somewhat resource-constrained devices - in fact it was originally designed for embedded applications, but in all cases, it allocates and monitors resources, and can detect stack overflow and abort the program with some kind of error indication.

Since a function's execution point and its dynamically allocated data (parameters, and dynamically allocated variables, called "automatic" variables in C) both need to be preserved when another function is called, and restored when that function returns, they are often both stored on the same stack, but not always. The choice depends on the design of the runtime environment, or in some cases, the hardware.

With very resource-constrained devices such as the Microchip PIC and the Atmel AVR, several techniques are used to deal with dynamic memory allocation. But many of these devices have so little RAM that a program's allowable function nesting depth and recursion are very restricted anyway, and recursion may not even be permitted.

Specifically, the 8-bit PIC microcontrollers (baseline, mid-range and "high-end") all have a stack that's not within main memory; in baseline and mid-range devices, this stack can only be used for return addresses for function calls (including automatic calls due to interrupts). This stack cannot be used for function parameters or local variables, because (a) it's tiny - only two levels in baseline devices, eight levels in mid-range devices, 16 levels in enhanced mid-range devices, and 28 levels in "high-end" devices, and (b) the core doesn't provide any way to access it (some limited kludges are provided in the "high-end" PICs).

The C programming environments for PICs don't allow recursion. (If there are any that do, they would implement it in a non-standard way.) In fact, parameters and local variables used by functions must be allocated statically (at fixed addresses) by the compiler, which analyses the program to figure out how memory usage can be minimised by overlapping allocation between functions that never appear on the same branch of call trees. The compiler goes to a lot of trouble to make generalised C code run on these architectures, but even then, there are limitations (such as recursion being disallowed) that they have to pass back up to the programmer.

The AVR and most microcontrollers put the stack in globally addressable RAM, so they are better able to implement C-language constructions, but again the small amount of RAM is often a limiting factor.

With small devices, stack overflow may not be automatically detected. On the AVR, and many other microcontrollers that have their stack in main memory, a stack overflow means that memory used for other purposes - statically allocated data, for example - gets overwritten without any warning! On the PIC, the stack "wraps around" and starts overwriting the oldest information first! (The "high-end" PICs can generate an exception on stack overflow.)

It's common for embedded systems programmers to fill the stack memory with a repeating pattern, such as "STACK---STACK---STACK---STACK---", at the start of program execution, so a memory dump later will show how much of the stack was actually used during program operation.

Recursion can be simulated using a loop. The dynamically allocated data associated with each invocation of the function is put into an array in memory, and the stack pointer is replaced by a variable containing either an entry number in that array or a pointer into it, that allows the loop code to locate the data at the current recursion "depth". This trick makes better use of memory, can be used in architectures where real recursion isn't allowed or is too limited, and has other advantages as well.

I wrote an anagram program in Java that used this technique. It would translate to Python pretty easily too. Let me know if you want to see it.

 

[chopnhack]

So it probably needs mathematical understanding of the function to see different ways of implementing it. I think this is where the difficulty lies - not in coding the recursive function, but in understanding the underlying problem well enough to recognise the required cases. (Though I think sometimes the coding can be difficult as well.)

Indeed! Thank you, at least I know I am not alone in this, LOL!

I wrote an anagram program in Java that used this technique. It would translate to Python pretty easily too. Let me know if you want to see it.

Thanks Kris, of course I would love to see it!!! But it might be all Greek to me... LOL The stack explanation was quite good, thanks for that - I had a vague idea of how it was done, but this confirms and builds on it. At this point, my brain is about to pop off! I wish that each module was two weeks instead of one - more time to develop the ideas. These courses were not built for people who work full time and have family and other commitments or perhaps my time management and comprehension is slower than their expected average . Either way, that will be my feedback to them, FWIW.

 

[Arouse1973]

How the hell do you guys get this? I feel a rash coming on. I love you BC108

 

[Gryd3]

How the hell do you guys get this? I feel a rash coming on. I love you BC108

I understand this better than electronics
I think it's fun! And I can play with code anywhere as long as I have a smartphone, or computer.

 

[KrisBlueNZ]

Sorry, I'm not going to be able to upload a Python version of my Java anagram program. It's quite a bit bigger and more complicated than I thought, and needs quite a lot of effort to convert from Java to Python. One day if I finish doing that, I'll upload it. Sorry :-(

 

[chopnhack]

Sorry, I'm not going to be able to upload a Python version of my Java anagram program. It's quite a bit bigger and more complicated than I thought, and needs quite a lot of effort to convert from Java to Python. One day if I finish doing that, I'll upload it. Sorry :-(

No worries, it would probably be above my level at the moment anyways! Thank you though.

 

[Merlin3189]

Just a quick question for Kris.
Your anagram prog: does it look up to see if words are in a dictionary or just find all the permutations of letters?
I ask, because if you do, I wonder where you got your dictionary word list from? Or where your program can look them up online.

Regards. Don (Merlin3189)

 

[KrisBlueNZ]

Hi Don. It uses a word list file, which I created from various online sources whose locations I did not keep track of! It includes lots of "words" that aren't words (initialisms, etc) because I wanted to maximise the number of matches and filter them manually. It's about 1.2 MB and ZIPs down to 306K (245K with 7-zip). I've attached it to this post - it's a ZIP file that contains an uncompressed 7z archive that you need to rename then extract.

 

[hevans1944]

When first exposed to recursion in a computer science class, I thought it was pretty nifty. Later, I realized that the actual implementation (using stacks) made a real program non-deterministic! End of story for me. I think recursive code is right up there with self-modifying code as something to avoid like the plague. Interesting as a mind game, but not something to put in my programs. YMMD.

Thank you @KrisBlueNZ for the overview of stacks and their limitations with regard to recursive calls. And of course the use of loops to implement recursion is still finite-bound by the size of the memory array allocated to store intermediate results. The code is probably more readable though.

 

[KrisBlueNZ]

I agree that the decision to use recursion should not be taken lightly. Code needs to make sure the termination condition will be reached within a reasonable number of recursions and the implications for the stack need to be clearly understood.

I think it's a matter of risk and severity of impact. Any kind of loop can make a program "non-deterministic" and so can many other factors, such as interrupts, task switching etc; I don't think recursion is alone in that respect. It's more dangerous than a loop because of the effect on the stack. Self-modifying code is a lot more dangerous than recursion IMO.

Yes, in a resource-constrained system you have to be careful of anything that uses the critical resources, and in a microcontroller, memory is a critical resource.

 

[Anoxynym]

This may be a cold thread, but here is my two cents worth.

I instrument my code by sprinkling it with diagnostic write statements. In C these use a global constant and preprocessor directives. When I turn them off they are not even compiled, so they add no overhead other than a bit of additional clutter in the source code. I find the additional clutter may even enhance the clarity of the code when I revisit it later.

At the head of the file I put something like

#define TRACE0 1 // enable trace writes at function entry and exit

Then in every function I insert

#if TRACE0
printf("entering function foo( Param1 = %d, Param2 = %d ) \n", Param1, Param2 );
#endif // TRACE0

as the first executed instruction in the function, i.e., after all the local variable declarations. This flags the entry to the function and displays its parameters.

I also write

#if TRACE0
printf("function foo(Param1 = %d, Param2 = %d) returns %d \n", Param1, Param2, ReturnValue );
#endif // TRACE0

as the last executed statement before the return statement in the function.

The trace writes tell me which function was executing when it crashed, making it fast and easy to locate bugs. I find it much easier than running the program in the debugger. Python's immediate crash in the interpreter make it pretty clear where the problem is much more easily than the edit -- compile -- execute sequence we use in C.

But as it applies to understanding recursion, these debug writes are the tool that can make the concept really transparent and easy to understand. This is how I cleared up all confusion in my mind about what recursion is and how it works.

There are some problems that benefit from recursive approach. Compilers and interpreters are examples that come to mind easily. Along with artificial intelligence (AI) facilities like backtracking, recursion can help solve very hard problems, such as, believe it or not, routing circuit boards and Field Programmable Gate Arrays (FPGAs).

I know this thread concerns python programming, not C. Python does not have the preprocessor statements familiar to C programmers. In python we can get the same tracing facility by using global variables with nearly the same syntax at the beginning and end of each function. Turning trace writes on and off consumes a tiny bit of time at execution. Such overhead is really down in the noise level as far as I am concerned.

I find python much cleaner and easier because it does not have all the "syntactic noise" that C suffers from, so it is a much better starting language as well as probably fast out pacing C as an implementation language. Python's built in functionality (e.g., Dictionaries and list support) are vastly simpler than doing the same thing in C.

Python supports object oriented programming and functional programming and provide these "out of the gate" so to speak. C programmers migrate to C++ for object oriented support, and are immediately burdened by a much greater level of syntactic noise by C++.

C can pass around pointers to functions and can sort of get some of the benefits of polymorphism by using void pointers, but at the abandonment of the protection inherent in type protection. Those hacks are not nearly as transparent and effortless as python's lazy binding.

I probably should break this up into several more concise rants. One of the topics is recursion. Another is trace writes. Another is the use of trace writes to make recursion more understandable. Another is relative merits of python vs. C programming. The recursion clarifying explanation could include the motivation for learning about recursion from its value in certain applications where it is close to indispensible because it simplifies certain problems, making them automatically solvable by computer (maybe using LONG execution runs) rather than nearly impossible.

 

[chopnhack]

This may be a cold thread, but here is my two cents worth.

Nope, I am still interested ;-)

Can you expand on this a bit? I am a novice and I can see the idea that you present, but I can't quite grasp the implementation. Specifically, can you give me a snippet of code (c is fine) that I can insert and try out?