## Recursion

Please compose all posts in Emacs.

Moderators: phlip, Moderators General, Prelates

photosinensis
Posts: 163
Joined: Wed Aug 22, 2007 6:17 am UTC

### Re: Recursion

btilly wrote:
Govalant wrote:
wisnij wrote:
photosinensis wrote:Fibonacci is actually one of the unusual (though certainly not rare) cases where defining the function recursively is retarded--taking a problem solvable in O(log n) time and doing so in O(2^n) time.

Unless you cache the intermediate results.

If you're talking about getting the nth fibonacci number there's already a exact formula. It just uses integer powers and division by sqrt(5).

Calculating sqrt(5) to sufficient precision to give a precise answer is extremely difficult. The fastest solution that I know of for finding the exact integer value of the n'th Finbonacci number recursively uses the identities F2n = 2Fn+1Fn-Fn2, F2n+1 = Fn+12+Fn2, and F2n+2 = Fn+12+2Fn+1Fn. (I hope I worked those out correctly...) This allows one go to down by powers of two.

So, for instance, F25 would require (F12, F13). Which would require (F6. F7). Which would require (F3, F4). Which would require (F1, F2). Which are both 1.

All Fibonacci numbers are ints. Cast the solution as an int, see what comes out, and make adjustments to the final formula as necessary. Accuracy is an easily fixable problem when dealing with discreet values.
While I clicked my fav'rite bookmark, suddenly there came a warning,
And my heart was filled with mournng, mourning for my dear amour.
"'Tis not possible!" I uttered, "Give me back my free hardcore!"
Quoth the server: 404.

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

### Re: Recursion

photosinensis wrote:
btilly wrote:
Govalent wrote:If you're talking about getting the nth fibonacci number there's already a exact formula. It just uses integer powers and division by sqrt(5).

Calculating sqrt(5) to sufficient precision to give a precise answer is extremely difficult. The fastest solution that I know of for finding the exact integer value of the n'th Finbonacci number recursively uses the identities F2n = 2Fn+1Fn-Fn2, F2n+1 = Fn+12+Fn2, and F2n+2 = Fn+12+2Fn+1Fn. (I hope I worked those out correctly...) This allows one go to down by powers of two.

So, for instance, F25 would require (F12, F13). Which would require (F6. F7). Which would require (F3, F4). Which would require (F1, F2). Which are both 1.

All Fibonacci numbers are ints. Cast the solution as an int, see what comes out, and make adjustments to the final formula as necessary. Accuracy is an easily fixable problem when dealing with discreet values.

Sorry, but no.

The Fibonacci sequence grows exponentially, which means that the number of digits that you need to know to get the right answer for Fn goes up linearly with n. I guarantee you that your standard floating point libraries will be horribly wrong before long. And extended precision floating point libraries are very complex.

If you don't believe me, write an implementation that will correctly handle F100=354224848179261915075, and F200=280571172992510140037611932413038677189525. Then have it try to calculate F10_000.
Last edited by btilly on Sun Dec 23, 2007 6:55 am UTC, edited 1 time in total.
Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Contact:

### Re: Recursion

Anpheus wrote:Absolutely, you bring up totally valid points where recursion sometimes is more efficient. But the efficiency comes at a space cost, the stack. Unless your compiler is efficient, in which case it transforms the solution into one that is essentially iterative, I mean, as far as the CPU is considered, a jmp is a jmp, whether part of a loop or a function. (I'm skipping over some details so please don't pedant me about long jmp and different calling styles and what-not.)

Keep in mind that, while you can implement any recursive function without explicit recursion, it may require maintaining effectively a runtime stack yourself. You will save some space (you'll no longer need to record the return address, static link, and any variables no longer needed), but it won't reduce the overall order of the solution.

Another possible reason that recursion can be painful is specific to Sparc: You'll hit the number of hardware register windows provided in fairly short order and start trapping.

Anpheus wrote:As others have mentioned, if the compiler detects it, that code becomes iterative and will not pose a stack problem, but as you said, it would be a bad idea to do your debug and quality control with settings that you aren't using in production. IMO, the only difference between your debug and production settings should be added symbol information and whatever other extra information you can get out of the compiler and debugger, but nothing that significantly affects the machine code that results.

While that would be nice, and there are cases in which this is actually done, in general this isn't practical. You probably want your release code optimized, and optimized code is often very difficult to debug even if you have symbol information. ("What's the value of variable v? Oh, the compiler optimized it away, and I can't find that out? Well, shit.") For programs where speed is more important than correctness and being race free and such (and there are plenty of them, most notably games), your approach isn't the right way to do things IMHO.

Anpheus
I can't get any worse, can I?
Posts: 860
Joined: Fri Nov 16, 2007 10:38 pm UTC
Location: A privileged frame of reference.

### Re: Recursion

If you trust your compiler implicitly to the point where you'll let it do different things on a debug machine and on a production machine, you're making a grave error. As has already been pointed out, when the compiler changes code the errors change as well, and that makes it extremely confusing to reproduce problems.

And you're right, there isn't always a best solution where iterative will benefit, there are definitely cases where maintaining a stack is the most efficient solution. I'm not going to argue that. I am going to argue that the use of recursion has reached absurdity in programming. Just because it's there doesn't mean you need to do it.
Spoiler:

Code: Select all

`  /###\_________/###\  |#################|  \#################/   |##┌         ┐##|   |##  (¯`v´¯)  ##|   |##  `\ ♥ /´  ##|   |##   `\¸/´   ##|   |##└         ┘##|  /#################\  |#################|  \###/¯¯¯¯¯¯¯¯¯\###/`

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Contact:

