AK's weblog

Entries tagged as recursion

Entries tagged as recursion

Related tags

Thursday, May 31. 2007

Endrekursionen und der gcc

Endrekursionen sind Rekursionen, bei denen der rekursive Funktionsaufruf die letzte Operation zum Berechnen des Funktionsergebnisses ist. Eine wichtige Eigenschaft von Endrekursionen ist, dass sie zu Iterationen transformiert werden können, d.h. der Speicherverbrauch auf dem Stack bleibt konstant, während bei nicht-endrekursiven Funktionen der Speicherverbrauch auf dem Stack mit der Rekursiontiefe wächst. Das ist insbesondere relevant für funktionale Sprachen, deren einziges Mittel zur Iterationen die Rekursion darstellt. Das sei einmal der Theorieteil.

Gestern hab ich mir aufgrund einer Diskussion mit nion zu dem Thema mal angeschaut, was der gcc mit endrekursiven Funktionen in C denn genau macht. Und siehe da: der gcc transformiert endrekursive C-Funktionen doch tatsächlich zu Iterationen! Folgende Codesnippets zeigen es deutlich:
  1. int sum (int n) {
  2.   if (n == 0)
  3.     return 0;
  4.  
  5.   return n + sum (n - 1);
  6. }

wird zu
  1. sum:
  2.         pushl   %ebp
  3.         xorl    %eax, %eax
  4.         movl    %esp, %ebp
  5.         movl    8(%ebp), %edx
  6. .L3:
  7.         testl   %edx, %edx
  8.         je      .L4
  9.         addl    %edx, %eax
  10.         decl    %edx
  11.         jmp     .L3
  12. .L4:
  13.         popl    %ebp
  14.         ret

Damit das auch etwas praxisrelevanter wird, hier der Code zum rekursiven Freigeben einer verketteten Liste:
  1. void delete_word_r(word_t * e) {
  2.         if (e) {
  3.                 word_t* next = e->next;
  4.                 if (e->word)
  5.                         free(e->word);
  6.                 free(e);
  7.                 delete_word_r(next);
  8.         }
  9. }

Der gcc macht folgendes daraus:
  1. delete_word_r:
  2.         pushl   %ebp
  3.         movl    %esp, %ebp
  4.         pushl   %esi
  5.         pushl   %ebx
  6.         movl    8(%ebp), %ebx
  7. .L33:
  8.         testl   %ebx, %ebx
  9.         je      .L38
  10.         movl    (%ebx), %eax
  11.         movl    4(%ebx), %esi
  12.         testl   %eax, %eax
  13.         je      .L36
  14.         subl    $12, %esp
  15.         pushl   %eax
  16.         call    free
  17.         addl    $16, %esp
  18. .L36:
  19.         subl    $12, %esp
  20.         pushl   %ebx
  21.         movl    %esi, %ebx
  22.         call    free
  23.         addl    $16, %esp
  24.         jmp     .L33
  25. .L38:
  26.         leal    -8(%ebp), %esp
  27.         popl    %ebx
  28.         popl    %esi
  29.         popl    %ebp
  30.         ret

Coole Sache. In beiden Assembler-Snippets ist weder ein "call sum" noch ein "call delete_word_r" zu finden.
Posted by Andreas Krennmair at 16:19 | Comments (4) | Trackbacks (0)
Defined tags for this entry: , , , ,
Related entries by tags:
(Page 1 of 1, totaling 1 entries)

About Me



Andreas Krennmair, software engineer, open-source developer, currently living and working in Berlin, Germany.

Calendar

Back July '17
Mon Tue Wed Thu Fri Sat Sun
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            

Quicksearch

Archives

Show tagged entries

Buttons










Syndicate This Blog

Blog Administration

Open login screen

Powered by

Serendipity PHP Weblog

Links

Blogroll

• xkcd.com
• Planet Debian
• MY POV ([expect the unexpected])
• C skills
• Planet Erlang / Published News
• armstrong on software
• Photos from akrennmair
• Das Metalab informiert
• dive into mark
• /usr/local/bin
• F!XMBR
• heise online News (full feed)
• JLog
• SecuriTeam Blogs
• .:Computer Defense:.
• Riot Porn
• Chaosradio
• Radiomultikulti vom RBB: Russendisko unplugged
• AK's weblog
• The Recurity Lablog
• milw0rm.com
• seclog.de
• ilja's blag
• udo.kernecker.at - mein leben als prinzregent... ;-)
• grabnerandi.at diary feed
• Hilli's WebLog
• accidents waiting to happen
• Venzi's Weblog
• TaoSecurity
• Irrlicht3d.org
• murphee's Rant
• waiterrant.net
• grml development blog
• mutt Changelog
• nion's blog
• Wannabe Everything
• blog@bytelabs
• Knowledge Brings Fear
• Die wunderbare Welt von Isotopp
• Fefes Blog
• law blog
• mikas blog
• BILDblog
• GoogleWatchBlog
• Krone - Blog
• The Lunatic Fringe
• mp's blog
• Su-Shee 2.0
• Sex, Drugs & Compiler Construction
• Qbi's Weblog
• gedankensplitter
• Ohns Gehirnschleimschmiede
• fh
• Clifford Wolf's Blog
• AK's moblog
• Telepolis News
• Slashdot
• Newssystem von bundesheer.at
• Riding Rails - home
• Serendipity
• O'Reilly Ruby
• CCC Events Weblog
• del.icio.us/dubrider
• del.icio.us/timpritlove
• del.icio.us/ak
• del.icio.us/mika
• AK's Soup
• Friends of ak
• Astronomy Picture of the Day
• german-bash.org - Die neuesten Zitate
• QDB
• WeirdWeirdWorld Latest Feed
• I CAN HAS CHEEZBURGER?
• The Trailer Mash
• Cruel.Com
• fun.drno.de
• Peter Pilz grüner Sicherheitssprecher Österreich Wien
• NPD-BLOG.INFO
• INSM Watchblog
• Hitler-Blog
• Everybody loves Eric Raymond
• Dilbert