fork(1) download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4.  void fun(int n){
  5.     if(n <= 0) // step (A)
  6.         return;
  7.  
  8.     fun(n-1); // Step(B)
  9.     cout << n <<' '; // step (C) it is called backtrack
  10.     return;
  11. }
  12. int main()
  13. {
  14.     fun(5);
  15.  
  16.     /*
  17.      Note before we start
  18.      step B is Recursion
  19.  
  20.      so Step C it's called a backtrack
  21.      because step C will start after the Recursion end
  22.  
  23.      the function we start at 5 and go at 4 then 3 then 2 then 1 then 0
  24.  
  25.      and then it will back, when it back step C will start
  26.      so the output will be 1 2 3 4 5 not 5 4 3 2 1
  27.  
  28.      so in recursion we start at 5 an go at 1
  29.      and when we back the step C start
  30.  
  31.     */
  32.  
  33.     /*
  34.         Recursion is Stack
  35.         so to understand the Recursion we must make a stack
  36.  
  37.         |      |
  38.         |      |
  39.         |      |  stack :)
  40.         |      |
  41.         |      |
  42.         |      |
  43.         --------
  44.  
  45.         in Main Function we Call fun(5) so put it in stack;
  46.         |      |
  47.         |      |
  48.         |      |
  49.         |      |
  50.         |      |
  51.         |fun(5)| <- top
  52.         --------
  53.  
  54.     inside the function
  55.      void fun(int n){
  56.         if(n <= 0) // step (A)
  57.             return;
  58.  
  59.         fun(n-1); // Step(B)
  60.         cout << n <<' '; // step (C)
  61.         return;
  62.     }
  63.     we will start t step A , there is a condition
  64.  
  65.         if(n <= 0)
  66.             return;
  67.  
  68.          5 <= 0  is false so he won't return ( think about "return" as "pop from stack" )
  69.          it will continue  and go in step B
  70.          and call fun(n-1) => fun(4) so put it in stack
  71.  
  72.         |      |
  73.         |      |
  74.         |      |
  75.         |      |
  76.         |fun(4)| <- top
  77.         |fun(5)|
  78.         --------
  79.         we will repeat the function and go in step A again
  80.  
  81.         if(n <= 0)
  82.             return;
  83.  
  84.          4 <= 0  is false so he won't return ( don't pop )
  85.          it will continue  and go in step B
  86.          and call fun(n-1) => fun(3) so put it in stack
  87.  
  88.         |      |
  89.         |      |
  90.         |      |
  91.         |fun(3)| <- top
  92.         |fun(4)|
  93.         |fun(5)|
  94.         --------
  95.         we will repeat the function again and go in step A
  96.  
  97.         if(n <= 0)
  98.             return;
  99.  
  100.          3 <= 0  is false
  101.          continue and go in step B
  102.          and call fun(n-1) => fun(2) so put it
  103.  
  104.         |      |
  105.         |      |
  106.         |fun(2)| <- top
  107.         |fun(3)|
  108.         |fun(4)|
  109.         |fun(5)|
  110.         --------
  111.         we will repeat the function again and go in step A
  112.  
  113.         if(n <= 0)
  114.             return;
  115.  
  116.          2 <= 0  is false
  117.          continue and go in step B
  118.          and call fun(n-1) => fun(1) so put it
  119.  
  120.         |      |
  121.         |fun(1)| <- top
  122.         |fun(2)|
  123.         |fun(3)|
  124.         |fun(4)|
  125.         |fun(5)|
  126.         --------
  127.         we will repeat the function again and go in step A
  128.  
  129.         if(n <= 0)
  130.             return;
  131.  
  132.          1 <= 0  is false
  133.          continue and go in step B
  134.          and call fun(n-1) => fun(0) so put it
  135.  
  136.         |fun(0)| <- top
  137.         |fun(1)|
  138.         |fun(2)|
  139.         |fun(3)|
  140.         |fun(4)|
  141.         |fun(5)|
  142.         --------
  143.         now Repeat again and go in step A
  144.         if(n <= 0)
  145.             return;
  146.  
  147.          0 <= 0  is True So it will return ( That means that we will POP from stack )
  148.  
  149.         |      |
  150.         |fun(1)| <- top
  151.         |fun(2)|
  152.         |fun(3)|
  153.         |fun(4)|
  154.         |fun(5)|
  155.         --------
  156.  
  157.         ** next the Backtracking will be happened **
  158.  
  159.         remember in fun(1) we finish step (B) already
  160.         so step (C) will start and print 1
  161.  
  162.         fun(n-1); // Step(B)
  163.         cout << n <<' '; // step (C)
  164.         return;
  165.  
  166.         after step step C
  167.         there is a (return) that mean pop from stack
  168.  
  169.         |      |
  170.         |      |
  171.         |fun(2)| <- top
  172.         |fun(3)|
  173.         |fun(4)|
  174.         |fun(5)|
  175.         --------
  176.  
  177.         in fun(2) we finish step (B) already
  178.         so step (C) will start and print 2
  179.  
  180.         after step step C
  181.         there is a (return) that mean pop from stack
  182.  
  183.         |      |
  184.         |      |
  185.         |      |
  186.         |fun(3)| <- top
  187.         |fun(4)|
  188.         |fun(5)|
  189.         --------
  190.  
  191.         in fun(3) we finish step (B) already
  192.         so step (C) will start and print 3
  193.  
  194.         after step step C
  195.         there is a (return) that mean pop from stack
  196.  
  197.         |      |
  198.         |      |
  199.         |      |
  200.         |      |
  201.         |fun(4)| <- top
  202.         |fun(5)|
  203.         --------
  204.  
  205.         in fun(4) we finish step (B) already
  206.         so step (C) will start and print 4
  207.  
  208.         after step step C
  209.         there is a (return) that mean pop from stack
  210.  
  211.         |      |
  212.         |      |
  213.         |      |
  214.         |      |
  215.         |      |
  216.         |fun(5)| <- top
  217.         --------
  218.  
  219.         in fun(5) we finish step (B) already
  220.         so step (C) will start and print 5
  221.  
  222.         after step step C
  223.         there is a (return) that mean pop from stack
  224.  
  225.         |      |
  226.         |      |
  227.         |      |
  228.         |      |
  229.         |      |
  230.         |      |
  231.         --------
  232.  
  233.         Stack is Empty So The Function had been finished :D
  234.  
  235.         output : 1 2 3 4 5
  236.  
  237.     */
  238.  
  239.     return 0;
  240. }
  241.  
Success #stdin #stdout 0s 4352KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 2 3 4 5
https://ideone.com/qbrcgS
Recursion is simple
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!