### Re: Recursion

Anpheus wrote:If you trust your compiler implicitly to the point where you'll let it do different things on a debug machine and on a production machine, you're making a grave error. As has already been pointed out, when the compiler changes code the errors change as well, and that makes it extremely confusing to reproduce problems.

So what should, say, Valve do? Spend four times longer in development and raise the production costs four times because they have to debug optimized code, or get smashed at release because the code runs four times longer?

Look, you still have to test the release version, of course. But you can work for some time on just a debug build. If there is a bug in the debug build there is a bug in your code, and you should fix it (subject to a cost-benefit analysis). You can then move onto the release version and start to debug that. (Actually you should really keep up testing on a release build throughout, to make sure that there isn't something you can catch easily and early. However, the debug version should have the focus early on.)

And you're right, there isn't always a best solution where iterative will benefit, there are definitely cases where maintaining a stack is the most efficient solution. I'm not going to argue that. I am going to argue that the use of recursion has reached absurdity in programming. Just because it's there doesn't mean you need to do it.

Oh, of course. But the flip side is that if you have an algorithm that can be programmed cleaner with recursion, you should do so until profiling tells you that the overhead of the runtime stack is a problem.

Anpheus
I can't get any worse, can I?
Posts: 860
Joined: Fri Nov 16, 2007 10:38 pm UTC
Location: A privileged frame of reference.

### Re: Recursion

EvanED wrote:
Anpheus wrote:If you trust your compiler implicitly to the point where you'll let it do different things on a debug machine and on a production machine, you're making a grave error. As has already been pointed out, when the compiler changes code the errors change as well, and that makes it extremely confusing to reproduce problems.

So what should, say, Valve do? Spend four times longer in development and raise the production costs four times because they have to debug optimized code, or get smashed at release because the code runs four times longer?

Oh, good, I can come up with hypothetical strawmen too. What should Blizzard do? Spend a fourth as much time in development and release a product before its ready, and then have to make up those costs in bugs that weren't caught due to differences between debug and production machines, or should they release a product that works the first time because they first of all, wrote code in a provably correct and tested manner the first time and then not have to worry about those problems in production?

You're confusing the issue by confusing production with full debug symbol builds with regular debug builds. Neither of which are production. And I see no reason why you shouldn't run both, obviously, to catch all possible errors, but there's really no point in strawmanning my argument and then, pompously, saying that coding correctly, using tests, and doing every possible quality control test is valuable. Duh. We know that. I know that.

Oh, of course. But the flip side is that if you have an algorithm that can be programmed cleaner with recursion, you should do so until profiling tells you that the overhead of the runtime stack is a problem.

Absolutely, never over-optimize a problem. If you have an O(n3) algorithm and you're trying to find problems in your code, so you spend three weeks optimizing that algorithm to something like O(n2) and later find out that n is always less than, I don't know, six... you've wasted your time. You and I clearly both know when optimization is premature or not, so don't start bringing up such points as if you're a bastion of clarity here. There is no "flip side" other than common sense (something most programmers lack, admittedly.) My point still stands in its entirety: just because a tool is available, such as recursion, or to bring up other topics, polymorphism, object orientation, operator overloading or any other tools, doesn't mean you have to use them. At all. That said, if you're writing C code and you end up writing something that looks like it's object oriented, you probably wasted more time writing the framework for it than you gained writing it in C instead of learning a little C++.

It's always, always about using the right tool for the job, and we both know that EvanED. So, recursion isn't always the right tool for the job. There's a misconception given to people whenever they write code to write recursive code whenever possible when it's often stupid to do so. Fibonacci sequence, factorials, etc.
Spoiler:

Code: Select all

`  /###\_________/###\  |#################|  \#################/   |##┌         ┐##|   |##  (¯`v´¯)  ##|   |##  `\ ♥ /´  ##|   |##   `\¸/´   ##|   |##└         ┘##|  /#################\  |#################|  \###/¯¯¯¯¯¯¯¯¯\###/`

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Contact:

### Re: Recursion

