{"id":1080,"date":"2014-11-29T00:01:22","date_gmt":"2014-11-29T08:01:22","guid":{"rendered":"http:\/\/c-for-dummies.com\/blog\/?p=1080"},"modified":"2014-11-22T07:51:18","modified_gmt":"2014-11-22T15:51:18","slug":"the-factorial-recursion","status":"publish","type":"post","link":"https:\/\/c-for-dummies.com\/blog\/?p=1080","title":{"rendered":"The Factorial Recursion"},"content":{"rendered":"

It’s the example of recursion most often used, but it’s not the best example. Of course, to illustrate a better example you need to approach concepts such as fractals and graphical programming doodads. My favorite form of recursion is traversing a directory tree. Regardless, the code for a factorial recursion remains the go-to workhorse.
\n
\nAs a reminder, a factorial is a mathematical calculation expressed as n<\/em>!, which I pronounce, “N-bang.” Mathematicians would say, “N factorial,” but they’re not C programmers.<\/p>\n

The calculation for n<\/em>! is n<\/em> × n<\/em>-1 × n<\/em>-2 × n<\/em>-3 . . . n<\/em>×1.<\/p>\n

In an earlier Lesson<\/a>, I showed how this calculation could be coded by using a loop. Below you see an example of coding a factorial by using recursion, i.e., a function that calls itself.<\/p>\n

\r\n#include <stdio.h>\r\n\r\nlong factorial(long f);\r\n\r\nint main()\r\n{\r\n    long a,b;\r\n\r\n    printf(\"Enter an integer: \");\r\n    scanf(\"%ld\",&a);\r\n    b = factorial(a);\r\n    printf(\"%ld! = %ld\\n\",a,b);\r\n\r\n    return(0);\r\n}\r\n\r\nlong factorial(long f)\r\n{\r\n    if(f == 1)\r\n        return(f);\r\n    else\r\n        return(f*factorial(f-1));\r\n}<\/pre>\n
The factorial()<\/em> function calls itself at Line 22, which is also where the factorial calculation is made:<\/p>\n
f*factorial(f-1);<\/code><\/pre>\n
The insane part of this process is that the function calls itself in the return<\/em> statement, which is typical of many recursive functions.<\/p>\n
In the C language, what goes into the parentheses happens first, so before anything is returned, the function calls itself with a decremented value of variable f<\/code>.<\/p>\n
The effect is that f<\/code> slides from its initial value down to 1, which is caught at Line 19. Then the value 1 is returned at Line 20.<\/p>\n
Where is it returned to?<\/p>\n
The value is returned to Line 22, where it’s multiplied by the previous value of f<\/code>, or f<\/code>+1. So the recursive calculation happens as the function unwinds, and it’s done backwards: f<\/code> × f<\/code>+1 × f<\/code>+2 × f<\/code>+3 . . . × f<\/code>. That value keeps returning until it’s finally returned from the function.<\/p>\n
That’s one recursive way to do a factorial. Other examples of recursion pop up in programming all the time, although it’s not as popular of a technique as working a loop.<\/p>\n
I admit that recursion isn’t the easiest thing to comprehend. In a future Lesson, I’ll explore traversing a directory tree by using recursion. That’s the example I coded that best taught me how recursion works.<\/p>\n","protected":false},"excerpt":{"rendered":"
The tried and true warhorse of the recursion examples. Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-1080","post","type-post","status-publish","format-standard","hentry","category-main"],"_links":{"self":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1080","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1080"}],"version-history":[{"count":8,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1080\/revisions"}],"predecessor-version":[{"id":1109,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1080\/revisions\/1109"}],"wp:attachment":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1080"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1080"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1080"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}