{"id":1809,"date":"2016-03-19T00:01:04","date_gmt":"2016-03-19T07:01:04","guid":{"rendered":"http:\/\/c-for-dummies.com\/blog\/?p=1809"},"modified":"2016-03-12T09:53:41","modified_gmt":"2016-03-12T17:53:41","slug":"a-recursive-permutation-function","status":"publish","type":"post","link":"https:\/\/c-for-dummies.com\/blog\/?p=1809","title":{"rendered":"A Recursive Permutation Function"},"content":{"rendered":"

Of course recursion is scary! At no other time in your programming career is your code more susceptible to stack overflows, which appear on the screen as ugly system errors when the code runs. I find that exciting.
\n
\nRecursion is a solution to the permutation problem when the length of text characters isn’t fixed. Instead, the length is a variable; the string is n<\/em> characters long. The permutations range from aaa...a<\/code> through zzz...z<\/code>. So the string’s length is what the recursive function must deal with, and that length is what determines when the function starts to unwind.<\/p>\n

Inside the recursive function you need a loop to generate characters from a<\/code> to z<\/code>. The recursive nature of the function slides that loop’s position to each element in the array, from 0 through n<\/em>.<\/p>\n

Sounds weird? Yeah, it is.<\/p>\n

Click here<\/a> to view the full code for the recursive password-cracking program. The recursive function is named compare()<\/em>, which is listed here:<\/p>\n

\r\nint compare(int pos,int len,char *s1,char *s2)\r\n{\r\n    char c;\r\n\r\n    if( pos == len)\r\n    {\r\n        if( strcmp(s1,s2)==0 )\r\n        {\r\n            printf(\"%s -> %s\\n\",s1,s2);\r\n            return(TRUE);\r\n        }\r\n        else\r\n            return(FALSE);\r\n    }\r\n    else\r\n    {\r\n        for( c='a'; c<='z' ; c++ )\r\n        {\r\n            s1[pos] = c;\r\n            pos++;\r\n            if( compare(pos,len,s1,s2) )\r\n                return(TRUE);\r\n            pos--;\r\n        }\r\n    }\r\n    return(FALSE);\r\n}<\/pre>\n
The function contains two parts. The first is at Line 30:<\/p>\n
    if( pos == len)<\/code><\/pre>\n
pos<\/code> is the position indicator, the key that eventually unwinds the recursion. It represents the character position in string s1<\/code>. When its length is equal to the length of string s2<\/code>, a comparison is made. The compare()<\/em> function then returns to itself with a value of either TRUE or FALSE, depending on the results of the strcmp()<\/em> function.<\/p>\n
It may seem like pos<\/code> is greater than len<\/code>, which is confusing. Remember that pos<\/code> references an array element. The last character in a 4-character string sits at element 3 in the array. When pos<\/code> is equal to len<\/code>, both strings are the same size and can be compared.<\/p><\/blockquote>\n
The second part is the condition when the two strings aren’t of equal length, which starts with the else<\/em> statement at Line 40. In this chunk of code, the compare()<\/em> function builds string s1<\/code>.<\/p>\n
The for<\/em> loop at Line 42 marches from a<\/code> to z<\/code>. The character is put into element pos<\/code> in char<\/em> array s1<\/code>. The position pos<\/code> is incremented to the next element in the array. compare()<\/em> is called recursively at Line 46 to process that next element.<\/p>\n
As long as pos < len<\/code>, the else<\/em> portion of the compare()<\/em> function continues to build string s1<\/code>. Eventually, the string aaa...a<\/code> is created, which is equal to the length of target string s2<\/code>. At that point, pos == len<\/code> and the strings are compared. If the strings match, TRUE is returned and the recursion unwinds. Otherwise, FALSE is returned. At that point, Line 48, the pos<\/code> indicator is decremented, and the next letter in the loop is processed, aaa...b<\/code>.<\/p>\n
The for<\/em> loop continues to change each character in the s1<\/code> array, just as the nested loops did in an earlier post<\/a>. As long as the compare()<\/em> function returns to itself with a FALSE value, the loop keeps permuting string s1<\/code>. It spins through all permutations up until zzz...z<\/code> and finally returns FALSE at Line 51 when the two strings cannot match.<\/p>\n
This recursive technique isn’t any faster than a solution using nested for<\/em> loops; the longer the string you type, the longer it takes Mr. Computer to crunch the results. A long string composed of a’s and b’s will process more quickly. If you type a long string with lots of z’s in it, expect to wait a while.<\/p>\n
The only advantage of using recursion is that the same function works regardless of the length of the target string.<\/p>\n","protected":false},"excerpt":{"rendered":"
The key to recursion is to ensure that the function eventually unwinds itself. Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[2],"tags":[],"class_list":["post-1809","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\/1809","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=1809"}],"version-history":[{"count":5,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1809\/revisions"}],"predecessor-version":[{"id":1827,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=\/wp\/v2\/posts\/1809\/revisions\/1827"}],"wp:attachment":[{"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1809"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1809"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/c-for-dummies.com\/blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1809"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}