Anpheus wrote:Oh, good, I can come up with hypothetical strawmen too. What should Blizzard do? Spend a fourth as much time in development and release a product before its ready, and then have to make up those costs in bugs that weren't caught due to differences between debug and production machines, or should they release a product that works the first time because they first of all, wrote code in a provably correct and tested manner the first time and then not have to worry about those problems in production?

No, you could replace "Valve" with "Blizzard" in my post, and I suspect it would still be true, though perhaps with less than 4. The difference would be how long they work with the production version. But if Blizzard doesn't primarily use an unoptimized version early in their production process (and at least try to replicate bugs in the debug build before using the release build to debug), I think they are doing it wrong.

You're confusing the issue by confusing production with full debug symbol builds with regular debug builds.

How? No I'm not.

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

### Re: Recursion

Anpheus wrote:It's always, always about using the right tool for the job, and we both know that EvanED. So, recursion isn't always the right tool for the job. There's a misconception given to people whenever they write code to write recursive code whenever possible when it's often stupid to do so. Fibonacci sequence, factorials, etc.

While I agree that stupid recursive functions are too easy to write, recursion often allows us to cleanly express some very efficient algorithms as well. For instance in the thread viewtopic.php?f=12&t=14595 I gave the following recursive algorithm for calculating n choose r:

Code: Select all

`def multiply_range(n, m)  if (m < n)    return 1  elsif (n == m)    return m  else    i = (n + m) / 2    return multiply_range(n, i) * multiply_range(i+1, m)  endenddef nCr(n, r)  return 0  if r > n  s = n/2  if (r < s)    return multiply_range(n-r + 1, n) / multiply_range(1, r)  else    return multiply_range(r + 1, n) / multiply_range(1, n-r)  endend`

That algorithm includes an efficient implementation of factorial that would be far, far harder to express efficiently without recursion.

Similarly in this thread I've outlined the most efficient algorithm that I know of for working out the n'th Fibonacci number. Again, it is most naturally expressed with recursion.

So both examples that you've given of things that should not be done with recursion can actually be done extremely efficiently with recursion! (Admittedly recursion gives nothing useful to the usual naive implementations.)
Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

JamesCFraser
Posts: 32
Joined: Wed Nov 14, 2007 9:47 pm UTC

### Re: Beginning in Computer Science

spelunker wrote:Honestly, though, how many times have any of you here actually written a recursive function in the wild? Most of the time it's a better idea to write it iteratively simply because it takes up less space and is more straightforward.

Don't get me wrong, every programmer worth his salt should understand recursion and be able to do it; I just don't use it a lot...

Sounds like you write some fairly boring code to me. In about 3/5 programs I write I make use of recursion. I also don't use recursion where an iterative loop is required (as that would blatantly be stupid).

I mainly write programs to solve problems, though.

spelunker
Posts: 102
Joined: Wed Dec 05, 2007 7:07 am UTC

### Re: Beginning in Computer Science

JamesCFraser wrote:
spelunker wrote:Honestly, though, how many times have any of you here actually written a recursive function in the wild? Most of the time it's a better idea to write it iteratively simply because it takes up less space and is more straightforward.

Don't get me wrong, every programmer worth his salt should understand recursion and be able to do it; I just don't use it a lot...

Sounds like you write some fairly boring code to me. In about 3/5 programs I write I make use of recursion. I also don't use recursion where an iterative loop is required (as that would blatantly be stupid).

I mainly write programs to solve problems, though.

3/5 seems kinda high to me. I've probably intentionally actually used it maybe twice in my college career so far. I almost considered using it last week, but decided against it.

My stuff is hardly boring, by the way

I'm just saying that recursion is awesome, recursion is clever, but it just isn't used that often. Rarely, I'd say, and if you looked around the programming world I doubt you would find many places that use recursion in 3/5 of their code.

Hench
Porn, hence, Man
Posts: 498
Joined: Wed Mar 28, 2007 4:16 pm UTC
Location: Right between my eyes
Contact:

### Re: Recursion

I'm not here to say that one is patently better than the other, but as someone raised on imperative languages recursion was a somewhat foreign concept at first. I've learned very quickly, however, that it has its place in programming paradigms just as iteration does.

Some examples of recursion in my own code:

Code: Select all

`private String getZeros(int num) {     return (num<10) ? "0" : "0"+getZeros(num/10);}`

The code is called from d = new DecimalFormat(getZeros(pages)); where pages is input into the program at runtime. There's no telling how large or small pages may be, but the output has to be formatted based on that number. The code returns a String containing the number of zeros equal to the number of places in the integer. So, a pages value less than 10 returns "0", a pages value greater than or equal to 10 but less than 100 yields "00", and so on. Writing this with an iterative loop, we get this:

Code: Select all

`private String getZeros(int num) {     String z = "0";     for(; num>10; num/=10, z = z + "0");     return z;}`

