Рекурсивная функция? [beginner]

Question

Я не понимаю рекурсивных функций.

Я написал этот код, чтобы помочь мне, но я не понимаю, почему он работает так, как он.

Он печатает назад шаги от 0 до числа n/2 i, но не знает, что заставляет его печатать каждый шаг, который он пропускал от низкого до высокого, потому что он стал рекурсивным. Я близко, но еще не там ...

#include <iostream> 
#include <conio.h> 
using namespace std; 

int recursiv(int); 

int times; 

int main(){  
    int x;  
    cout<<"Imput number\n"; 
    cin>>x;  
    recursiv(x); 

    getch(); 
    return 0; 
} 
int recursiv(int x){ 

    times++; 
    if(x) 
    recursiv(x/2); 
    cout<<"We are now at "<<x/2<<endl; 
    if (!x) 
    cout<< "We reached "<<x<<" but it took "<<times-1<< " steps\n"; 
    return 0; 
} 

Answer 1

Когда вы имеете дело с рекурсией вы должны понять две основные части кода функции: тот, который выполняется на пути вперед, и тот, который выполняется на обратном пути:

void X() { 
    // way forward 
    X(); 
    // way back 
} 

путь вперед часть выполняется при вызове функции снова и снова до конца рекурсии; путь назад выполняется при возврате от последнего вызова к первому.

void print(int x) { 
    if (!x) return; // end of recursion 
    std::cout << x << " "; 
    print(x-1); 
} 

Приведенный выше пример содержит std::cout << xна пути вперед, что означает, что вызов print(5) будет печатать: 5 4 3 2 1.

void print(int x) { 
    if (!x) return; // end of recursion 
    print(x-1); 
    std::cout << x << " "; 
} 

В приведенном выше примере переместил фактическую печать на пути назад часть функции, которая означает, что тот же самый вызов print(5) напечатает: 1 2 3 4 5.

Давайте вашу функцию (очищенную немного):

int recursiv(int x){ 
    times++; 
    if(!x) return 0; // split 
    recursiv(x/2); 
    cout << "We are now at "<< x/2 << endl; 
    return 0; 
} 

Мы можем выделить две наши части довольно легко.путь вперед является:

times++; 
if(x) return; 

В которой мы только увеличиваем наш Int параметр times (мы просто игнорировать условное для конца рекурсии здесь).

путь назад является:

cout<<"We are now at "<<x/2<<endl; 
return 0; 

, который будет выполнен из последнего вызова к первому (так же, как второй вариант, например). Поэтому взятие с самого низкого числа (ближе к 0 из-за условия конечной рекурсии), которое является последним, вызванным до конца рекурсии, первым, как и наш пример.

Answer 2

Если я правильно понимаю ваш вопрос:

Он должен печатать от высокой к низкой, но на самом деле печатает от низкого до высокого. почему это?

Линия cout<<"We are now at "<<x/2<<endl; после вызова для рекурсии. , поэтому функция вызывает себя с меньшим количеством снова и снова до тех пор, пока не достигнет критерия разрыва. Функция с наименьшей суммой вызывает std::cout, возвращает вторую наименьшую сумму, std::cout и так далее, пока последний не сделает это.

Если вы хотите получить результат в другом порядке, переместите указанную линию на две строки выше, поэтому каждое итерационное эхо до вызова ребенка.

пример:

int recursiv(int x, int times = 0) { 
    std::cout << "We are now at " << x/2 << std::endl; 

    if(x) 
    return recursiv(x/2, times + 1); 
    else 
    std::cout << "We reached " << x << " but it took " << times << " steps" << std::endl; 

    return 0; 
} 

Unrelated: глобальные переменные считаются плохой практикой. Для них есть варианты использования, это не один из них. Я исправил это внутри функции.