A recursive function calls itself. That’s a strange and beautiful concept, one that saves a lot of coding time, but how does it really work?
\n
\nBefore I get into the traditional factorial recursion example, the following code demonstrates a simple and visual example of recursion.<\/p>\n
\r\n#include <stdio.h>\r\n\r\nint recurse(int v)\r\n{\r\n printf(\"v = %d\\n\",v);\r\n if( v == 5 )\r\n return(v);\r\n recurse(v+1);\r\n}\r\n\r\nint main()\r\n{\r\n int a = 0;\r\n\r\n recurse(a);\r\n\r\n return(0);\r\n}<\/pre>\nIf you build this code, you may see a -Wreturn-type<\/code> compiler warning. The code is fine, despite the warning.<\/p><\/blockquote>\nIn this code, recurse()<\/em> is a recursive function. It calls itself at Line 8:<\/p>\nrecurse(v+1);<\/code><\/p>\nThat statement is legal, and it works. No limitation exists on a function calling itself, but the code must have a way to escape. That escape valve is provided at Line 6 with an if<\/em> statement. All the calls to recurse()<\/em> at Line 8 are unwound by the return<\/em> at Line 7.<\/p>\nHere’s a sample run:<\/p>\n
v = 0\r\nv = 1\r\nv = 2\r\nv = 3\r\nv = 4\r\nv = 5<\/code><\/pre>\nSo v<\/code> keeps increasing because recurse()<\/em> keeps calling itself. Then when v<\/code> is equal to 5, the return<\/em> statement kicks in and the whole thing unwinds. It’s a rather convoluted way to increment a variable 5 times, and nothing is really done with that variable, but the function is recursive.<\/p>\nNow if it didn’t work, then the code would run amok. With recurse()<\/em> continually calling itself, eventually the stack pointer<\/em>, which keeps track of function calls in C, would exceed its allocated memory. To see that disaster in action, comment out Lines 6 and 7 in the code so that the recurse()<\/em> function looks like this:<\/p>\n\r\nint recurse(int v)\r\n{\r\n printf(\"v = %d\\n\",v);\r\n\/\/ if( v == 5 )<\/span>\r\n\/\/ return(v);<\/span>\r\n recurse(v+1);\r\n}<\/pre>\nBuild and run again.<\/p>\n
On my computer, I saw the following:<\/p>\n
...\r\nv = 262000\r\nv = 262001\r\nv = 262002\r\nv = 262003\r\nv = 262004\r\nv = 262005\r\nSegmentation fault: 11<\/code><\/pre>\nAfter calling itself 262,005 times, the recurse()<\/em> function finally blew the stack. That’s the situation you want to avoid.<\/p>\nIn next week’s Lesson<\/a>, I’ll show how a factorial calculation can be done by using recursion.<\/p>\n","protected":false},"excerpt":{"rendered":"Hopefully this simple demonstration doesn’t blow your mind. Continue reading