Honestly, I prefer the first because of its succinctness, and can't really speak to the efficiency (but I'd wager a guess and say the first is more efficient). I must mention, however, that when I first wrote this, my first thought was the write it recursively; it never crossed my mind to write the function with a for loop. Just sayin'.

A couple summers ago I wrote a Sudoku solver with a doctorate student at my university, and the main algorithm we came up with used recursion. Relevant code:

Code: Select all

`private boolean solve(Coord coord) {     // determine if coord location has a number in it.     // return true if done with puzzle.     // check for solvablility and return false if not solvable     for(int d = 1; d <= 9; d++)          if(d is available to by played here) {               make move;               clone coord and increment it to the next square in sequence;               if(solve(next)) return true;            // important bit               else undo the move made earlier;          }     return false;}`

This code works by brute forcing its way through the puzzle, checking along the way for inconsistencies so it fails fast. The algorithm is many orders of magnitude faster than pure brute force because in the commented out bits it fails fast and pops back up the stack to a solvable state and continues on from there. The recursive call there allows the algorithm to traverse the puzzle and not lose its states - as it fails further along in the puzzle and pops back, it can pick up where it left off.

Here's another example:

Code: Select all

`private boolean moveFocusFrom(JTextField src, int keycode) {     int index = fields.indexOf(src);     if(index == -1) return false;     if(keycode == VK_UP && --index == -1)          index = fields.size()-1;     else if((keycode == VK_DOWN || keycode == VK_ENTER) && ++index == fields.size())          index = 0;     JTextField next = fields.get(index);     return next.isEnabled() ? next.requestFocusInWindow() : moveFocusFrom(next,keycode);}`

This code provides for traversal of a list of text fields in an up-down order. "fields" holds all the text fields in the order they appear to the user, the top being at index 0 and bottom being at the end of the list. The keyPressed method provided by Swing provides the source of the key press and the key (the keycode there). The main trouble comes from the fact that it is possible for the user to disable any field at any point in the sequence, and the code is designed to skip over these disabled fields (checks with next.isEnabled()) and traverse to the next field. The recursion here makes this looks (to me, at least) elegant and at the very least very easy to read. I thought about doing it iteratively, but I settled on this implementation because of the ease of implementation.

So, in conclusion, I guess, I've found situations where I much prefer to use recursion over iteration. And these examples don't even include programs I've written in languages that don't allow for iteration anyway! But as far as I'm concerned, both have their place. I've honestly written more iterative functions than recursive, but I certainly recognize the power that recursion has in certain situations over iteration. I'm not saying one is better than the other. They both have their place.
Spoiler:
Your perceptions will not change reality, but simply color it.

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Contact:

### Re: Recursion

Hench wrote:Honestly, I prefer the first because of its succinctness, and can't really speak to the efficiency (but I'd wager a guess and say the first is more efficient).

Almost certainly not. Both perform more or less the same operations that are explicit from code. The recursive function has the fact that you're constantly pushing stack frames, which is the problem Anpheus had. (The recursive one isn't tail recursive, so it's not going to be optimized.) This raises the possibility that you could blow your stack, it reduces data locality, and it will increase your working set, perhaps pushing other data out of the cache. If you run on Sparc and call it with a number in the millions or billions, you will cause some spilling traps to the OS.

Now, that said, you're only going to have a few frames active at once, so it probably won't make a big difference and may even make no difference. However, I would be very surprised if the recursive version performed better.

I'm not saying you should have written it iteratively; there's more than just efficiency that goes into that decision. But, purely on the statement of efficiency, I suspect you're wrong.

A couple summers ago I wrote a Sudoku solver with a doctorate student at my university, and the main algorithm we came up with used recursion.

Backtracking is one of those stereotypical examples of when recursion is really nice.

Washer
Posts: 1
Joined: Fri Nov 23, 2007 7:07 am UTC

### Re: Beginning in Computer Science

Clumpy wrote:
segmentation fault wrote:
Clumpy wrote:On a similar note, is recursion very crucial?

If you're not being sarcastic, its just about the worst thing ever

Nope. I wasn't being sarcastic, but I wish I was . I just started beginning Computer Science and am enjoying it except for the mindfreak that is recursion. I'm sure I'll get it eventually.

In order to understand recursion, you must first understand recursion.

Workaphobia
Posts: 121
Joined: Thu Jan 25, 2007 12:21 am UTC

### Re: Beginning in Computer Science

Clumpy wrote:
segmentation fault wrote:
Clumpy wrote:On a similar note, is recursion very crucial?

If you're not being sarcastic, its just about the worst thing ever

Nope. I wasn't being sarcastic, but I wish I was . I just started beginning Computer Science and am enjoying it except for the mindfreak that is recursion. I'm sure I'll get it eventually.

