{"id":525,"date":"2021-06-09T13:50:29","date_gmt":"2021-06-09T13:50:29","guid":{"rendered":"https:\/\/xcodeph.net\/?page_id=525"},"modified":"2021-06-09T14:14:43","modified_gmt":"2021-06-09T14:14:43","slug":"recursion","status":"publish","type":"page","link":"https:\/\/xcodeph.net\/index.php\/recursion\/","title":{"rendered":"Recursion"},"content":{"rendered":"\n

Recursion means “defining a problem in terms of itself”. This can be a very powerful tool in writing algorithms. Recursion comes directly from Mathematics, where there are many examples of expressions written in terms of themselves. For example, the Fibonacci sequence is defined as: F(i) = F(i-1) + F(i-2)<\/p>\n\n\n\n

<\/p>\n\n\n\n

The recursive function has two parts:<\/p>\n\n\n\n

  1. Base Case<\/li>
  2. Recursive Structure<\/li><\/ol>\n\n\n\n

    Base Case<\/strong>: The s<\/strong>mallest version of the problem for which we already know the solution or a terminating condition where a function can return the result immediately.<\/p>\n\n\n\n

    Recursive Structure:<\/strong> Finding the solution to a problem via the solution of its smaller sub-problems. Here function must call itself <\/em>to break the current problem down to a simpler level.<\/p>\n\n\n\n

    The typical recursive coding takes the following form:<\/p>\n\n\n\n

    if (test for simple case) {\n    return (simple computation without recursion);\n} else {\n    return (recursive solution);\n}<\/pre>\n\n\n\n
    The below image depicts how Recursion works:<\/strong><\/p>\n\n\n\n
    \"Working<\/figure>\n\n\n\n
    Program 1<\/p>\n\n\n\n
    #include <iostream>\nusing namespace std;\n\nvoid countDown(int count)\n{\n    cout << \"push \" << count << '\\n';\n    countDown(count-1); \/\/ countDown() calls itself recursively\n}\n \nint main()\n{\n    countDown(5);\n \n    return 0;\n}<\/pre>\n\n\n\n
    Program 2<\/p>\n\n\n\n
    #include <iostream>\nusing namespace std;\n\nvoid countDown(int count)\n{\n    cout << \"push \" << count << '\\n';\n \n    if (count > 1) \/\/ termination condition\n        countDown(count-1);\n \n    cout << \"pop \" << count << '\\n';\n}\n \nint main()\n{\n    countDown(5);\n    return 0;\n}<\/pre>\n\n\n\n
    Program 3<\/p>\n\n\n\n
    #include <iostream>\nusing namespace std;\nint sumTo(int);\n\nint main()\n{\n\t\tcout << sumTo(5);\n\n    return 0;\n}\n\n\/\/ return the sum of all the numbers between 1 and value (inclusive)\nint sumTo(int value)\n{\n    if (value <= 0)\n        return 0; \/\/ base case (termination condition)\n    else if (value == 1)\n        return 1; \/\/ base case (termination condition)\n    else\n        return sumTo(value - 1) + value; \/\/ recursive function call\n}\n<\/pre>\n\n\n\n
    Program 4<\/p>\n\n\n\n
    #include<iostream>\nusing namespace std;\t\n\n\tvoid print_backwards();\n\t\n\tint main()\n\t{\n\t\tprint_backwards();\n\t\tcout << \"\\n\";\n\t\treturn 0;\n\t}\n\t\n\tvoid print_backwards()\n\t{\n\t\tchar character;\n\t\t\n\t\tcout << \"Enter a character ('.' to end program): \";\n\t\tcin >> character;\n\t\tif (character != '.')\n\t\t{\n\t\t\tprint_backwards();\n\t\t\tcout << character;\n\t\t}\n\t}<\/pre>\n\n\n\n
    Program 5<\/p>\n\n\n\n
    #include<iostream>\nusing namespace std;\n\nint sum(int );\n\nint main()\n{\n    int number, result;\n\n    cout << \"Enter a positive integer: \";\n    cin >> number;\n\n    result = sum(number);\n\n    cout << \"sum - \" << result;\n\treturn 0;\n}\n\nint sum(int num)\n{\n    if (num!=0)\n        return num + sum(num-1); \/\/ sum() function calls itself\n    else\n        return num;\n}<\/pre>\n\n\n\n
    Program 6<\/p>\n\n\n\n
    #include <iostream>\nusing namespace std;\n\nint factorial(int n)\n{\n\tif(n!=0)\n\t\treturn n*factorial(n-1);\t\t\n\treturn 1;\n}\n\nint main()\n{\n\tint num,facto;\n\tcout << \"Enter a number: \";\n\tcin >> num;\n\tfacto=factorial(num);\n\tcout << facto;\n\treturn 0;\n}<\/pre>\n\n\n\n
    \"recursion_factorial.png\"<\/figure>\n\n\n\n
    Program 7<\/p>\n\n\n\n
    #include <iostream>\nusing namespace std;\n\ndouble power(double,int);\n\nint main()\n{\n   double base,pow;\n   int exponent;\n   cout << \"Enter Base: \";\n   cin >> base;\n   cout << \"Enter Exponent: \";\n   cin >> exponent;\n\n   pow=power(base,exponent);\n   cout << \"The value of \" << base \n\t   << \" to the power of \" << exponent \n\t   << \" is \" << pow;\n   return(0);\n}\n\ndouble power (double Num,int Exp)\n{\n   if(Exp <=0 )\t\t\/\/ Exp is non-positive\n       return(1);\n   else\n      return(Num * power(Num, Exp-1));\n}<\/pre>\n\n\n\n
    Program 8<\/p>\n\n\n\n
    #include <iostream>\n\nusing namespace std;\n\nvoid normalPrint(char *s)\n{\n\tif(*s) {\n\t\tputchar(*s);\n\t\tnormalPrint(s+1);\n\t}\n}\nvoid reversePrint(char *s)\n{\n\tif(*s) {\n\t\treversePrint(s+1);\n\t\tputchar(*s);\n\t}\n}\n\nint main() \n{\n\tchar *str = \"Hadji Tejuco\";\n\tnormalPrint(str);\n\tcout << endl;\n\treversePrint(str);\n\tcout << endl;\n\treturn 0;\n}<\/pre>\n\n\n\n
    Program 9<\/p>\n\n\n\n
    #include <iostream>\n\nusing namespace std;\n\nint n_to_the_kth_power(int n, int k)\n{\n\tif (k == 0) \n\t\treturn 1;\n\telse \n\t\treturn n * n_to_the_kth_power(n, k-1);\n}\n\nint main ()\n{\n\n  int n = 2, k = 10;\n  while (k >= 0) {\n\t  cout << n << \"**\" << k << \" = \" << n_to_the_kth_power(n,k) << endl; \n\t  k--;\n  }\n  while(1) {}\n  return 0;\n}<\/pre>\n\n\n\n
    Output<\/p>\n\n\n\n
    2**10 = 1024\n2**9 = 512\n2**8 = 256\n2**7 = 128\n2**6 = 64\n2**5 = 32\n2**4 = 16\n2**3 = 8\n2**2 = 4\n2**1 = 2\n2**0 = 1\n<\/pre>\n\n\n\n
    Program 10<\/p>\n\n\n\n
    #include <iostream>\nusing namespace std;\n\nint gcd (int m, int n)\n{\n\tif(n == 0) return m;\n\tcout << \"gcd(\" << m << ',' << n <<')'<< endl; \n\treturn gcd(n, m % n);\n}\n\nint main()\n{\n\tcout << \"gcd = \" << gcd(1256636, 1630968) << endl;\n\treturn 0;\n}<\/pre>\n\n\n\n
    Output<\/p>\n\n\n\n
    gcd = gcd(1256636,1630968)\ngcd(1630968,1256636)\ngcd(1256636,374332)\ngcd(374332,133640)\ngcd(133640,107052)\ngcd(107052,26588)\ngcd(26588,700)\ngcd(700,688)\ngcd(688,12)\ngcd(12,4)\n4\n<\/pre>\n\n\n\n
    Program 11<\/p>\n\n\n\n
    #include <iostream>\nusing namespace std;\n\nint fibo(int n)\n{\n\tif(n == 0 || n == 1) return n;\n\treturn fibo(n-1)+fibo(n-2);\n}\n\nint fibo_iter(int n)\n{\n\tif(n == 0 || n == 1) return n;\n\n\tint f0 = 0, f1 = 1, f2;\n\tfor(int i = 2; i <= n; i++) {\n\t\tf2 = f0 + f1;\n\t\tf0 = f1;\n\t\tf1 = f2;\n\t}\n\treturn f2;\n}\n\nint fibo_dynamic(int n)\n{\n        static int saved[100] = {0};\n\n\tif(saved[n] != 0) return saved[n];\n\n\tif(n == 0 || n == 1) {\n\t\tsaved[n] = n;\n\t\treturn saved[n];\n\t}\n\n\tsaved[n] = fibo_dynamic(n-1)+fibo_dynamic(n-2);\n\n\treturn saved[n];\n}\n\nint main()\n{\n\tint i;\n\tint n = 15;\n\tcout << \"recursive Fibonacci \" << endl;\n\tfor(i = 0; i < n; i++) \n\t\tcout <<  fibo(i) << \" \";\n\tcout << endl;\n\n\tcout << \"iterative Fibonacci \" << endl;\n\tfor(i = 0; i < n; i++) \n\t\tcout <<  fibo_iter(i) << \" \";\n\tcout << endl;\n\n\tcout << \"dynamic Fibonacci \" << endl;\n\tfor(i = 0; i < n; i++) \n\t\tcout <<  fibo_dynamic(i) << \" \";\n\tcout << endl;\n\n\treturn 0;\n}<\/pre>\n\n\n\n
    Output<\/p>\n\n\n\n
    recursive Fibonacci\n0 1 1 2 3 5 8 13 21 34 55 89 144 233 377\niterative Fibonacci\n0 1 1 2 3 5 8 13 21 34 55 89 144 233 377\ndynamic Fibonacci\n0 1 1 2 3 5 8 13 21 34 55 89 144 233 377<\/pre>\n\n\n\n
    \"recursive_diagram.png\"<\/figure>\n\n\n\n
    \"dynamic_recursive.png\"<\/figure>\n\n\n\n
    Program 11 (Palindrome)<\/p>\n\n\n\n
    #include <iostream>\nusing namespace std;\n  \nint reverse_digits(int n, int temp)\n{\n   if (n == 0)\n     return temp;\n  \n     temp = (temp * 10) + (n % 10);\n     return reverse_digits(n \/ 10, temp);\n}\n  \nint main()\n{\n   int num;\n   cout<<\"Enter the number to check palindrome:\"; cin>>num;\n  \n   int result = reverse_digits(num, 0);\n  \nif (result == num)\n   cout << \"Number \"<<num<<\" is a palindrome\" << endl;\nelse\n   cout << \"Number \"<<num<<\" is not a palindrome\"<< endl;\n   return 0;\n}\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
    Recursion means “defining a problem in terms of itself”. This can be a very powerful tool in writing algorithms. Recursion comes directly from Mathematics, where there are many examples of expressions written in terms of themselves. For example, the Fibonacci sequence is defined as: F(i) = F(i-1) + F(i-2) The recursive function has two parts: […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/pages\/525"}],"collection":[{"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/comments?post=525"}],"version-history":[{"count":3,"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/pages\/525\/revisions"}],"predecessor-version":[{"id":531,"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/pages\/525\/revisions\/531"}],"wp:attachment":[{"href":"https:\/\/xcodeph.net\/index.php\/wp-json\/wp\/v2\/media?parent=525"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}