Ah, recursion is my favorite topic in early CS curriculums. In fact, I just remembered what I have my signature set to (taken from my old CS2 textbook). If you really want to understand recursion, learn what the call stack is and trace how it changes as a recursion executes, step by step, or build a call tree. If you know how proofs by induction work, they go hand-in-hand with recursive definitions. And when designing recursive functions from scratch, when you get to the part that makes the recursive call, just assume that it works as per the function's specification, and move on to the rest of the algorithm - don't dwell on what goes on inside the recursion if it's not necessary.

I was going to reply to some of the earlier comments about iteration versus recursion, but I think it's already been beaten out. I'll just say that the computations you can do with iteration are a subset of those you can do with recursion, and declarative languages like Lisp and Oz (and apparently, also gcc) will automatically transform such recursion into iteration. Regardless of the performance cost and whether or not you actively decide to use recursion, it is critical to understanding how certain algorithms work.

Washer wrote:In order to understand recursion, you must first understand recursion.

God damnit, Washer, did you have to take my closer?

 Whoops, I actually didn't have it set on this account. Well, there we go.
Evidently, the key to understanding recursion is to begin by understanding recursion.

The rest is easy.

wing
the /b/slayer
Posts: 1876
Joined: Tue May 29, 2007 5:56 am UTC

### Re: Recursion

This thread sums up my views.
I AM A SEXY, SHOELESS GOD OF WAR!
Akula wrote:Our team has turned into this hate-fueled juggernaut of profit. It's goddamn wonderful.

segmentation fault
Posts: 1770
Joined: Wed Dec 05, 2007 4:10 pm UTC
Location: Nu Jersey
Contact:

### Re: Beginning in Computer Science

Washer wrote:In order to understand recursion, you must first understand recursion.

best explanation of recursion yet.

i also like: Recursion - see Recursion.

EDIT:

nevermind.

wing wrote:This thread sums up my views.

he wins.
people are like LDL cholesterol for the internet

Workaphobia
Posts: 121
Joined: Thu Jan 25, 2007 12:21 am UTC

### Re: Recursion

I disagree. Ten minutes with Uncyclopedia is enough time to cure anyone of an interest in self-referential and self-linked definitions of recursion and related topics.
Evidently, the key to understanding recursion is to begin by understanding recursion.

The rest is easy.

blob
Posts: 350
Joined: Thu Apr 05, 2007 8:19 pm UTC

### Re: Recursion

Those are actually definitions of infinite recursion, since they don't supply a base case.
Avatar yoinked from Inverloch.

"Unless ... unless they kill us, then animate our corpses as dead zombies to fight for them. Then I suppose they've taken our lives, AND our freedom."
- Elan, OOTS 421.

pieaholicx
The cake is a lie!
Posts: 531
Joined: Mon Oct 22, 2007 12:51 pm UTC
Contact:

### Re: Recursion

It's okay, I'm Chaotic Neutral. I can kill him over the loot.
Overexposure to pieaholicx may, in semi-rare cases, emancipate dental fillings, crowns, tooth enamel, and teeth.

EvilSporkMan
Posts: 19
Joined: Thu Nov 15, 2007 4:59 pm UTC

### Re: Recursion

1) The runtime of the naive fibonacci function is Theta(fib(n)) = Theta(phi^n) = o(2^n).
2) Recursion is the typical way to implement backtracking, which shows up all the time in speed programming and is great for generating k-combinations. You CAN write it with an explicit stack, but it's going to take you forever and the speed gain will be marginal at best (and you're going to be very sorry indeed if you use C++'s std::stack).

Posts: 274
Joined: Fri Nov 10, 2006 6:08 am UTC
Location: Wouldn't you rather know how fast I'm going?
Contact:

### Re: Beginning in Computer Science

spelunker wrote:Honestly, though, how many times have any of you here actually written a recursive function in the wild? Most of the time it's a better idea to write it iteratively simply because it takes up less space and is more straightforward.

Really? Recursive code is _much_ easier to debug (if you are familiar with it, of course). For production code, it's sometimes better to do the extra work to expand it to iterative code, but most of the time you can let the compiler optimize it, or it's really not worth the extra work on your part to save a minute amount of spacetime.
3.14159265... wrote:What about quantization? we DO live in a integer world?

crp wrote:oh, i thought you meant the entire funtion was f(n) = (-1)^n
i's like girls u crazy

zenten
Posts: 3799
Joined: Fri Jun 22, 2007 7:42 am UTC

### Re: Beginning in Computer Science

segmentation fault wrote:
Anpheus wrote:Yet that doesn't take into account a compiler which may be able to optimize the two into a non-recursive function. Which means your definition of recursion is a little weak: name a recursive function that can't be transformed into a non-recursive function according to your definition.

Ackermann (sp?) function REQUIRES recursion.

No, it can't. Otherwise a language that can't handle recursion isn't Turing complete.

segmentation fault
Posts: 1770
Joined: Wed Dec 05, 2007 4:10 pm UTC
Location: Nu Jersey
Contact:

### Re: Beginning in Computer Science

zenten wrote:No, it can't. Otherwise a language that can't handle recursion isn't Turing complete.

well, yeah. if you cant express Ackermann, you cant be Turing Complete.
people are like LDL cholesterol for the internet

Anpheus
I can't get any worse, can I?
Posts: 860
Joined: Fri Nov 16, 2007 10:38 pm UTC
Location: A privileged frame of reference.

### Re: Recursion

http://en.wikipedia.org/wiki/Brainfuck#Commands

Only supports iterative loops, but it's basically just a "jmp if not."

Like I said, the machine code for all CPUs is iterative, it's just a series of opcodes that have jump instructions to go to other parts of the code.
Spoiler:

Code: Select all

`  /###\_________/###\  |#################|  \#################/   |##┌         ┐##|   |##  (¯`v´¯)  ##|   |##  `\ ♥ /´  ##|   |##   `\¸/´   ##|   |##└         ┘##|  /#################\  |#################|  \###/¯¯¯¯¯¯¯¯¯\###/`

segmentation fault
Posts: 1770
Joined: Wed Dec 05, 2007 4:10 pm UTC
Location: Nu Jersey
Contact:

### Re: Recursion

Anpheus wrote:Like I said, the machine code for all CPUs is iterative, it's just a series of opcodes that have jump instructions to go to other parts of the code.

like the beginning of the Ackermann subroutine, which the subroutine calls?

The result of an Ackermann function call needs to be passed to the Ackermann function itself, which is why it needs to be recursive, even in assembly. Ackermann, aside from 2 cases, will call itself. it has to, by definition.

found an assembly example of Ackermann:

Spoiler:

Code: Select all

`Ackermann Proc  Near C, m:dword, n:dword                                    ; int Ackermann(int m, int n) { @@if1:   Cmp  m , 0               ; if (m == 0)          Je   @@then1                         Jmp  @@else1                 @@then1: Mov  eAx, n              ;   Ackermann = n+1;          Inc  eAx                            Jmp  @@endIf1               @@else1:                          ;  else  @@if2:       Cmp     m, 0        ;   if (m > 0 && n == 0)               Ja      @@and2                        Jmp     @@else2            @@and2:    Cmp     n, 0                        Je      @@then2                       Jmp     @@else2    @@then2:                                      Mov     eCx, m               Dec     eCx                    ;     Ackermann = Ackermann(m-1, 1);               invoke  Ackermann, eCx, 1               Jmp     @@endif2   @@else2:                        ;   else        @@if3:    Cmp     m, 0        ;    if (m > 0 && n > 0)               Ja      @@and3      ;         Ackermann =                Jmp     @@endif3    ;          Ackermann(m-1, Ackermann(m, n-1))     @@and3:   Cmp     n, 0        ;     Endif               Ja      @@then3     ;    Endif               Jmp     @@endif3    ;  Endif     @@then3:  Mov     eCx, n                      Dec     Cx          ; eAx = Ackermann(m, n-1)                invoke  Ackermann, m, eCx                Mov     eCx, m               Dec     eCx                        ; eAx = Ackermann(m-1, eAx)               invoke  Ackermann, eCx, eAx     @@endif3:  @@endif2:@@endif1:          Ret                      ; Remove current m, n from stackAckermann Endp`

it looks like a really bad example, im not sure if i should have even used it, but whatever. the point is, Ackermann calls Ackermann.
people are like LDL cholesterol for the internet

Cynic
Posts: 39
Joined: Sun Oct 08, 2006 5:08 pm UTC

### Re: Recursion

Everyone's getting confused because we're so concerned with whether code is iterative or recursive.
Instead of a more fundamental concept. The solution, or the problem, or something.

I know that it sounds a bit Zen, but there's a fundamental distinction, and I believe the original poster was asking about the concept of recursion, rather than our specific implementations of it. "On a similar note, is recursion very crucial?"

The fact that recursion currently uses up stack space and is generally nasty in terms of efficiency is purely implementation-specific. With the advent of newer computing architectures our computing model may be turned on its head completely, especially looking hundreds of years in the future. Recursion may become more efficient in the future. Quantum computing will make things rather different too.

I laughed when I saw people discussing compilers optimizing tail recursion, & complaining that it's no longer recursive, or something. Whether it's recursive or not is purely conceptual, as the assembly code is a bunch of binary ops and jmp statements. Whether it's solving a problem or not is incidental, the reality of it is that recursion is much like the concept of logic itself - invented by humans. So is it "really" recursive, if it has been optimized out?

The code is just stuff that flips a bunch of little switches X times per second. Or in the case of code being run right now by our brains.. who knows.

But the problem..

I'm finding it hard to elucidate this, but it's a bit like concrete & abstract syntax, & we're missing the point, or something. meh.

Izawwlgood
WINNING
Posts: 18686
Joined: Mon Nov 19, 2007 3:55 pm UTC
Location: There may be lovelier lovelies...

### Re: Recursion

Godel Escher Bach!
... with gigantic melancholies and gigantic mirth, to tread the jeweled thrones of the Earth under his sandalled feet.

Dongorath
Posts: 93
Joined: Tue Oct 16, 2007 1:17 pm UTC

### Re: Recursion

Recursion is usefull. Use it wisely ! Should be taught, but not as the true and only way to code.

Yes, I like recursion (CaML was the first language with which I learned to programm), but too often have I seen recursion break my stacks, so I try as often as I can to use iteration rather than recursion (especially since I wander at Project Euler).

segmentation fault
Posts: 1770
Joined: Wed Dec 05, 2007 4:10 pm UTC
Location: Nu Jersey
Contact:

### Re: Recursion

Cynic wrote:I laughed when I saw people discussing compilers optimizing tail recursion, & complaining that it's no longer recursive, or something. Whether it's recursive or not is purely conceptual, as the assembly code is a bunch of binary ops and jmp statements. Whether it's solving a problem or not is incidental, the reality of it is that recursion is much like the concept of logic itself - invented by humans. So is it "really" recursive, if it has been optimized out?

the point of the argument is whether or not recursion is always optimized out. its not, since ackermann requires recursion. otherwise you end up with an infinitely nested if statement.
people are like LDL cholesterol for the internet

Anpheus
I can't get any worse, can I?
Posts: 860
Joined: Fri Nov 16, 2007 10:38 pm UTC
Location: A privileged frame of reference.

### Re: Recursion

It's not impossible to implement Ackermann non-recursively, it's just not primitive-recursive, which means your code for implementing it iteratively will need to use a manually managed stack.
Spoiler:

Code: Select all

`  /###\_________/###\  |#################|  \#################/   |##┌         ┐##|   |##  (¯`v´¯)  ##|   |##  `\ ♥ /´  ##|   |##   `\¸/´   ##|   |##└         ┘##|  /#################\  |#################|  \###/¯¯¯¯¯¯¯¯¯\###/`

zenten
Posts: 3799
Joined: Fri Jun 22, 2007 7:42 am UTC

### Re: Beginning in Computer Science

segmentation fault wrote:
zenten wrote:No, it can't. Otherwise a language that can't handle recursion isn't Turing complete.

well, yeah. if you cant express Ackermann, you cant be Turing Complete.

Correct.

And since there are turing complete languages that cannot handle recursion, such as Commodore BASIC, or the Turing programming language. Now, doing the Ackermann function under these won't be *fun*, and it isn't worth the extra work (unless for some weird reason you're confined to a language that can't do recursion), but that's not the same thing.

Anpheus
I can't get any worse, can I?
Posts: 860
Joined: Fri Nov 16, 2007 10:38 pm UTC
Location: A privileged frame of reference.

### Re: Recursion

Huh? Hey, I understand that the type of recursion that the Ackermann function employs is intrinsically more interesting than say, most other cases of recursion, but it's not something that can't be done with a stack.

The key is you need the ability to have unbounded loops. This is the same as having an infinitely deep call stack for recursion.
Spoiler:

Code: Select all

`  /###\_________/###\  |#################|  \#################/   |##┌         ┐##|   |##  (¯`v´¯)  ##|   |##  `\ ♥ /´  ##|   |##   `\¸/´   ##|   |##└         ┘##|  /#################\  |#################|  \###/¯¯¯¯¯¯¯¯¯\###/`

segmentation fault
Posts: 1770
Joined: Wed Dec 05, 2007 4:10 pm UTC
Location: Nu Jersey
Contact:

### Re: Recursion

Anpheus wrote:It's not impossible to implement Ackermann non-recursively, it's just not primitive-recursive, which means your code for implementing it iteratively will need to use a manually managed stack.

yeah, you push values onto your stack, and re-run the function...kind of like a recursive function call which does all that for you.

its the same thing.
people are like LDL cholesterol for the internet

Anpheus
I can't get any worse, can I?
Posts: 860
Joined: Fri Nov 16, 2007 10:38 pm UTC
Location: A privileged frame of reference.

### Re: Recursion

Except recursion is just a simplification, a metaphor for one possible thing you could do with a stack. Using a manually managed stack you can avoid a stack overflow and get rid of any variables you don't need going on the stack (if you have temporary vars for example.)
Spoiler:

Code: Select all

`  /###\_________/###\  |#################|  \#################/   |##┌         ┐##|   |##  (¯`v´¯)  ##|   |##  `\ ♥ /´  ##|   |##   `\¸/´   ##|   |##└         ┘##|  /#################\  |#################|  \###/¯¯¯¯¯¯¯¯¯\###/`

segmentation fault
Posts: 1770
Joined: Wed Dec 05, 2007 4:10 pm UTC
Location: Nu Jersey
Contact:

### Re: Recursion

Anpheus wrote:Except recursion is just a simplification, a metaphor for one possible thing you could do with a stack. Using a manually managed stack you can avoid a stack overflow and get rid of any variables you don't need going on the stack (if you have temporary vars for example.)

if your passing unneeded variables to functions, youre doing it wrong.
people are like LDL cholesterol for the internet

Anpheus
I can't get any worse, can I?
Posts: 860
Joined: Fri Nov 16, 2007 10:38 pm UTC
Location: A privileged frame of reference.

### Re: Recursion

*eyebrow*
That's not what I was saying.

Let's say I have an algorithm that uses a temporary variable at some point in the function, and recursively calls itself.

So it allocates the space on the stack for all the variables that need to be passed to the recursively called one, PLUS the temporary variable that no longer needs to be used. Then it does this again. If I recursively call the function 35 times, then I've allocated 35 times the size of that variable on the stack unnecessarily.

Code: Select all

`unsigned int foo(unsigned int a, unsigned int b) {  unsigned int c = ...   //some transformation of a, b, dependent on c.  if (a == 0)    return b+1;  else if (a > 0 && b == 0)    return foo(a-1,b);  else if (a > 0 && b > 0)    return foo(a-1,foo(a,b-1));}`

I run this code, it allocates c on the stack, I follow design principles in which I inline what could also be another function in the interest of speed. However, doing so causes it to allocate an extra c for every call to the function.

This modified Ackermann will have an extra c every time it runs, unless I manually manage the stack iteratively. If I write the transformation of a and b as a function of c and extract that function, it's extremely likely the compiler will just inline it. The compiler will have to know that as far as the stack is concerned, c doesn't need to be stored, it's only used once and can be thrown away. I don't actually know if compilers will catch this, unfortunately. I do know however that an iterative, manually managed stack will avoid the problem of a stack overflow on the Ackermann function and would allow the above, modified Ackermann to run without taking up any more space on the stack than the unmodified Ackermann.
Spoiler:

Code: Select all

`  /###\_________/###\  |#################|  \#################/   |##┌         ┐##|   |##  (¯`v´¯)  ##|   |##  `\ ♥ /´  ##|   |##   `\¸/´   ##|   |##└         ┘##|  /#################\  |#################|  \###/¯¯¯¯¯¯¯¯¯\###/`

segmentation fault
Posts: 1770
Joined: Wed Dec 05, 2007 4:10 pm UTC
Location: Nu Jersey
Contact:

### Re: Recursion

Anpheus wrote:So it allocates the space on the stack for all the variables that need to be passed to the recursively called one, PLUS the temporary variable that no longer needs to be used. Then it does this again. If I recursively call the function 35 times, then I've allocated 35 times the size of that variable on the stack unnecessarily.

...?

c is allocated from the heap, not the stack. c is never put on the stack. you will have a bunch of c's in memory, yes, but not on the stack.

and if your c is static, theres only one c in memory, but still, it does not go on the stack.
Last edited by segmentation fault on Wed Jan 16, 2008 7:43 pm UTC, edited 1 time in total.
people are like LDL cholesterol for the internet

Anpheus
I can't get any worse, can I?
Posts: 860
Joined: Fri Nov 16, 2007 10:38 pm UTC
Location: A privileged frame of reference.

### Re: Recursion

Err... I don't see a malloc?
Spoiler:

Code: Select all

`  /###\_________/###\  |#################|  \#################/   |##┌         ┐##|   |##  (¯`v´¯)  ##|   |##  `\ ♥ /´  ##|   |##   `\¸/´   ##|   |##└         ┘##|  /#################\  |#################|  \###/¯¯¯¯¯¯¯¯¯\###/`

segmentation fault
Posts: 1770
Joined: Wed Dec 05, 2007 4:10 pm UTC
Location: Nu Jersey
Contact:

### Re: Recursion

statically allocated variables have a region of their own, and its not the stack.

either way, that c should be static, so youre not recreating it.
Last edited by segmentation fault on Wed Jan 16, 2008 7:45 pm UTC, edited 1 time in total.
people are like LDL cholesterol for the internet

Anpheus
I can't get any worse, can I?
Posts: 860
Joined: Fri Nov 16, 2007 10:38 pm UTC
Location: A privileged frame of reference.

### Re: Recursion

Do you code in C/C++ often?
Spoiler:

Code: Select all

`  /###\_________/###\  |#################|  \#################/   |##┌         ┐##|   |##  (¯`v´¯)  ##|   |##  `\ ♥ /´  ##|   |##   `\¸/´   ##|   |##└         ┘##|  /#################\  |#################|  \###/¯¯¯¯¯¯¯¯¯\###/`